×

Maximum properly colored trees in edge-colored graphs. (English) Zbl 1498.90240

Summary: An edge-colored graph \(G\) is a graph with an edge coloring. We say \(G\) is properly colored if any two adjacent edges of \(G\) have distinct colors, and \(G\) is rainbow if any two edges of \(G\) have distinct colors. For a vertex \(v \in V(G)\), the color degree \(d_G^{col}(v)\) of \(v\) is the number of distinct colors appearing on edges incident with \(v\). The minimum color degree \(\delta^{col}(G)\) of \(G\) is the minimum \(d_G^{col}(v)\) over all vertices \(v \in V(G)\). In this paper, we study the relation between the order of maximum properly colored tree in \(G\) and the minimum color degree \(\delta^{col}(G)\) of \(G\). We obtain that for an edge-colored connected graph \(G\), the order of maximum properly colored tree is at least \(\min \{|G|, 2\delta^{col}(G)\}\), which generalizes the result of Y. Cheng et al. [Discrete Math. 343, No. 1, Article ID 111629, 6 p. (2020; Zbl 1429.05061)]. Moreover, the lower bound \(2\delta^{col}(G)\) in our result is sharp and we characterize all extremal graphs \(G\) with the maximum properly colored tree of order \(2\delta^{col}(G) \ne |G|\).

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1429.05061
Full Text: DOI

References:

[1] Akbari, S.; Alipour, A., Multicolored trees in complete graphs, J Graph Theory, 54, 221-232 (2006) · Zbl 1112.05034 · doi:10.1002/jgt.20204
[2] Alon, N.; Gutin, G., Properly colored Hamilton cycles in edge-colored complete graphs, Random Struct Algorithms, 11, 179-186 (1997) · Zbl 0882.05084 · doi:10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P
[3] Bang-Jensen, J.; Gutin, G.; Yeo, A., Properly coloured Hamiltonian paths in edge-coloured complete graphs, Discrete Appl Math, 82, 247-250 (1998) · Zbl 0897.05037 · doi:10.1016/S0166-218X(97)00062-0
[4] Bollobás, B.; Erdős, P., Alternating Hamiltonian cycles, Israel J Math, 23, 126-131 (1976) · Zbl 0325.05114 · doi:10.1007/BF02756791
[5] Borozan, V.; Fernandez de La Vega, W.; Manoussakis, Y.; Martinhon, C.; Muthu, R.; Pham, HP; Saad, R., Maximum colored trees in edge-colored graphs, Euro J Combin, 80, 296-310 (2019) · Zbl 1415.05049 · doi:10.1016/j.ejc.2018.02.027
[6] Brualdi, RA; Hollingsworth, S., Multicolored trees in complete graphs, J Combin Theory Ser B, 68, 310-313 (1996) · Zbl 0861.05020 · doi:10.1006/jctb.1996.0071
[7] Cheng, Y.; Kano, M.; Wang, G., Properly colored spanning trees in edge-colored graphs, Discrete Math, 343, 1, 111629 (2020) · Zbl 1429.05061 · doi:10.1016/j.disc.2019.111629
[8] Cheng, Y.; Sun, Q.; Tan, TS; Wang, G., Rainbow Hamiltonian cycles in strongly edge-colored graphs, Discrete Math, 342, 4, 1186-1190 (2019) · Zbl 1405.05094 · doi:10.1016/j.disc.2019.01.002
[9] Dirac, GA, Some theorems on abstract graphs, Proc London Math Soc, 2, 1, 69-81 (1952) · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
[10] Feng, J.; Giesen, H.; Guo, Y.; Gutin, G.; Jensen, T.; Rafiey, A., Characterization of edge-colored complete graphs with properly colored Hamilton paths, J Graph Theory, 53, 333-346 (2006) · Zbl 1125.05037 · doi:10.1002/jgt.20188
[11] Fujita, S.; Magnant, C., Properly colored paths and cycles, Discrete Appl Math, 159, 1391-1397 (2011) · Zbl 1228.05150 · doi:10.1016/j.dam.2011.06.005
[12] Horn, P., Rainbow spanning trees in complete graphs colored by one-factorizations, J Graph Theory, 87, 333-346 (2018) · Zbl 1386.05027 · doi:10.1002/jgt.22160
[13] Kano, M.; Li, X., Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey, Graphs Combin, 24, 237-263 (2008) · Zbl 1190.05045 · doi:10.1007/s00373-008-0789-5
[14] Kano, M.; Ozeki, K.; Suzuki, K.; Tsugaki, M.; Yamashita, T., Spanning \(k\)-trees of bipartite graphs, Electron J Combin, 22, 1, P1.13 (2015) · Zbl 1305.05046 · doi:10.37236/3628
[15] Li, H., Rainbow \(C^{\prime }_3\) s and \(C^{\prime }_4\) s in edge-colored graphs, Discrete Math, 313, 1893-1896 (2013) · Zbl 1277.05065 · doi:10.1016/j.disc.2012.11.024
[16] 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 · doi:10.1007/s00373-016-1690-2
[17] Li, H.; Wang, G., Color degree and heterochromatic cycles in edge-colored graphs, Euro J Combin, 33, 8, 1958-1964 (2012) · Zbl 1248.05071 · doi:10.1016/j.ejc.2012.06.005
[18] Lo, A., A Dirac type condition for properly coloured paths and cycles, J Graph Theory, 76, 60-87 (2014) · Zbl 1294.05077 · doi:10.1002/jgt.21751
[19] Lo, A., Properly colored Hamiltonian cycles in edge-colored complete graphs, Combinatorica, 36, 4, 471-492 (2016) · Zbl 1389.05043 · doi:10.1007/s00493-015-3067-1
[20] Lo, A., Long properly coloured cycles in edge-coloured graphs, J Graph Theory (2018) · Zbl 1507.05038 · doi:10.1002/jgt.22405
[21] Ore, O., Note on Hamilton circuits, Am Math Monthly, 67, 55 (1960) · Zbl 0089.39505 · doi:10.2307/2308928
[22] Suzuki, K., A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph, Graphs Combin, 22, 261-269 (2006) · Zbl 1099.05039 · doi:10.1007/s00373-006-0662-3
[23] Wang, G.; Li, H., Color degree and alternating cycles in edge-colored graphs, Discrete Math, 309, 4349-4354 (2009) · Zbl 1198.05070 · doi:10.1016/j.disc.2009.01.016
[24] Wang, G., Rainbow matchings in properly edge colored graphs, Electron J Combin, 18, P162 (2011) · Zbl 1230.05137 · doi:10.37236/649
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.