Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
From MaRDI portal
Publication:472396
DOI10.1016/j.ejc.2014.09.006zbMath1303.05032arXiv1203.5380OpenAlexW2052286712WikidataQ123239294 ScholiaQ123239294MaRDI QIDQ472396
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
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)
Related Items
Painting squares in \(\Delta^2-1\) shades ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors ⋮ A note on \(\Delta\)-critical graphs ⋮ The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree ⋮ Special issue in honour of Landon Rabern ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ 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 ⋮ Chromatic-choosability of hypergraphs with high chromatic number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- List colouring when the chromatic number is close to the order of the graph
- Brooks' theorem via the Alon-Tarsi theorem
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Hajos' graph-coloring conjecture: Variations and counterexamples
- A strengthening of Brooks' theorem
- The colour theorems of Brooks and Gallai extended
- On the choosability of complete multipartite graphs with part size three
- A Fractional Analogue of Brooks' Theorem
- Graphs with $\chi=\Delta$ Have Big Cliques
- On hitting all maximum cliques with an independent set
- On graphs having prescribed clique number, chromatic number, and maximum degree
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Graph colouring and the probabilistic method
