Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks. (English) Zbl 1157.05041
Summary: We show that the conjectures by M.M. Matthews and D.P. Sumner [J. Graph Theory 9, 269–277 (1985; Zbl 0591.05041)] (every 4-connected claw-free graph is Hamiltonian), by C.Thomassen [J. Graph Theory 10, 309–324 (1986; Zbl 0614.05050)] (every 4-connected line graph is Hamiltonian) and by H. Fleischner and B. Jackson [Ann. Discrete Math. 41, 171–177 (1989; Zbl 0677.05054)] (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.
We use a refinement of the contractibility technique which was introduced by Z. Ryjáček and R.H. Schelp in [J. Graph Theory 43, No.1, 37–48 (2003; Zbl 1018.05099)] as a common generalization and strengthening of the reduction techniques by P.A. Catlin [J. Graph Theory 12, No.1, 29–44 (1988; Zbl 0659.05073)] and Veldman and of the closure concept introduced by Z. Ryjáček in [J. Comb. Theory, Ser. B 70, No.2, 217–224 (1997; Zbl 0872.05032)].
We use a refinement of the contractibility technique which was introduced by Z. Ryjáček and R.H. Schelp in [J. Graph Theory 43, No.1, 37–48 (2003; Zbl 1018.05099)] as a common generalization and strengthening of the reduction techniques by P.A. Catlin [J. Graph Theory 12, No.1, 29–44 (1988; Zbl 0659.05073)] and Veldman and of the closure concept introduced by Z. Ryjáček in [J. Comb. Theory, Ser. B 70, No.2, 217–224 (1997; Zbl 0872.05032)].
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C38 | Paths and cycles |
Citations:
Zbl 0591.05041; Zbl 0614.05050; Zbl 0677.05054; Zbl 1018.05099; Zbl 0659.05073; Zbl 0872.05032References:
| [1] | Beineke, L. W., Characterizations of derived graphs, J. Combin. Theory Ser. B, 9, 129-135 (1970) · Zbl 0202.55702 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London, Elsevier, New York · Zbl 1134.05001 |
| [3] | Catlin, P. A., A reduction technique to find spanning eulerian subgraphs, J. Graph Theory, 12, 29-44 (1988) · Zbl 0659.05073 |
| [4] | Fleischner, H., Cycle decompositions, 2-coverings, removable cycles and the four-color disease, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press: Academic Press New York), 233-246 · Zbl 0556.05047 |
| [5] | Fleischner, H.; Jackson, B., A note concerning some conjectures on cyclically 4-edge-connected 3-regular graphs, (Andersen, L. D.; Jakobsen, I. T.; Thomassen, C.; Toft, B.; Vestergaard, P. D., Graph Theory in Memory of G.A. Dirac. Graph Theory in Memory of G.A. Dirac, Annals of Discrete Math., vol. 41 (1989), North-Holland: North-Holland Amsterdam), 171-177 · Zbl 0677.05054 |
| [6] | Harary, F.; Nash-Williams, C. St. J.A., On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull., 8, 701-709 (1965) · Zbl 0136.44704 |
| [7] | Kochol, M., Equivalence of Fleischner’s and Thomassen’s conjectures, J. Combin. Theory Ser. B, 78, 277-279 (2000) · Zbl 1027.05058 |
| [8] | Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1, 3}\)-free graphs, J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047 |
| [9] | Nedela, R.; Škoviera, M., Decompositions and reductions of snarks, J. Graph Theory, 22, 253-279 (1996) · Zbl 0856.05082 |
| [10] | Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B, 70, 217-224 (1997) · Zbl 0872.05032 |
| [11] | Ryjáček, Z.; Schelp, R. H., Contractibility techniques as a closure concept, J. Graph Theory, 43, 37-48 (2003) · Zbl 1018.05099 |
| [12] | Thomassen, C., Reflections on graph theory, J. Graph Theory, 10, 309-324 (1986) · Zbl 0614.05050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
