A decomposition of gallai multigraphs

Alexander Halperin; Colton Magnant; Kyle Pula

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 2, page 331-352
  • ISSN: 2083-5892

Abstract

top
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

How to cite

top

Alexander Halperin, Colton Magnant, and Kyle Pula. "A decomposition of gallai multigraphs." Discussiones Mathematicae Graph Theory 34.2 (2014): 331-352. <http://eudml.org/doc/267744>.

@article{AlexanderHalperin2014,
abstract = {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},
author = {Alexander Halperin, Colton Magnant, Kyle Pula},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; Gallai multigraph},
language = {eng},
number = {2},
pages = {331-352},
title = {A decomposition of gallai multigraphs},
url = {http://eudml.org/doc/267744},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Alexander Halperin
AU - Colton Magnant
AU - Kyle Pula
TI - A decomposition of gallai multigraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 2
SP - 331
EP - 352
AB - 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
LA - eng
KW - edge coloring; Gallai multigraph
UR - http://eudml.org/doc/267744
ER -

References

top
  1. [1] B. Alexeev, On lengths of rainbow cycles, Electron. J. Combin. 13(1) (2006) #105 
  2. [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[WoS][Crossref] Zbl1174.05041
  3. [3] A. Diwan and D. Mubayi, Turán’s theorem with colors, preprint, 2007. 
  4. [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. Zbl1196.05052
  5. [5] A. Frieze and M. Krivelevich, On rainbow trees and cycles, Electron. J. Combin. 15 (2008) #59. Zbl1159.05019
  6. [6] S. Fujita and C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory 70 (2012) 404-426. doi:10.1002/jgt.20622[Crossref] Zbl1247.05149
  7. [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[Crossref] 
  8. [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[Crossref][WoS] Zbl1231.05178
  9. [9] S. Fujita, C. Magnant and K. Ozeki. Rainbow generalizations of Ramsey theory: a survey, (2011) updated. http://math.georgiasouthern.edu/∼cmagnant Zbl1231.05178
  10. [10] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66. doi:10.1007/BF02020961[Crossref] 
  11. [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.[WoS] Zbl1209.05082
  12. [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[Crossref] Zbl1041.05028
  13. [13] P. Vojtěchovský, Periods in missing lengths of rainbow cycles, J. Graph Theory 61 (2009) 98-110. doi:10.1002/jgt.20371 [Crossref][WoS] Zbl1191.05047

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.