A decomposition of Gallai multigraphs
| Autor: | Colton Magnant, Kyle Pula, Alexander Halperin |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Mathematics::Combinatorics Erdős–Gallai theorem Applied Mathematics Rainbow Computer Science::Computational Complexity Computer Science::Computational Geometry Graph Combinatorics Edge coloring Computer Science::Discrete Mathematics QA1-939 gallai multigraph Discrete Mathematics and Combinatorics edge coloring Mathematics |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 34, Iss 2, Pp 331-352 (2014) |
| ISSN: | 2083-5892 1234-3099 |
| DOI: | 10.7151/dmgt.1740 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|