Linear choosability of sparse graphs |
| |
Authors: | Daniel W Cranston Gexin Yu |
| |
Institution: | aDepartment of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284, United States;bDepartment of Mathematics, College of William & Mary, Williamsburg, VA 23185, United States |
| |
Abstract: | A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , 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 Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then . |
| |
Keywords: | Linear coloring List coloring Planar graph Discharging method Maximum average degree |
本文献已被 ScienceDirect 等数据库收录! |
|