Contents

Ars Combinatoria

  • Research article

Upper Bounds for the Vertex Folkman Number \(F_v(3,3,3;4)\) and \(F_v(3,3,3;5)\)

Fei Deng1, Meilian Liang2, Zehui Shao3, Xiaodong Xu4
1 School of Information Science and Technology, Chengdu University of Technology, Chengdu, 610059, China
2School of Mathematics and Information Science, Guangxi University, Nanning 530004, China
3Faculty of Science and Technology, Macau University, Av. Padre Torhas Pereira, Taipa, Macau, China; School of Information Science & Technology, Chengdu University, Chengdu, 610106, China
4Guangxi Academy of Science, Nanning, Guangxi 530007,China
  • Published: 31/10/2013

Abstract

For positive integers \(t\) and \(k\), the \({vertex}\) (resp. edge) Folkman number \(F_v(t,t,t;k)\) (resp. \(F_e(t,t,t;k)\)) is the smallest integer \(n\) such that there is a \(K_k\)-free graph of order \(n\) for which any three coloring of its vertices (resp. edges) yields a monochromatic copy of \(K_t\). In this note, an algorithm for testing \((t,t,\ldots,t;k)\) in cyclic graphs is presented and it is applied to find new upper bounds for some vertex or edge Folkman numbers. By using this method, we obtain \(F_v(3,3,3;4) \leq 66\), \(F_v(3,3,3;5) \leq 24\), which leads to \(F_v(6,6,6;7) \leq 726\), and \(F_v(3,3,3;8) \leq 727\).

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Fei Deng, Meilian Liang, Zehui Shao, Xiaodong Xu. Upper Bounds for the Vertex Folkman Number \(F_v(3,3,3;4)\) and \(F_v(3,3,3;5)\)[J], Ars Combinatoria, Volume 112. 249-256. .