کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334295 | 690361 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fano colourings of cubic graphs and the Fulkerson Conjecture
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A Fano colouring is a colouring of the edges of a cubic graph by points of the Fano plane such that the colours of any three mutually adjacent edges form a line of the Fano plane. It has recently been shown by Holroyd and Å koviera [Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57-66] that a cubic graph has a Fano colouring if and only if it is bridgeless. In this paper we prove that six, and conjecture that four, lines of the Fano plane are sufficient to colour any bridgeless cubic graph. We establish connections of our conjecture to other conjectures concerning bridgeless cubic graphs, in particular to the well-known conjecture of Fulkerson about the existence of a double covering by 1-factors in every bridgeless cubic graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 112-120
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 112-120
نویسندگان
Edita MáÄajová, Martin Å koviera,