Equitable list tree-coloring of bounded treewidth graphs

The equitable list tree-coloring model is an useful tool to formulate a structure decomposition problem on the complex network with some security considerations. In this paper, it is proved that the equitable list vertex arboricity of every graph with treewidth ω is at most ⌈ Δ ( G ) / 2 ⌉ + ω − 2 whenever Δ ( G ) ≥ 4 ω + 1, and moreover, if such a graph does not contain K 3, 3 as a topological minor, then its equitable list vertex arboricity is at most ⌈ Δ ( G ) / 2 ⌉ provided that ω ∈ { 2, 3, 4 } and Δ ( G ) ≥ 6 ω − 3.

Authors

• Yan Li
• Xin Zhang Northwestern Polytechnical University

Keywords

• Equitable coloring
• Tree coloring
• List coloring
• Arboricity
• Treewidth