Towards Characterization of 5-List-Colorability of Toroidal Graphs
Z Dvořák, FM Peñarrubia - arXiv preprint arXiv:2407.18800, 2024 - arxiv.org
Z Dvořák, FM Peñarrubia
arXiv preprint arXiv:2407.18800, 2024•arxiv.orgThrough computer-assisted enumeration, we list minimal obstructions for 5-choosability of
graphs on the torus with the following additional property: There exists a cyclic system of non-
contractible triangles around the torus where the consecutive triangles are at distance at
most four. This condition is satisfied by all previously known obstructions, and we verify that
there are no additional obstructions with this property. This supports the conjecture that a
toroidal graph is 5-choosable if and only if it is 5-colorable.
graphs on the torus with the following additional property: There exists a cyclic system of non-
contractible triangles around the torus where the consecutive triangles are at distance at
most four. This condition is satisfied by all previously known obstructions, and we verify that
there are no additional obstructions with this property. This supports the conjecture that a
toroidal graph is 5-choosable if and only if it is 5-colorable.
Through computer-assisted enumeration, we list minimal obstructions for 5-choosability of graphs on the torus with the following additional property: There exists a cyclic system of non-contractible triangles around the torus where the consecutive triangles are at distance at most four. This condition is satisfied by all previously known obstructions, and we verify that there are no additional obstructions with this property. This supports the conjecture that a toroidal graph is 5-choosable if and only if it is 5-colorable.
arxiv.org