The Typical Structure of Gallai Colorings and Their Extremal Graphs

DOI10.1137/19M1253344MaRDI QIDQ5204070zbMATH OpenOpenAlexFDO

Authors József Balogh, Lina Li

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)

Abstract: An edge coloring of a graph $G$ is a Gallai coloring if it contains no rainbow triangle. We show that the number of Gallai $r$-colorings of $K_n$ is $$. This result indicates that almost all Gallai $r$-colorings of $K_n$ use only 2 colors. We also study the extremal behavior of Gallai $r$-colorings among all $n$-vertex graphs. We prove that the complete graph $K_n$ admits the largest number of Gallai $3$-colorings among all $n$-vertex graphs when $n$ is sufficiently large, while for $rgeq4$, it is the complete bipartite graph $K_{lfloorn/2floor,lceiln/2ceil}$. Our main approach is based on the hypergraph container method, developed independently by Balogh, Morris, and Samotij as well as by Saxton and Thomason, together with some stability results for containers.

Recommendations

• Extremal problems and results related to Gallai-colorings
• Extremal graphs in some coloring problems
• Gallai colorings of non-complete graphs
• On some extremal graph coloring problems of Nordhaus Gaddum class
• The number of Gallai k-colorings of complete graphs
• scientific article; zbMATH DE number 15467
• Gallai colorings and domination in multipartite digraphs
• Extremal restraints for graph colourings
• Structures and chromaticity of some extremal 3-colourable graphs
• On Some Extremal Properties of Hypergraph Colorings

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• A note on perfect graphs
• A rainbow Erdös-Rothschild problem
• A rainbow Erdős-Rothschild problem
• Books in graphs
• Counting Gallai 3-colorings of complete graphs
• Edge colorings of complete graphs without tricolored triangles
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Gallai colorings of non-complete graphs
• Graph pairs and their entropies: Modularity problems
• Hypergraph containers
• Independent sets in hypergraphs
• Large subgraphs in rainbow-triangle free colorings
• Multicolor containers, extremal entropy, and counting
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• On the number of points in general position in the plane
• Ramsey-type results for Gallai colorings
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The Erdős-Hajnal conjecture for rainbow triangles
• The method of hypergraph containers
• The number of graphs without forbidden subgraphs
• The typical structure of graphs with no large cliques
• Transitiv orientierbare Graphen

Cited in

(18)

• Distribution of colors in Gallai colorings
• Gallai-colorings of triples and 2-factors of \(\mathcal{B}_3\)
• Counting Gallai 3-colorings of complete graphs
• Remarks on an edge-coloring problem
• An extension of the rainbow Erdős-Rothschild problem
• Integer colorings with no rainbow 3-term arithmetic progression
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• Integer colorings with forbidden rainbow sums
• Rainbow Erdös-Rothschild problem for the Fano plane
• Disconnected colors in generalized Gallai-colorings
• Edge-colorings avoiding patterns in a triangle
• The number of Gallai k-colorings of complete graphs
• Complete edge-colored permutation graphs
• Counting orientations of graphs with no strongly connected tournaments
• Graphs with many edge-colorings such that complete graphs are rainbow
• Remarks on the distribution of colors in Gallai colorings
• A decomposition of Gallai multigraphs
• Extremal problems and results related to Gallai-colorings

This page was built for publication: The Typical Structure of Gallai Colorings and Their Extremal Graphs

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