Colouring a graph frugally

DOI10.1007/BF01195001MaRDI QIDQ1280272zbMATH OpenOpenAlexFDO

Authors Hugh Hind, Michael Molloy, Bruce Reed

Publication date 14 March 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01195001

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Lov%EF%BF%BD%EF%BF%BDsz+local+lemma&go=Go Lov��sz local lemma]probabilistic methodsgraph colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Asymptotically optimal frugal colouring
• Asymptotically optimal frugal colouring
• Coloring graphs with sparse neighborhoods
• Improved bounds on coloring of graphs
• Coloring -colorable graphs using relatively small palettes

Cites work

• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• A parallel algorithmic version of the local lemma
• An algorithmic approach to the Lovász local lemma. I

Cited in

(41)

• Improved bounds on linear coloring of plane graphs
• Frugal, acyclic and star colourings of graphs
• Bounds on vertex colorings with restrictions on the union of color classes
• Proper conflict-free coloring of graphs with large maximum degree
• \(k\)-forested coloring of planar graphs with large girth
• Graph coloring with cardinality constraints on the neighborhoods
• On a theorem about vertex colorings of graphs
• Linear coloring of planar graphs with large girth
• \(k\)-forested choosability of planar graphs and sparse graphs
• Distributed algorithms for the Lovász local lemma and graph coloring
• Star Chromatic Index
• Asymptotically optimal frugal colouring
• Paint cost and the frugal distinguishing number
• Linear coloring of graphs
• Intersection dimension and graph invariants
• On linear coloring of planar graphs with small girth
• Upper bounds on the linear chromatic number of a graph
• Linear choosability of sparse graphs
• Separation dimension and degree
• Linear coloring of planar graphs without 4-cycles
• The complexity of frugal colouring
• Locally identifying colourings for graphs with given maximum degree
• New upper bounds on linear coloring of planar graphs
• Asymptotically optimal frugal colouring
• Chromatic coloring with a maximum color class
• Better bounds for poset dimension and boxicity
• Linear choosability of graphs
• Linear and 2-frugal choosability of graphs of small maximum average degree
• Counting colorings of triangle-free graphs
• Improved bounds on coloring of graphs
• Coloring graphs with sparse neighborhoods
• Conflict-free colourings of graphs and hypergraphs
• The linear \(t\)-colorings of Sierpiński-like graphs
• The \((d, 1)\)-total labelling of Sierpiński-like graphs
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• Dynamic proper colorings of a graph
• Linear colorings of subcubic graphs
• A general framework for hypergraph coloring
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• Nondegenerate colourings in the Brooks theorem
• A result on linear coloring of planar graphs

This page was built for publication: Colouring a graph frugally

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1280272)