Linear Choosability of Sparse Graphs

Details Linear Choosability of Sparse Graphs Linear Choosability of Sparse Graphs

2010-07-09

arxiv.org/abs/1007.1615v1

Discrete Math. Vol. 311, no. 17, 2011, pp. 1910-1917

Mathematics

Combinatorics

12 pages, 2 figures

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Linear Choosability of Sparse Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Choosability of Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Choosability of Sparse Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645503