Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+ All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only \$99

 Relative Articles Dynamic choosability of triangle-free graphs and sparse random graphs On edge-group choosability of graphs Choosability in signed planar graphs On group choosability of total graphs On Choosability with Separation of Planar Graphs with Forbidden Cycles Choosability with Separation in Complete Multipartite Graphs On choosability with separation of planar graphs with lists of different sizes Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles Chromatic-choosability of the power of graphs Choosability and paintability of the lexicographic product of graphs More...
Mathematics  2010

# Linear Choosability of Sparse Graphs

 Full-Text   Cite this paper

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)\ge \ceil{\Delta(G)/2}+1\$. In this paper, we prove the following results: (1) if \$\mad(G)<12/5\$ and \$\Delta(G)\ge 3\$, then \$\lcl(G)=\ceil{\Delta(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)\ge 9\$, then \$\lcl(G)\le\ceil{\Delta(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)\le\ceil{\Delta(G)/2}+4\$.

Full-Text