A (5,5)-Colouring of Kn with Few Colours

DOI10.1017/S0963548318000172MaRDI QIDQ4554774zbMATH OpenOpenAlexFDO

Authors Alex Cameron, Emily Heath

Publication date 9 November 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: For fixed integers $p$ and $q$, let $f(n,p,q)$ denote the minimum number of colors needed to color all of the edges of the complete graph $K_n$ such that no clique of $p$ vertices spans fewer than $q$ distinct colors. Any edge-coloring with this property is known as a $(p,q)$-coloring. We construct an explicit $(5,5)$-coloring that shows that $f(n,5,5)leq{n}^{1/3+o(1)}$ as $nightarrowinfty$. This improves upon the best known probabilistic upper bound of $Oleft(n^{1/2}ight)$ given by ErdH{o}s and Gy'{a}rf'{a}s, and comes close to matching the best known lower bound $Omegaleft(n^{1/3}ight)$.

Recommendations

• A Note on k-Colorability of P 5-Free Graphs
• The total coloring of \(K_5\)-minor-free graphs
• \([1,1,2]\)-colorings of \(K_5\) and \(K_6\).
• 5-coloring \(K_{3,k}\)-minor-free graphs
• An explicit edge-coloring of K_n with six colors on every K₅
• Five-coloring graphs on the Klein bottle
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• The edge colorings of \(K_5\)-minor free graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• On restricted colourings of \(K_ n\)

Cites work

• A dense infinite Sidon sequence
• A generalized Ramsey problem
• A variant of the classical Ramsey problem
• Almost-rainbow edge-colorings of some small subgraphs
• An explicit construction for a Ramsey problem
• Coloring triple systems with local conditions
• Edge-coloring cliques with many colors on subcliques
• Edge-coloring cliques with three colors on all 4-cliques
• scientific article; zbMATH DE number 3927021 (Why is no real title available?)
• scientific article; zbMATH DE number 3540832 (Why is no real title available?)
• The Erdős-Gyárfás problem on generalized Ramsey numbers

Cited in

(16)

• \(K_ 5\) is the only double-critical 5-chromatic graph
• Edge-coloring cliques with three colors on all 4-cliques
• An explicit edge-coloring of K_n with six colors on every K₅
• scientific article; zbMATH DE number 4070935 (Why is no real title available?)
• Essentially Infinite Colourings of Graphs
• The optimal drawings of \(K_{5,n}\)
• Almost-rainbow edge-colorings of some small subgraphs
• New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
• Edge-coloring cliques with many colors on subcliques
• Lower bounds on the Erdős–Gyárfás problem via color energy graphs
• New bounds on the generalized Ramsey number \(f(n, 5, 8)\)
• The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
• Growth rates of the bipartite Erdős-Gyárfás function
• Small Ramsey numbers for books, wheels, and generalizations
• Generalized Ramsey numbers of cycles, paths, and hypergraphs
• A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

This page was built for publication: A (5,5)-Colouring of K_n with Few Colours

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