Improved upper bound for the degenerate and star chromatic numbers of graphs

DOI10.1007/s10878-016-0076-yzbMath1376.05050OpenAlexW2509952732MaRDI QIDQ2410096

Xue Liang Li, Jian-Sheng Cai, Gui Ying Yan

Publication date: 17 October 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-016-0076-y

zbMATH Keywords

upper boundchromatic numberstar coloringentropy compression methoddegenerate coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ An upper bound for the choice number of star edge coloring of graphs ⋮ Entropy compression versus Lovász local lemma

Cites Work

• Improved bounds on coloring of graphs
• Degenerate and star colorings of graphs on surfaces
• On acyclic colorings of planar graphs
• Acyclic edge-coloring using entropy compression
• Star coloring of graphs
• A conjecture of Borodin and a coloring of Grünbaum
• A constructive proof of the general lovász local lemma
• The Two-Coloring Number and Degenerate Colorings of Planar Graphs

This page was built for publication: Improved upper bound for the degenerate and star chromatic numbers of graphs