Coloring a graph with -1 colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker

DOI10.1016/J.EJC.2014.09.006MaRDI QIDQ472396zbMATH OpenOpenAlexWikidataFDO

Authors Daniel W. Cranston, Landon Rabern

Publication date 19 November 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.5380

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: Borodin and Kostochka conjectured that every graph $G$ with maximum degree $Deltage9$ satisfies $chilemaxomega,Delta-1$. We carry out an in-depth study of minimum counterexamples to the Borodin-Kostochka conjecture. Our main tool is the identification of graph joins that are $f$-choosable, where $f(v)=d(v)-1$ for each vertex $v$. Since such a join cannot be an induced subgraph of a vertex critical graph with $chi=Delta$, we have a wealth of structural information about minimum counterexamples to the Borodin-Kostochka conjecture. Our main result proves that certain conjectures that are prima facie weaker than the Borodin-Kostochka conjecture are in fact equivalent to it. One such equivalent conjecture is the following: Any graph with $chigeDelta=9$ contains $$ as a subgraph.

Recommendations

• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Graphs with \(\chi=\Delta\) have big cliques
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Equivalence of two conjectures on equitable coloring of graphs
• A strengthening of Brooks' theorem

Cites work

• scientific article; zbMATH DE number 3851121 (Why is no real title available?)
• scientific article; zbMATH DE number 3920511 (Why is no real title available?)
• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A fractional analogue of Brooks' theorem
• A strengthening of Brooks' theorem
• Brooks' theorem via the Alon-Tarsi theorem
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• Graph colouring and the probabilistic method
• Graphs with \(\chi=\Delta\) have big cliques
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• List colouring when the chromatic number is close to the order of the graph
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On graphs having prescribed clique number, chromatic number, and maximum degree
• On hitting all maximum cliques with an independent set
• On the choosability of complete multipartite graphs with part size three
• The colour theorems of Brooks and Gallai extended
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(15)

• A note on coloring vertex-transitive graphs
• The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Painting squares in \(\Delta^2-1\) shades
• scientific article; zbMATH DE number 1409249 (Why is no real title available?)
• A note on \(\Delta\)-critical graphs
• Coloring hammer-free graphs with \(\Delta - 1\) colors
• Chromatic-choosability of hypergraphs with high chromatic number
• Partitioning of a graph into induced subgraphs not containing prescribed cliques
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• \(k\)-colouring when \(k\) is close to \(\Delta\)
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Special issue in honour of Landon Rabern
• Graphs with \(\chi=\Delta\) have big cliques
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors

This page was built for publication: Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker

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