A note on the list vertex arboricity of toroidal graphs

作者：Wang, Yiqiao^*; Chen, Min; Wang, Weifan

来源：Discrete Mathematics, 2018, 341(12): 3344-3347.

DOI：10.1016/j.disc.2018.08.021

• Toroidal graph
• Complete graph K-7
• List vertex arboricity

The vertex arboricity a(G) of a graph G is the minimum number of colors required to color the vertices of G such that no cycle is monochromatic. The list vertex arboricity a(l)(G) is the list-coloring version of this concept. In this note, we prove that if G is a toroidal graph, then a(l)(G) <= 4; and a(l)(G) = 4 if and only if G contains K-7 as an induced subgraph.

• 出版日期2018-12
• 单位北京中医药大学; 浙江师范大学