-forested choosability of planar graphs and sparse graphs

详细信息    查看全文

• 作者：Xin Zhang ^{sdu.zhang@yahoo.com.cn} ; Guizhen Liu ; ^{gzliu@sdu.edu.cn} ; Jian-Liang Wu ^{jlwu@sdu.edu.cn}
• 关键词：k-forested coloring ; Linear coloring ; Frugal coloring ; Maximum average degree ; Planar graph
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：6 March, 2012
• 年：2012
• 卷：312
• 期：5
• 页码：999-1005
• 全文大小：240 K

文摘

A proper vertex coloring of a simple graph is -forested if the subgraph induced by the vertices of any two color classes is a -forest, i.e.?a forest with maximum degree at most . The -forested coloring is also known as linear coloring, which has been extensively studied in the literature. In this paper, we aim to extend the study of -forested coloring to general -forested colorings for every by combinatorial means. Precisely, we prove that for a fixed integer and a planar graph with maximum degree and girth , if , then the -forested chromatic number of is actually . Moreover, we also prove that the -forested chromatic number of a planar graph with maximum degree and girth is provided . In addition, we show that the -forested chromatic number of an outerplanar graph is at most for every . In fact, all these results are proved for not only planar graphs but also for sparse graphs, i.e.?graphs having a low maximum average degree , and we actually prove a choosability version of these results.