2011/02/19 by Xin Zhang, Zhang, Xin, Guizhen Liu +4
Computer Science · Mathematics · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #math.CO #msc:05C10 #msc:05C15
paper · pdf · doi:10.48550/arxiv.1102.3987
Please cite this paper in press as X. Zhang, G. Liu, J.-L. Wu, k-forested choosability of graphs with bounded maximum average degree, Bulletin of the Iranian Mathematical Society, to appear
arxiv created 2011/02/19 · openalex publication_date 2011/02/19 · arxiv updated 2011/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A proper vertex coloring of a simple graph is k-forested if the graph induced by the vertices of any two color classes is a forest with maximum degree less than k. A graph is k-forested q-choosable if for a given list of q colors associated with each vertex v, there exists a k-forested coloring of G such that each vertex receives a color from its own list. In this paper, we prove that the k-forested choosability of a graph with maximum degree Δ≥ k≥ 4 is at most \lceil\fracΔk-1\rceil+1, \lceil\fracΔk-1\rceil+2 or \lceil\fracΔk-1\rceil+3 if its maximum average degree is less than 12/5, 8/3 or 3, respectively.