Asymptotically optimal frugal colouring
From MaRDI portal
Publication:965250
DOI10.1016/j.jctb.2009.07.002zbMath1211.05046MaRDI QIDQ965250
Michael S. O. Molloy, Bruce A. Reed
Publication date: 21 April 2010
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.2009.07.002
Related Items
Separation dimension and degree, Distributed algorithms for the Lovász local lemma and graph coloring, Frugal, acyclic and star colourings of graphs, Corrigendum to ``Asymptotically optimal frugal colouring [J. Comb. Theory, Ser. B 100, No. 2, 226--246 (2010)], The complexity of frugal colouring, Intersection dimension and graph invariants
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lopsided Lovász Local lemma and Latin transversals
- On a packing and covering problem
- Colouring a graph frugally
- A bound on the total chromatic number
- A strengthening of Brooks' theorem
- Linear coloring of graphs
- Concentration of measure and isoperimetric inequalities in product spaces
- Weighted sums of certain dependent random variables
- Concentration for Independent Permutations
- The Randomized Coloring Procedure with Symmetry-Breaking
- A constructive proof of the general lovász local lemma
- An algorithmic approach to the Lovász local lemma. I
- Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
- 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
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- On a combinatorial game
- 25 pretty graph colouring problems