×

Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles. (English) Zbl 1416.05102

Summary: In an edge-colored graph \((G, c)\), let \(d^c(v)\) be the number of colors on the edges incident to vertex \(v\) and let \(\delta^c(G)\) be the minimum value of \(d^c(v)\) over all vertices \(v \in V(G)\). A cycle of \((G, c)\) is called proper if any two adjacent edges of the cycle have distinct colors. An edge-colored graph \((G, c)\) on \(n \geq 3\) vertices is called properly vertex-pancyclic if each vertex of \((G, c)\) is contained in a proper cycle of length \(l\) for every \(l\) with \(3 \leq l \leq n\). S. Fujita and C. Magnant [ibid. 159, No. 14, 1391–1397 (2011; Zbl 1228.05150)] conjectured that every edge-colored complete graph on \(n \geq 3\) vertices with \(\delta^c(G) \geq \frac{n + 1}{2}\) is properly vertex-pancyclic. We show that this conjecture is true if the edge-colored complete graph has no monochromatic triangles.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles

Citations:

Zbl 1228.05150
Full Text: DOI

References:

[1] Alon, N.; Gutin, G., Properly colored Hamilton cycles in edge-colored complete graphs, Random Struct. Algorithms, 11, 179-186 (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] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (Springer Monographs in Mathematics (2009), Springer-Verlag, London Ltd.: Springer-Verlag, London Ltd. London) · Zbl 1170.05002
[4] Chartrand, G.; Lesniak, L., Graphs & Digraphs (2005), Chapman & Hall: Chapman & Hall CRC, Boca Raton, FL · Zbl 1057.05001
[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] Chou, W. S.; Manoussakis, Y.; Megalakaki, O.; Spyratos, M.; Zs. Tuza, Paths through fixed vertices in edge-colored graphs, Math. Inform. Sci. Humaines, 127, 49-58 (1994) · Zbl 0826.68064
[7] Daykin, D. E., Graphs with cycles having adjacent lines of different colors, J. Combin. Theory Ser. B, 20, 149-152 (1976) · Zbl 0316.05106
[8] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[9] Dorninger, D., On Permutations of Chromosomes, Contributions To General Algebra, 5 (Salzburg, 1986), 95-103 (1987), Hölder-Pichler-Tempsky: Hölder-Pichler-Tempsky Vienna · Zbl 0643.92012
[10] Dorninger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 159-168 (1994) · Zbl 0823.92010
[11] Dorninger, D.; Timischl, W., Geometrical constraints on Bennett’s predictions of chromosome order, Heredity, 58, 321-325 (1987)
[12] Fujita, S.; Li, R.; Zhang, S., Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs, J. Graph Theory, 87, 362-373 (2018) · Zbl 1386.05057
[13] Fujita, S.; Magnant, C., Properly colored paths and cycles, Discrete Appl. Math., 159, 1391-1397 (2011) · Zbl 1228.05150
[14] Gyárfás, A.; Simony, G., Edge colorings of complete graphs without tricolored triangles, J. Graph Theory, 46, 211-216 (2004) · Zbl 1041.05028
[15] Li, H., Rainbow \(C_3\)’s and \(C_4\)’s in edge-colored graphs, Discrete Math., 313, 1893-1896 (2013) · Zbl 1277.05065
[16] Li, R.; Broersma, H.; Zhang, S., Properly edge-colored theta graphs in edge-colored complete graphs, Graphs Combin., 35, 261-286 (2019) · Zbl 1407.05097
[17] Li, B.; Ning, B.; Xu, C.; Zhang, S., Rainbow triangles in edge-colored graphs, European J. Combin., 36, 453-459 (2014) · Zbl 1284.05103
[18] Li, R.; Ning, B.; Zhang, S., Color degree sum conditions for rainbow triangles in edge-colored graphs, Graphs Combin., 32, 2001-2008 (2016) · Zbl 1349.05112
[19] Lo, A., A Dirac type condition for properly colored paths and cycles, J. Graph Theory, 76, 60-87 (2014) · Zbl 1294.05077
[20] Lo, A., An edge-colored version of Dirac’s theorem, SIAM J. Discrete Math., 28, 18-36 (2014) · Zbl 1297.05085
[21] Shearer, J., A property of the colored complete graph, Discrete Math., 25, 175-178 (1979) · Zbl 0397.05024
[22] Wang, G.; Li, H., Color degree and alternating cycles in edge-colored graphs, Discrete Math., 309, 4349-4354 (2009) · Zbl 1198.05070
[23] Wang, G.; Wang, T.; Liu, G., Long properly colored cycles in edge colored complete graphs, Discrete Math., 324, 56-61 (2014) · Zbl 1285.05070
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.