A Note on Coloring Vertex-Transitive Graphs

[摘要] 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 +

[学科分类] 离散数学和组合数学

[关键词] Graph coloring;Vertex-transitive graphs;Borodin-Kostochka Conjecture