Colouring graphs when the number of colours is almost the maximum degree
From MaRDI portal
Publication:462929
DOI10.1016/j.jctb.2014.06.004zbMath1301.05130OpenAlexW2014924232MaRDI QIDQ462929
Bruce A. Reed, Michael S. O. Molloy
Publication date: 22 October 2014
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2014.06.004
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)
Related Items
Ramsey-nice families of graphs, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Distant set distinguishing edge colourings of graphs, Adaptable and conflict colouring multigraphs with no cycles of length three or four, On the inclusion chromatic index of a graph, When removing an independent set is optimal for reducing the chromatic number, Conflict‐free chromatic number versus conflict‐free chromatic index, A note on \(\Delta\)-critical graphs, Colorings, transversals, and local sparsity, Asymptotically good edge correspondence colourings, The complexity of star colouring in bounded degree graphs and regular graphs, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Hardness transitions and uniqueness of acyclic colouring, Unnamed Item, A local epsilon version of Reed's conjecture, Distant sum distinguishing index of graphs with bounded minimum degree, ON GRAPH FOLDING AND MOBILE RADIO FREQUENCY ASSIGNMENT, Colouring H-free graphs of bounded diameter., Open Problems on Graph Coloring for Special Graph Classes, New algorithm for calculating chromatic index of graphs and its applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Which problems have strongly exponential complexity?
- (\(\Delta-k\))-critical graphs
- Concentration of measure and isoperimetric inequalities in product spaces
- Weighted sums of certain dependent random variables
- Concentration for Independent Permutations
- Graph Theory and Probability
- A constructive proof of the general lovász local lemma
- An algorithmic approach to the Lovász local lemma. I
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- A constructive proof of the Lovász local lemma
- Colouring graphs when the number of colours is nearly the maximum degree
- Probability Inequalities for Sums of Bounded Random Variables
- Paths, Trees, and Flowers
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Graph colouring and the probabilistic method
