Chromatic vertex Folkman numbers
The electronic journal of combinatorics, Tome 27 (2020) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For graph $G$ and integers $a_1 \ge \cdots \ge a_r \ge 2$, we write $G \rightarrow (a_1 ,\cdots ,a_r)^v$ if and only if for every $r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i \in \{1, \cdots, r\}$. The vertex Folkman number $F_v(a_1 ,\cdots ,a_r; s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G \rightarrow (a_1 ,\cdots ,a_r)^v$. It is well known that if $G \rightarrow (a_1 ,\cdots ,a_r)^v$ then $\chi(G) \geq m$, where $m = 1+ \sum_{i=1}^r (a_i - 1)$. In this paper we study such Folkman graphs $G$ with chromatic number $\chi(G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s \ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G \rightarrow (s,\cdots_r,s)^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ with respect to this property. Among others we conjecture that for every $s \ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s;s+1)$ vertices with $\chi(G)=2s-1$ and $G\rightarrow (s,s)^v$.
DOI : 10.37236/7862
Classification : 05C55, 05C35

Xiaodong Xu  1   ; Meilian Liang  2   ; Stanisław P. Radziszowski  3

1 Guangxi Academy of Sciences Nanning, 530007, P.R.China
2 School of Mathematics and Information Science Guangxi University, Nanning, 530004, P.R.China
3 Department of Computer Science Rochester Institute of TechnologyRochester, NY
@article{10_37236_7862,
     author = {Xiaodong Xu and Meilian Liang and Stanis{\l}aw P. Radziszowski},
     title = {Chromatic vertex {Folkman} numbers},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {3},
     doi = {10.37236/7862},
     zbl = {1441.05153},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7862/}
}
TY  - JOUR
AU  - Xiaodong Xu
AU  - Meilian Liang
AU  - Stanisław P. Radziszowski
TI  - Chromatic vertex Folkman numbers
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7862/
DO  - 10.37236/7862
ID  - 10_37236_7862
ER  - 
%0 Journal Article
%A Xiaodong Xu
%A Meilian Liang
%A Stanisław P. Radziszowski
%T Chromatic vertex Folkman numbers
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7862/
%R 10.37236/7862
%F 10_37236_7862
Xiaodong Xu; Meilian Liang; Stanisław P. Radziszowski. Chromatic vertex Folkman numbers. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/7862

Cité par Sources :