Let H be a 2-regular graph and let G be obtained from H by gluing in vertex-disjoint copies of K₄. The "cycles plus K₄'s" problem is to show that G is 4-colourable; this is a special case of the Strong Colouring Conjecture. In this paper we reduce the "cycles plus K₄'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.
No takes yet. Share an insight, caveat, or question.
Dalal et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: