Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree |
| |
Authors: | Nathann Cohen Fr��d��ric Havet |
| |
Institution: | (2) University of California, San Diego, USA; |
| |
Abstract: | A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph
G is 2-frugally (resp. linearly) L-colourable if for a given list assignment
L:V(G)? 2\mathbb N{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum
average degree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|