Colouring graphs when the number of colours is almost the maximum degree
DOI10.1016/J.JCTB.2014.06.004zbMATH Open1301.05130OpenAlexW2014924232MaRDI QIDQ462929FDOQ462929
Authors: Michael Molloy, Bruce Reed 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Graph Theory and Probability
- Paths, Trees, and Flowers
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- Concentration of measure and isoperimetric inequalities in product spaces
- Weighted sums of certain dependent random variables
- Title not available (Why is that?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Graph colouring and the probabilistic method
- An algorithmic approach to the Lovász local lemma. I
- Title not available (Why is that?)
- A constructive proof of the general Lovász local lemma
- Concentration for Independent Permutations
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- A constructive proof of the Lovász local lemma
- Title not available (Why is that?)
- Title not available (Why is that?)
- Colouring graphs when the number of colours is nearly the maximum degree
- (\(\Delta-k\))-critical graphs
Cited In (30)
- Deciding Relaxed Two-Colorability—A Hardness Jump
- Title not available (Why is that?)
- Colouring graphs when the number of colours is nearly the maximum degree
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Hardness transitions and uniqueness of acyclic colouring
- Colouring H-free graphs of bounded diameter.
- A note on \(\Delta\)-critical graphs
- Distant sum distinguishing index of graphs with bounded minimum degree
- Colorings, transversals, and local sparsity
- New algorithm for calculating chromatic index of graphs and its applications
- The complexity of colouring problems on dense graphs
- On graph folding and mobile radio frequency assignment
- Adaptable and conflict colouring multigraphs with no cycles of length three or four
- A local epsilon version of Reed's conjecture
- On the inclusion chromatic index of a graph
- Ramsey-nice families of graphs
- When removing an independent set is optimal for reducing the chromatic number
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Distant set distinguishing edge colourings of graphs
- Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
- Open problems on graph coloring for special graph classes
- Asymptotically good edge correspondence colourings
- Graphs with chromatic numbers strictly less than their colouring numbers
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Graphs with chromatic number close to maximum degree
- The complexity of star colouring in bounded degree graphs and regular graphs
- Conflict‐free chromatic number versus conflict‐free chromatic index
- (\(\Delta-k\))-critical graphs
- Title not available (Why is that?)
- 19-linear-colorable graphs with maximum degree 6
This page was built for publication: Colouring graphs when the number of colours is almost the maximum degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462929)
