The Typical Structure of Gallai Colorings and Their Extremal Graphs

DOI10.1137/19M1253344zbMATH Open1428.05094arXiv1812.07747OpenAlexW2994143791MaRDI QIDQ5204070FDOQ5204070

Authors: József Balogh, Lina Li 

Publication date: 9 December 2019

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

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.

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

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

zbMATH Keywords

extremal graphcontainer methodGallai coloring

Mathematics Subject Classification ID

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

Cites Work

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

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 forbidden rainbow sums
• Integer colorings with no rainbow 3-term arithmetic progression
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• Rainbow Erdös-Rothschild problem for the Fano plane
• Disconnected colors in generalized Gallai-colorings
• Edge-colorings avoiding patterns in a triangle
• Complete edge-colored permutation graphs
• Counting orientations of graphs with no strongly connected tournaments
• The number of Gallai \(k\)-colorings of complete graphs
• 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)