Decomposition of sparse graphs, with application to game coloring number

作者：Montassier, Mickael^*; Pecher, Arnaud; Raspaud, Andre; West, Douglas B; Zhu, Xuding

来源：Discrete Mathematics, 2010, 310(10-11): 1520-1523.

DOI：10.1016/j.disc.2010.01.008

• Edge-partition
• Forest
• Subgraphs with bounded maximum degree

Let k be a nonnegative integer, and let m(k) = 4(k 1)(k 3)/k(2) 6k 6. We prove that every simple graph with maximum average degree less than mk decomposes into a forest and a subgraph with maximum degree at most k (furthermore, when k <= 3 both subgraphs can be required to be forests). It follows that every simple graph with maximum average degree less than mk has game coloring number at most 4 k.

• 出版日期2010-6-6
• 单位中山大学