A note on coloring vertex-transitive graphs (Q2341047): Difference between revisions

Summary: 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 \leqslant \max \{\omega, \lceil\frac{5\Delta + 3}{6}\rceil\}\), and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with \(\Delta \geqslant 13\) we prove the Borodin-Kostochka conjecture, i.e., \(\chi\leqslant\max\{\omega,\Delta-1\}\).