Linear choosability of sparse graphs

DOI10.1016/J.DISC.2011.05.017zbMATH Open1225.05095arXiv1007.1615OpenAlexW2141381908MaRDI QIDQ2275448FDOQ2275448

Authors: Daniel W. Cranston, Gexin Yu 

Publication date: 9 August 2011

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

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$.

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

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

zbMATH Keywords

list coloringplanar graphdischarging methodmaximum average degreelinear coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Acyclic colorings of planar graphs
• 25 pretty graph colouring problems
• Multicriterial graph problems with MAXMIN criterion
• Linear coloring of planar graphs with large girth
• Colouring a graph frugally
• Linear coloring of graphs
• Linear choosability of graphs

Cited In (13)

• 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
• Linear list colorings of graphs with maximum average degrees bounded.

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)