Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T17:07:15.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Excluding Minors in Cubic Graphs

Published online by Cambridge University Press:  12 September 2008

K. Kilakos  and
B. Shepherd
K. Kilakos
Affiliation:
Centre for Discrete and Applicable Mathematics, London School of Economics, London, UK
B. Shepherd
Affiliation:
Centre for Discrete and Applicable Mathematics, London School of Economics, London, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

Let P10\e be the graph obtained by deleting an edge from the Petersen graph. We give a decomposition theorem for cubic graphs with no minor isomorphic to P10\e. The decomposition is used to show that graphs in this class are 3-edge-colourable. We also consider an application to a conjecture due to Grötzsch which states that a planar graph is 3-edge-colourable if and only if it is fractionally 3-edge-colourable.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 1 , March 1996 , pp. 57 - 78
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alspach, B., Goddyn, L. A. and Zhang, C. Q. (1996) Graphs with the circuit cover property. Submitted.Google Scholar
[2]Appel, K. and Haken, W. (1977) Every planar map is four-colourable, part I: discharging, Illinois J. Math. 21 429–490.Google Scholar
[3]Appel, K., Haken, W. and Koch, J. (1977) Every planar map is four-colourable, part II: reducibility. Illinois J. Math. 21 491–567.Google Scholar
[4]Edmonds, J. (1965) Maximum matching and a polyhedron with (0,1) vertices. J. Res. Nat. Bur. Standards Sect. B, 69B 125–130.Google Scholar
[5]Ellingham, M. N. (1984) Petersen subdivisions in some regular graphs. Congressus Numerantium 44 33–40.Google Scholar
[6]Fontet, M. (1978) Graphes 4-essentiels. C.R. Acad. Sci. Paris t287 289–290.Google Scholar
[7]Goddyn, L. A. (1996) Cones, lattices and Hilbert bases of circuits and perfect matchings. Contemporary Mathematics (to appear).Google Scholar
[8]Holyer, I. (1981) The NP-completeness of edge-colouring. SIAM J. Computing 10 718–720.CrossRefGoogle Scholar
[9]Kelmans, A. K. (1986) On 3-connected graphs without essential 3-cuts or triangles. Soviet Math. Dokl. 33(3) 698–703.Google Scholar
[10]Lovász, L. (1987) Matching structure and the matching lattice. J. Combinatorial Theory (B) 43 187–222.CrossRefGoogle Scholar
[11]Seymour, P. D. (1979) On multi-colourings of cubic graphs and conjectures of Fulkerson and Tutte. Proc. London Math. Society (3) 38 423–460.CrossRefGoogle Scholar
[12]Seymour, P. D. (1981) On Tutte's extension of the four-colour problem. J. Combinatorial Theory (B) 31 82–94.CrossRefGoogle Scholar
[13]Tait, P. G. (1880) Remarks on the colouring of maps. Proc. Royal Soc. Edinburgh, Ser. A 10 729.Google Scholar
[14]Tutte, W. T. (1966) On the algebraic theory of graph colourings. J. Combinatorial Theory (B) 23 15–50.CrossRefGoogle Scholar
[15]Wagner, K. (1937) Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 570–590.CrossRefGoogle Scholar
[16]Wormald, N. C. (1979) Classifying k-connected cubic graphs. Lecture Notes in Mathematics 748. Springer Verlag, 199–206.Google Scholar