The Typical Structure of Gallai Colorings and Their Extremal Graphs

DOI10.1137/19M1253344zbMath1428.05094arXiv1812.07747OpenAlexW2994143791MaRDI QIDQ5204070

Lina Li, József Balogh

Publication date: 9 December 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.07747

zbMATH Keywords

extremal graphcontainer methodGallai coloring

Mathematics Subject Classification ID

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

Related Items

Remarks on an edge-coloring problem ⋮ Integer colorings with no rainbow 3-term arithmetic progression ⋮ Integer colorings with no rainbow \(k\)-term arithmetic progression ⋮ Complete edge-colored permutation graphs ⋮ Counting orientations of graphs with no strongly connected tournaments ⋮ Integer colorings with forbidden rainbow sums ⋮ Edge-colorings avoiding patterns in a triangle ⋮ Graphs with many edge-colorings such that complete graphs are rainbow ⋮ Extremal problems and results related to Gallai-colorings ⋮ Distribution of colors in Gallai colorings ⋮ An extension of the rainbow Erdős-Rothschild problem ⋮ Rainbow Erdös--Rothschild Problem for the Fano Plane ⋮ The number of Gallai \(k\)-colorings of complete graphs ⋮ Remarks on the distribution of colors in Gallai colorings

Cites Work

• Unnamed Item
• Unnamed Item
• A rainbow Erdős-Rothschild problem
• Hypergraph containers
• Recent trends in combinatorics
• The typical structure of graphs with no large cliques
• Gallai colorings of non-complete graphs
• A note on perfect graphs
• Books in graphs
• The number of graphs without forbidden subgraphs
• The Erdős-Hajnal conjecture for rainbow triangles
• Counting Gallai 3-colorings of complete graphs
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Ramsey-type results for Gallai colorings
• Edge colorings of complete graphs without tricolored triangles
• A Rainbow Erdös--Rothschild Problem
• On the number of points in general position in the plane
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• THE METHOD OF HYPERGRAPH CONTAINERS
• Multicolor containers, extremal entropy, and counting
• Independent sets in hypergraphs
• Large Subgraphs in Rainbow‐Triangle Free Colorings
• Transitiv orientierbare Graphen
• Graph pairs and their entropies: Modularity problems