Linear coloring of sparse graphs

DOI10.1016/J.DAM.2011.10.028MaRDI QIDQ412383zbMATH OpenOpenAlexFDO

Authors Qian Wu, Yingqian Wang

Publication date 4 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.10.028

zbMATH Keywords

girthmaximum degreemaximum average degreelinear coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Recommendations

• Linear coloring of graphs
• Linear list coloring of some sparse graphs
• Linear list r-hued coloring of sparse graphs
• Coloring sparse hypergraphs
• A GRASP for coloring sparse graphs
• Linear Ramsey numbers of sparse graphs
• Coloring graphs with sparse neighborhoods
• Linear colorings of subcubic graphs
• Graph coloring in linear time

Cites work

• Improved bounds on linear coloring of plane graphs
• Linear choosability of graphs
• Linear choosability of sparse graphs
• Linear coloring of graphs
• Linear coloring of graphs embeddable in a surface of nonnegative characteristic

Cited in

(12)

• Linear coloring of planar graphs with girth at least five
• A GRASP for coloring sparse graphs
• \(k\)-forested choosability of planar graphs and sparse graphs
• Graph coloring in the estimation of sparse derivative matrices: Instances and applications
• Linear list r-hued coloring of sparse graphs
• Linear coloring of graphs
• On linear coloring of planar graphs with small girth
• Linear list colorings of graphs with maximum average degrees bounded.
• Linear choosability of sparse graphs
• The linear \(t\)-colorings of Sierpiński-like graphs
• Linear list coloring of some sparse graphs
• Linear colorings of subcubic graphs

This page was built for publication: Linear coloring of sparse graphs

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