2025/09/19 by Alexandra Kolačkovská, Mária Maceková, Kolačkovská, Alexandra +5
Computer Science · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2509.15870
openalex publication_date 2025/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called (d1,…,dk)-colorable if its vertices can be partitioned into k sets V1,…,Vk such that Δ(⟨ Vi⟩G)≤ di, i∈ \1,…, k\. If d1 = … = dk = m we say that G is k-colorable with defect m. A coloring with at least one di, i∈ \1,…, k\, greater than 0 is called an improper coloring. It is known that toroidal graphs are properly 7-colorable, therefore they are 7-colorable with defect 0. It was also proved that toroidal graphs are 5-colorable with defect 1 and 3-colorable with defect 2. The question whether they are 4-colorable with defect 1 remains open. In this paper we focus on improper coloring of toroidal graphs with values of defects being not all equal. We prove that these graphs are (0,0,0,0,0,1^*)-colorable, (0,0,0,0,2)-colorable and (0,0,0,1^*,1^*)-colorable (a star means that there is an improper coloring in which subgraph induced by the corresponding color class contains at most one edge). Choi and Esperet in [Improper coloring of graphs on surfaces, J. Graph Theory 91(1) (2019), 16-34] proved that every graph of Euler genus eg > 0 is (0, 0, 0, 9eg - 4)-colorable. From this result it follows that toroidal graphs are (0,0,0,14)-colorable. We decreased the value 14 and proved that toroidal graphs are (0,0,0,4)-colorable. We also show that all 6-regular toroidal graphs except K7 and T11 are (0,0,0,1)-colorable. Finally, we discuss the colorability of graphs embeddable on N1 and show that they are (0,0,0,2)-colorable.