Geodesic
Bounds for the smallest $k$-chromatic graphs of given girth
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3.

Voir la notice de l'article provenant de la source Episciences

Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$. After giving an overview of what is known about $n_g(k)$, we provide some new lower bounds based on exhaustive searches, and then obtain several new upper bounds using computer algorithms for the construction of witnesses, and for the verification of their correctness. We also present the first examples of reasonably small order for $k = 4$ and $g > 5$. In particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$, $30 \leq n_7(4) \leq 171$. 
@article{DMTCS_2019_21_3_a9,
     author = {Exoo, Geoffrey and Goedgebeur, Jan},
     title = {Bounds for the smallest $k$-chromatic graphs of given girth},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-9/}
}
TY  - JOUR
AU  - Exoo, Geoffrey
AU  - Goedgebeur, Jan
TI  - Bounds for the smallest $k$-chromatic graphs of given girth
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-9/
DO  - 10.23638/DMTCS-21-3-9
LA  - en
ID  - DMTCS_2019_21_3_a9
ER  - 
%0 Journal Article
%A Exoo, Geoffrey
%A Goedgebeur, Jan
%T Bounds for the smallest $k$-chromatic graphs of given girth
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-9/
%R 10.23638/DMTCS-21-3-9
%G en
%F DMTCS_2019_21_3_a9
Exoo, Geoffrey; Goedgebeur, Jan. Bounds for the smallest $k$-chromatic graphs of given girth. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi : 10.23638/DMTCS-21-3-9. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-9/

Cité par Sources :