Density of Gallai multigraphs

MaRDI QIDQ2256125zbMATH OpenFDO

Authors Colton Magnant

Publication date 19 February 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p28

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Gallai coloringmultigraphrainbow triangle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

Summary: \textit{A. Diwan} and \textit{D. Mubayi} asked how many edges of each color could be included in a 3-edge-colored multigraph containing no rainbow triangle [``Turán's theorem with colors, Preprint (2006), \url{http: //www.math.cmu.edu/~mubayi/papers/webturan.pdf}]. We answer this question under the modest assumption that the multigraphs in question contain at least one edge between every pair of vertices. We also conjecture that this assumption is, in fact, without loss of generality.

Recommendations

• Distribution of colors in Gallai colorings
• Counting Gallai 3-colorings of complete graphs
• A decomposition of Gallai multigraphs
• Rainbow triangles and cliques in edge-colored graphs
• Edge colorings of complete graphs without tricolored triangles

Cites work

• A decomposition of Gallai multigraphs
• Transitiv orientierbare Graphen

Cited in

(7)

• From one to many rainbow Hamiltonian cycles
• On a rainbow version of Dirac's theorem
• Graphs without a Rainbow Path of Length 3
• Spectral radius and rainbow k-factors of graphs
• Directed graphs without rainbow triangles
• Directed graphs without rainbow triangles (extended abstract)
• Graphs without a rainbow path of length 3 (extended abstract)

This page was built for publication: Density of Gallai multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256125)