Counting Gallai 3-colorings of complete graphs

DOI10.1016/J.DISC.2019.05.015zbMATH Open1416.05098arXiv1805.06805OpenAlexW2963820491WikidataQ127750733 ScholiaQ127750733MaRDI QIDQ2312802FDOQ2312802

Authors: Josefran de Oliveira Bastos, F. S. Benevides, G. O. Mota, Ignasi Sau 

Publication date: 18 July 2019

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

Abstract: An edge coloring of the n-vertex complete graph K_n is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that the number of Gallai colorings of K_n with at most three colors is at most 7(n+1)*2^{n choose 2}, which improves the best known upper bound of frac{3}{2} * (n-1)! * 2^{(n-1) choose 2} in [Discrete Mathematics, 2017].

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

Recommendations

• The number of Gallai \(k\)-colorings of complete graphs
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Distribution of colors in Gallai colorings
• Remarks on the distribution of colors in Gallai colorings
• Extremal problems and results related to Gallai-colorings

zbMATH Keywords

countingcomplete graphsrainbow trianglesGallai colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Cites Work

• Hypergraph containers
• Independent sets in hypergraphs
• Transitiv orientierbare Graphen
• On the number of \(B_h\)-sets
• An extremal problem for random graphs and the number of graphs with large even-girth
• The number of \(C_{2\ell}\)-free graphs
• The number of \(K_{m,m}\)-free graphs
• Acyclic edge-coloring using entropy compression
• Counting sum-free sets in abelian groups
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• The number of the maximal triangle-free graphs
• The number of maximal sum-free subsets of integers
• A rainbow Erdős-Rothschild problem
• Title not available (Why is that?)
• Szemerédi’s Regularity Lemma for Sparse Graphs
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Edge colorings of complete graphs without tricolored triangles
• A note on perfect graphs
• Title not available (Why is that?)
• Gallai colorings of non-complete graphs
• Perfect couples of graphs
• Graph pairs and their entropies: Modularity problems
• Gallai-colorings of triples and 2-factors of \(\mathcal{B}_3\)
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• The number of subsets of integers with no \(k\)-term arithmetic progression

Cited In (10)

• Distribution of colors in Gallai colorings
• Gallai-colorings of triples and 2-factors of \(\mathcal{B}_3\)
• Density of Gallai multigraphs
• Remarks on an edge-coloring problem
• Edge colorings of complete graphs without tricolored triangles
• Rainbow Erdös-Rothschild problem for the Fano plane
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Complete edge-colored permutation graphs
• The number of Gallai \(k\)-colorings of complete graphs
• Remarks on the distribution of colors in Gallai colorings

This page was built for publication: Counting Gallai 3-colorings of complete graphs

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