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

DOI10.1016/J.EJC.2014.09.006zbMATH Open1303.05032arXiv1203.5380OpenAlexW2052286712WikidataQ123239294 ScholiaQ123239294MaRDI QIDQ472396FDOQ472396

Authors: Daniel W. Cranston, Landon Rabern 

Publication date: 19 November 2014

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree
• A note on coloring vertex-transitive graphs
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Painting squares in \(\Delta^2-1\) shades
• Title not available (Why is that?)
• 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
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Graphs with \(\chi=\Delta\) have big cliques

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)