Answers are grounded in this paper and cite their sources.
This analysis demonstrates multiple improper colorability levels in toroidal graphs, suggesting new insights into their structure.
A graph G is called (d₁,,dₖ)-colorable if its vertices can be partitioned into k sets V₁,,Vₖ such that Δ( VᵢG)≤ dᵢ, i∈ \1,, k\. If d₁ = = dₖ = m we say that G is k-colorable with defect m. A coloring with at least one dᵢ, 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 K₇ and T₁₁ are $(0,0,0,1)$-colorable. Finally, we discuss the colorability of graphs embeddable on N₁ and show that they are $(0,0,0,2)$-colorable.
No takes yet. Share an insight, caveat, or question.
Kolačkovská et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: