The path-linked triangles 3-colourability conjecture
The path-linked triangles 3-colourability conjecture
Let be a graph which is a disjoint union of triangles and paths of length at most , and let be obtained from by gluing on vertex-disjoint triangles. For two triangles in , say they are path-linked if there exists a glued-in triangle with and the third vertex of lies on a path in of length at least two. Path-linked triangles conjecture. If every -triangle in is path-linked to at most one other -triangle, then is 3-colourable.
The restrictions are intended to avoid the known obstructions arising from more general unions of paths and triangles; the case where all -paths have length at most follows from an auxiliary bipartite-graph argument. The conjecture is presented as approachable, but remains open in the source.
Sources & referencesView supporting material
Primary source
Aseem Dalal, Jessica McDonald and Songling Shan, “A reduction of the "cycles plus K_4's" problem”, arXiv:2406.17723 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.