×

Properly coloured Hamiltonian paths in edge-coloured complete graphs. (English) Zbl 0897.05037

Authors’ abstract: We consider edge-coloured complete graphs. A path or cycle \(Q\) is called properly coloured (PC) if any two adjacent edges of \(Q\) differ in colour. Our note is inspired by the following conjecture by B. Bollobás and P. Erdős [Israel J. Math. 23, 126-131 (1976; Zbl 0325.05114)]: if \(G\) is an edge-coloured complete graph on \(n\) vertices in which the maximum monochromatic degree of every vertex is less than \(\lfloor n/2 \rfloor\), then \(G\) contains a PC Hamiltonian cycle. We prove that if an edge-coloured complete graph contains a PC 2-factor then it has a PC Hamiltonian path. R. Häggkvist (1996) announced that every edge-coloured complete graph satisfying the Bollobás-Erdős condition contains a PC 2-factor. These two results imply that every edge-coloured complete graph satisfying the Bollobás-Erdős condition has a PC Hamiltonian path.

MSC:

05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 0325.05114
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alon, N.; Gutin, G., Properly colored Hamilton cycles in edge colored complete graphs, Random Structures and Algorithms, 25, 277-286 (1997) · Zbl 0882.05084
[2] Bang-Jensen, J.; Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: A survey, Discrete Math., 165-166, 39-60 (1997) · Zbl 0876.05057
[3] O. Barr, Properly coloured Hamiltonian paths in edge-coloured complete graphs without monochromatic triangles, Ars Combinatoria, to appear.; O. Barr, Properly coloured Hamiltonian paths in edge-coloured complete graphs without monochromatic triangles, Ars Combinatoria, to appear. · Zbl 0963.05051
[4] Bollobás, B.; Erdós, P., Alternating Hamiltonian cycles, Israel J. Math., 23, 126-131 (1976) · Zbl 0325.05114
[5] Chen, C. C.; Daykin, D. E., Graphs with Hamiltonian cycles having adjacent lines different colors, J. Combin. Theory Ser., B 21, 135-139 (1976) · Zbl 0287.05106
[6] Chow, W. S.; Manoussakis, Y.; Megalakaki, O.; Spyratos, M.; Tuza, Z., Paths through fixed vertices in edge-colored graphs, Preprint U. de Paris-Sud, Orsay, L.R.I., no. 836 (1993) · Zbl 0826.68064
[7] Dorninger, D., On permutations of chromosomes, (Contributions to General Algebra, Vol. 5 (1987), Hölder-Pichler-Tempsky, Wien and Teubner: Hölder-Pichler-Tempsky, Wien and Teubner Stuttgart), 95-103 · Zbl 0643.92012
[8] Dorninger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 159-168 (1994) · Zbl 0823.92010
[9] Dorninger, D.; Timischl, W., Geometrical constraints on Bennett’s predictions of chromosome order, Heredity, 58, 321-325 (1987)
[10] Häggkvist, R., (Talk at International Colloquium on Combinatorics and Graph Theory at Balatonlelle. Talk at International Colloquium on Combinatorics and Graph Theory at Balatonlelle, Hungary (July 15-19, 1996))
[11] Shearer, J., A property of the colored complete graph, Discrete Math., 25, 175-178 (1979) · Zbl 0397.05024
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.