×

zbMATH — the first resource for mathematics

Hamiltonian weights and unique 3-edge-colorings of cubic graphs. (English) Zbl 0854.05070
A \((1, 2)\)-eulerian weight \(w\) of a 2-connected graph \(G\) is a weight \(w: E(G)\to \{1, 2\}\) such that the total weight of each edge-cut is even. A faithful cover of \(w\) is a family \(C\) of circuits such that each edge \(e\) is contained in precisely \(w(e)\) circuits of \(C\). A \((1, 2)\)-eulerian weight \(w\) of a graph is hamiltonian if every faithful cover of \(w\) is a set of two Hamilton circuits. A cubic graph is uniquely 3-edge-colorable if the graph has precisely one 1-factorization. The topic of faithful coverings is related to the circuit double cover conjecture and the topic of uniquely 3-edge-colorable cubic graphs is also an important subject in graph theory. Relation between the faithful coverings and the uniquely 3-edge-colorability of cubic graphs is studied in this paper and it is proved that if a 3-connected cubic graph \(G\) containing no subdivision of the Petersen graph admits a hamiltonian weight, then \(G\) is uniquely 3-edge-colorable.
Reviewer: H.Li (Orsay)

MSC:
05C45 Eulerian and Hamiltonian graphs
05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alspach, Discrete Math. 111 pp 11– (1993)
[2] Alspach, Trans. AMS. 344 pp 131– (1994)
[3] and , Graph Theory with Applications. Macmillan, London (1976). · Zbl 1226.05083
[4] and , Edge colourings of graphs. Selected Topics in Graph Theory. Academic Press, New York (1978) 103–126.
[5] Greenwell, Can. Math. Bull. 16 pp 525– (1973) · Zbl 0275.05107
[6] Goddyn, Contem. Math. 147 pp 419– (1993)
[7] On circuit covers, circuit decompositions and Euler tours of graphs. Surveys in Combinatorics, London Mathematics Society Lecture Note Series 187, Cambridge University Press, Cambridge (1993) 191–210. · Zbl 0791.05081
[8] Jaeger, Ann. Discrete Math. 27 pp 1– (1985)
[9] Nowhere-zero flow problem. Selected Topics in Graph Theory 3. Wiley, New York (1988) 71–95.
[10] and , Graph Colouring Problems, John Wiley & Sons, (1994).
[11] Sums of circuits. Graph Theory and Related Topics. Academic Press, New York (1979) 342–355.
[12] Szekeres, Bull. Austral. Math. Soc. 8 pp 367– (1973)
[13] Thomason, J. Graph Theory 6 pp 219– (1982)
[14] Thomason, Ann. Discrete Math. 3 pp 259– (1978)
[15] Tutte, J. London Math. Soc. 21 pp 98– (1946)
[16] Tutte, J. Combinat. Theory 1 pp 15– (1966)
[17] Hamiltonian circuits. Colloquio Internazional sulle Teorie combinatorics, Atti dei Convegni Lincei 17, Accad. Naz. Lindei, Roma 1 (1976) 193–199.
[18] Problem 2. Util. Math. (1976) 696.
[19] Zhang, Ann. Discrete Math. 55 pp 183– (1993)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.