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.5380WikidataQ123239294 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
05C35: Extremal problems in graph theory
05C15: Coloring of graphs and hypergraphs
05C07: Vertex degrees
Related Items
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, Painting squares in \(\Delta^2-1\) shades, Graphs with $\chi=\Delta$ Have Big Cliques
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
