×

zbMATH — the first resource for mathematics

Uniquely edge colourable graphs. (English) Zbl 0599.05023
The aim of this paper is to extend known results concerning the (finite simple) uniquely edge colourable graphs into further classes of graphs. All finite uniquely k-edge colourable graphs (including multigraphs) with \(4\leq k<\aleph_ 0\) are constructed and enumerated. Similarly, all uniquely k-edge colourable graphs with \(k\geq \aleph_ 0\) are described. Cases \(k<3\) and \(k=3\) are considered as well. The results were presented in the author’s paper in Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner Texte Math. 59, 17-22 (1983; Zbl 0538.05035).
MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] BOLLOBÁS B.: Extremal graph theory. Academic Press, London 1978. · Zbl 1099.05044
[2] BOSÁK J.: Hamiltonian lines in cubic graphs. Théorie des graphes (Proc. Symp. Rome 1966). Dunod, Paris 1967, 35-46.
[3] BOSÁK J.: Enumeration of uniquely edge colourable multigraphs. Graphs and other combinatorial topics (Proc. Symp. Prague 1982). Teubner, Leipzig 1984, to appear. · Zbl 0538.05035
[4] COMTET L.: Analyse combinatoire. I. Press Univ. de France, Paris 1970.
[5] FIORINI S.: On the chromatic index of a graph. III. Uniwuely edge-colourable graphs. Ouart. J. Math. Oxford (3), 26, 1975, 129-140. · Zbl 0312.05104
[6] FIORINI S.: Un grafo cubico, non-planare, unicamente tricolorabile, di vita 5. Calcolo 13, 1976, 105-108. · Zbl 0339.05104
[7] FIORINI S., WILSON R. J.: Edge colourings of graphs. Pitman, London 1977. · Zbl 0421.05023
[8] GREENWELL D. L., KRONK H. V.: Uniquely line colorable graphs. Canad. Math. Bull. 16 (4), 1973, 525-529. · Zbl 0275.05107
[9] HALL M., Jr.: Combinatorial theory. Blaisdell, Waltham, Mass. 1967. · Zbl 0196.02401
[10] IZBICKI H.: Zulässige Kantenfärbungen von pseudo-regulären Graphen 3. Grades mit der Kantenfarbenzahl 3. Monatsh. Math. 66, 1962, 424-430. · Zbl 0106.16803
[11] IZBICKI H.: Zulässige Kantenfärbungen von pseudo-regulären Graphen mit minimalen Kanten-farbenzahl. Monatsh. Math. 67, 1963, 25-31. · Zbl 0113.17405
[12] NINČÁK J.: Hamiltonian circuits in cubic graphs. Comm. Math. Univ. Carol. 15, 1974, 627-630. · Zbl 0294.05118
[13] THOMASON A. G.: Hamiltonian cycles and uniquely edge colourable graphs. Advances in Graph Theory, Ann. Discr. Math. 3. North-Holland, Amsterdam 1978, 259-268. · Zbl 0382.05039
[14] THOMASON A. G.: Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable. J. Graph Theory 6, 1982, 219-221. · Zbl 0495.05025
[15] TUTTE W. T.: Hamiltonian circuits. Colloquio Internazionale sulle Teorie Combinatoire, Atti Convegni Lincei 17. Accad. Naz. Lincei, Roma 1976, 193-199. · Zbl 0347.05110
[16] WILSON R. J.: Problem 2. Proc. Fifth British Cornbinatorial Conf. Utilitas Math., Winnipeg 1976, 696.
[17] WILSON R. J.: Edge-colourings of graphs - a survey. Theory and applications of graphs (Proc. Conf. Kalamazoo 1976). Springer, Berlin 1978, 608-619.
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.