Towards Characterization of 5-List-Colorability of Toroidal Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916337446551552 |
|---|---|
| author | Dvořák, Zdeněk Peñarrubia, Félix Moreno |
| author_facet | Dvořák, Zdeněk Peñarrubia, Félix Moreno |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18800 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Characterization of 5-List-Colorability of Toroidal Graphs Dvořák, Zdeněk Peñarrubia, Félix Moreno Combinatorics Discrete Mathematics 05C10, 05C15, 68R10 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. |
| title | Towards Characterization of 5-List-Colorability of Toroidal Graphs |
| topic | Combinatorics Discrete Mathematics 05C10, 05C15, 68R10 |
| url | https://arxiv.org/abs/2407.18800 |