Linear choosability of sparse graphs

DOI10.1016/J.DISC.2011.05.017MaRDI QIDQ2275448zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston, Gexin Yu

Publication date 9 August 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1615

zbMATH Keywords

list coloringplanar graphdischarging methodmaximum average degreelinear coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We study the linear list chromatic number, denoted $lcl(G)$, of sparse graphs. The maximum average degree of a graph $G$, denoted $mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. It is clear that any graph $G$ with maximum degree $Delta(G)$ satisfies $lcl(G)geceilDelta(G)/2+1$. In this paper, we prove the following results: (1) if $mad(G)<12/5$ and $Delta(G)ge3$, then $lcl(G)=ceilDelta(G)/2+1$, and we give an infinite family of examples to show that this result is best possible; (2) if $mad(G)<3$ and $Delta(G)ge9$, then $lcl(G)leceilDelta(G)/2+2$, and we give an infinite family of examples to show that the bound on $mad(G)$ cannot be increased in general; (3) if $G$ is planar and has girth at least 5, then $lcl(G)leceilDelta(G)/2+4$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• 25 pretty graph colouring problems
• Acyclic colorings of planar graphs
• Colouring a graph frugally
• Linear choosability of graphs
• Linear coloring of graphs
• Linear coloring of planar graphs with large girth
• Multicriterial graph problems with MAXMIN criterion

Cited in

(13)

• Linear list colorings of graphs with maximum average degrees bounded.
• On linear coloring of planar graphs with small girth
• Linear coloring of sparse graphs
• Linear choosability of graphs
• List-recoloring of sparse graphs
• A result on linear coloring of planar graphs
• Linear list coloring of some sparse graphs
• Linear colorings of subcubic graphs
• \(k\)-forested choosability of planar graphs and sparse graphs
• Linear choosability of graphs
• Linear and 2-frugal choosability of graphs of small maximum average degree
• An introduction to the discharging method via graph coloring
• Linear list r-hued coloring of sparse graphs

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

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