Linear and 2-frugal choosability of graphs of small maximum average degree

DOI10.1007/S00373-010-1009-7zbMATH Open1234.05083OpenAlexW2015986552MaRDI QIDQ659749FDOQ659749

Frédéric Havet, Nathann Cohen

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00459692/file/RR-7213.pdf

Recommendations

• Linear list colorings of graphs with maximum average degrees bounded.
• Linear list coloring of some sparse graphs
• Linear choosability of graphs
• Linear choosability of graphs
• Linear choosability of sparse graphs

zbMATH Keywords

planar graphdischarging methodfrugal colouringlinear colouring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Acyclic colorings of planar graphs
• Linear coloring of planar graphs with large girth
• Colouring a graph frugally
• Linear coloring of graphs
• Linear choosability of graphs
• Linear choosability of sparse graphs

Cited In (3)

• Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
• Linear colorings of subcubic graphs
• \(k\)-forested choosability of planar graphs and sparse graphs

This page was built for publication: Linear and 2-frugal choosability of graphs of small maximum average degree

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