Counting Gallai 3-colorings of complete graphs

DOI10.1016/J.DISC.2019.05.015MaRDI QIDQ2312802zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

countingcomplete graphsrainbow trianglesGallai colorings

Mathematics Subject Classification ID

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

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].

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

Cites work

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

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
• The number of Gallai k-colorings of complete graphs
• Complete edge-colored permutation 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)