A reduction of the 'cycles plus $K_4$'s' problem

التفاصيل البيبلوغرافية
العنوان: A reduction of the 'cycles plus $K_4$'s' problem
المؤلفون: Dalal, Aseem, McDonald, Jessica, Shan, Songling
سنة النشر: 2024
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - 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.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2406.17723
رقم الأكسشن: edsarx.2406.17723
قاعدة البيانات: arXiv