论文部分内容阅读
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 al (G) is the list-coloring version of this concept.Kronk and Mitchem (1975) proved that every toroidal graph G without 3-cycles has a(G) ≤ 2.Choi and Zhang (2014) proved that every toroidal graph G without 4-cycles has a(G) ≤ 2.Borodin and Ivanova (2009)proved that every planar graph G without 4-cycles adjacent to 3-cycles has al (G) ≤ 2.