Perfect matchings with restricted intersection in cubic graphs

被引：11

作者：

Kaiser, Tomas ^{[1
,2
]}

Raspaud, Andre ^{[3
]}

机构：

[1] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic

[2] Univ W Bohemia, Inst Theoret Comp Sci, Plzen 30614, Czech Republic

[3] Univ Bordeaux 1, LaBRI, F-33405 Talence, France

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2010年 / 31卷 / 05期

关键词：

D O I：

10.1016/j.ejc.2009.11.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A conjecture of G. Fan and A. Raspaud asserts that every bridgeless cubic graph contains three perfect matchings with empty intersection. We propose a possible approach to this and similar problems, based on the concept of a balanced join in an embedded graph. We use this method to prove that bridgeless cubic graphs of oddness two have Fano colorings using only five lines of the Fano plane. This is a special case of a conjecture by E. Macajova and M. Skoviera. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：1307 / 1315

页数：9

共 11 条

[1]

Diestel R., 2000, Graph Theory

[2] FULKERSON CONJECTURE AND CIRCUIT COVERS [J].

FAN, GH ;

RASPAUD, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 61 (01) :133-138

[3] COMMON BASIS FOR THEORY OF EULERIAN GRAPHS AND THEOREM OF PETERSEN [J].

FLEISCHNER, H .

MONATSHEFTE FUR MATHEMATIK, 1976, 81 (04) :267-278

[4]

Fulkerson D., 1971, MATH PROGRAM, V1, P168, DOI [10.1007/BF01584085, DOI 10.1007/BF01584085]

[5]

Grtzsch H., 1959, WISS Z M LUTHER U HA, V8, P109

[6] Colouring of cubic graphs by Steiner triple systems [J].

Holroyd, F ;

Skoviera, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 91 (01) :57-66

[7] Fano colourings of cubic graphs and the Fulkerson Conjecture [J].

Mácajová, E ;

Skoviera, M .

THEORETICAL COMPUTER SCIENCE, 2005, 349 (01) :112-120

[8]

MACAJOVA E, 2009, ELECT NOTES DISCRETE, V34, P237

[9]

MACAJOVA E, 2009, TR2009020 COM U

[10]

Mohar B., 2001, JH STUD MATH SCI, DOI 10.56021/9780801866890

← 1 2 →