A note on coloring vertex-transitive graphs (Q2341047)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A note on coloring vertex-transitive graphs
scientific article

    Statements

    A note on coloring vertex-transitive graphs (English)
    0 references
    0 references
    0 references
    22 April 2015
    0 references
    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\}\).
    0 references
    graph coloring
    0 references
    vertex-transitive graphs
    0 references
    Borodin-Kostochka conjecture
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references