We prove bounds on the chromatic number $\chi$ of a vertex-transitive graph in terms of its clique number $\omega$ and maximum degree $\Delta$. We conjecture that every vertex-transitive graph satisfies $\chi \le \max \{\omega, \left\lceil\frac{5\Delta + 3}{6}\right\rceil\}$, and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with $\Delta \ge 13$ we prove the Borodin–Kostochka conjecture, i.e., $\chi\le\max\{\omega,\Delta-1\}$.
@article{10_37236_4626,
author = {Daniel W. Cranston and Landon Rabern},
title = {A note on coloring vertex-transitive graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/4626},
zbl = {1310.05087},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4626/}
}
TY - JOUR
AU - Daniel W. Cranston
AU - Landon Rabern
TI - A note on coloring vertex-transitive graphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/4626/
DO - 10.37236/4626
ID - 10_37236_4626
ER -
%0 Journal Article
%A Daniel W. Cranston
%A Landon Rabern
%T A note on coloring vertex-transitive graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4626/
%R 10.37236/4626
%F 10_37236_4626
Daniel W. Cranston; Landon Rabern. A note on coloring vertex-transitive graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4626
