A note on coloring vertex-transitive graphs

作者：Cranston Daniel W^*; Rabern Landon

来源：Electronic Journal of Combinatorics, 2015, 22(2): P2.1.

DOI：10.37236/4626

• graph coloring
• vertex transitive
• Borodin Kostochka conjecture

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 <= max{omega, [5 Delta+3/6}, and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with Delta >= 13 we prove the Borodin Kostochka conjecture, i.e., chi <= max{omega, Delta - 1}.

• 出版日期2015-4-14