A note on coloring vertex-transitive graphs

MaRDI QIDQ2341047zbMATH OpenFDO

Authors Daniel W. Cranston, Landon Rabern

Publication date 22 April 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6550, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph coloringvertex-transitive graphsBorodin-Kostochka conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: 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 $chilemaxleftomega,leftlceilfrac5Delta+36ightceilight$ and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with $Deltage13$ we prove the Borodin-Kostochka conjecture, i.e., $chilemaxomega,Delta-1$.

Recommendations

• scientific article; zbMATH DE number 1286500
• Coloring Graphs with Dense Neighborhoods
• scientific article; zbMATH DE number 741287
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker

Cites work

• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A Theorem on k-Saturated Graphs
• A note on hitting maximum and maximal cliques with a stable set
• A note on vertex list colouring
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
• A strengthening of Brooks' theorem
• An improved bound for the strong chromatic number
• Another bound on the chromatic number of a graph
• Graph colouring and the probabilistic method
• Graphs with \(\chi=\Delta\) have big cliques
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Independence, clique size and maximum degree
• Independent systems of representatives in weighted graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On hitting all maximum cliques with an independent set
• On the Strong Chromatic Number
• Transversals of Vertex Partitions in Graphs

Cited in

(9)

• Two more characterizations of König-Egerváry graphs
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• scientific article; zbMATH DE number 1054731 (Why is no real title available?)
• Strong cliques in vertex‐transitive graphs
• A note on transformations of edge colorings of bipartite graphs
• Colourings, homomorphisms, and partitions of transitive digraphs
• Vertex-transitive CIS graphs
• Multiple list colouring of planar graphs
• Graphs with \(\chi=\Delta\) have big cliques

This page was built for publication: A note on coloring vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2341047)