Asymptotically optimal frugal colouring

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

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

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