2013/07/11 by Ilkyoo Choi, Choi, Ilkyoo
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1307.3293
16 pages, 10 figures
arxiv created 2013/07/11 · openalex publication_date 2013/07/11 · arxiv updated 2013/07/15 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
The choosability χ_ℓ(G) of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that χ_ℓ(G)≤ 7, and χ_ℓ(G)=7 if and only if G contains K7. Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and χ_ℓ(G)=6 if and only if G contains K6. They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that χ_ℓ(G)=5 if and only if G contains K5. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither K5 nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither K-5 (a K5 missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.