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

DOI10.1007/S00373-010-1009-7MaRDI QIDQ659749zbMATH OpenOpenAlexFDO

Authors Nathann Cohen, Frédéric Havet

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

zbMATH Keywords

discharging methodfrugal colouringlinear colouringplanar graph

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

• \(k\)-forested choosability of graphs with bounded maximum average degree
• Linear colorings of subcubic graphs
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• \(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)