A reduction of the "cycles plus $K_4$'s" problem
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_ | 1866916300137168896 |
|---|---|
| author | Dalal, Aseem McDonald, Jessica Shan, Songling |
| author_facet | Dalal, Aseem McDonald, Jessica Shan, Songling |
| contents | Let $H$ be a 2-regular graph and let $G$ be obtained from $H$ by gluing in vertex-disjoint copies of $K_4$. The "cycles plus $K_4$'s" problem is to show that $G$ is 4-colourable; this is a special case of the \emph{Strong Colouring Conjecture}. In this paper we reduce the "cycles plus $K_4$'s" problem to a specific 3-colourability problem. In the 3-colourability problem, vertex-disjoint triangles are glued (in a limited way) onto a disjoint union of triangles and paths of length at most 12, and we ask for 3-colourability of the resulting graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17723 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A reduction of the "cycles plus $K_4$'s" problem Dalal, Aseem McDonald, Jessica Shan, Songling Combinatorics 05C15 Let $H$ be a 2-regular graph and let $G$ be obtained from $H$ by gluing in vertex-disjoint copies of $K_4$. The "cycles plus $K_4$'s" problem is to show that $G$ is 4-colourable; this is a special case of the \emph{Strong Colouring Conjecture}. In this paper we reduce the "cycles plus $K_4$'s" problem to a specific 3-colourability problem. In the 3-colourability problem, vertex-disjoint triangles are glued (in a limited way) onto a disjoint union of triangles and paths of length at most 12, and we ask for 3-colourability of the resulting graph. |
| title | A reduction of the "cycles plus $K_4$'s" problem |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2406.17723 |