×

A decomposition of Gallai multigraphs. (English) Zbl 1290.05075

Summary: An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. Alexeev, On lengths of rainbow cycles, Electron. J. Combin. 13(1) (2006) #105; · Zbl 1111.05032
[2] R.N. Ball, A. Pultr and P. Vojtěchovský, Colored graphs without colorful cycles, Combinatorica 27 (2007) 407-427. doi:10.1007/s00493-007-2224-6; · Zbl 1174.05041
[3] A. Diwan and D. Mubayi, Turán’s theorem with colors, preprint, 2007.;
[4] R.J. Faudree, R. Gould, M. Jacobson and C. Magnant, Ramsey numbers in rainbow triangle free colorings, Australas. J. Combin. 46 (2010) 269-284.; · Zbl 1196.05052
[5] A. Frieze and M. Krivelevich, On rainbow trees and cycles, Electron. J. Combin. 15 (2008) #59.; · Zbl 1159.05019
[6] S. Fujita and C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory 70 (2012) 404-426. doi:10.1002/jgt.20622; · Zbl 1247.05149
[7] S. Fujita and C. Magnant, Gallai-Ramsey numbers for cycles, Discrete Math. 311 (2011) 1247-1254. doi:10.1016/j.disc.2009.11.004; · Zbl 1222.05186
[8] S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: a survey, Graphs Combin. 26 (2010) 1-30. doi:10.1007/s00373-010-0891-3; · Zbl 1231.05178
[9] S. Fujita, C. Magnant and K. Ozeki. Rainbow generalizations of Ramsey theory: a survey, (2011) updated. http://math.georgiasouthern.edu/∼cmagnant; · Zbl 1231.05178
[10] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66. doi:10.1007/BF02020961; · Zbl 0153.26002
[11] A. Gyárfás, G. Sárközy, A. Sebö and S. Selkow, Ramsey-type results for Gallai colorings, J. Graph Theory 64 (2010) 233-243.; · Zbl 1209.05082
[12] A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46 (2004) 211-216. doi:10.1002/jgt.20001; · Zbl 1041.05028
[13] P. Vojtěchovský, Periods in missing lengths of rainbow cycles, J. Graph Theory 61 (2009) 98-110. doi:10.1002/jgt.20371; · Zbl 1191.05047
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.