The path-linked triangles 3-colourability conjecture

Let HH be a graph which is a disjoint union of triangles and paths of length at most 1212, and let GG be obtained from HH by gluing on vertex-disjoint triangles. For two triangles T,TT,T' in HH, say they are path-linked if there exists a glued-in triangle YY with TY,TYT\cap Y,T'\cap Y\neq\emptyset and the third vertex of YY lies on a path in GG of length at least two. Path-linked triangles conjecture. If every HH-triangle in GG is path-linked to at most one other HH-triangle, then GG 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 HH-paths have length at most 22 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.