The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

DOI10.1017/S0305004116001031MaRDI QIDQ5360466zbMATH OpenFDO

Authors Oleg Pikhurko, Katherine Staden, Zelealem B. Yilma

Publication date 28 September 2017

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

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

zbMATH Keywords

stability theorem for complete multipartite graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $mathbfk:=(k_1,dots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;mathbfk)$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $cin1,dots,s$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbfk)$ to denote the maximum of $F(G;mathbfk)$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every $mathbfk$ and $n$, there is a complete multipartite graph $G$ on $n$ vertices with $F(G;mathbfk)=F(n;mathbfk)$. Also, for every $mathbfk$ we construct a finite optimisation problem whose maximum is equal to the limit of $lo{g}_{2}F(n;mathbfk)/nchoose2$ as $n$ tends to infinity. Our final result is a stability theorem for complete multipartite graphs $G$, describing the asymptotic structure of such $G$ with $F(G;mathbfk)=F(n;mathbfk)cdot{2}^{o(n^2)}$ in terms of solutions to the optimisation problem.

Recommendations

• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Edge colourings of graphs avoiding monochromatic matchings of a given size
• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture
• Vertex colourings of multigraphs with forbiddances on edges
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• The Erdős-Hadwiger problem and the chromatic numbers of finite geometric graphs
• Edge-Coloring Problems for Graphs.
• An Erdős-Gallai type theorem for vertex colored graphs

Cites work

• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 554066 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 881297 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A coloring problem for intersecting vector spaces
• A remark on the number of edge colorings of graphs
• A structural result for hypergraphs with many restricted edge colorings
• Edge colourings of graphs avoiding monochromatic matchings of a given size
• Edge-colorings avoiding a fixed matching with a prescribed color pattern
• Edge-colorings avoiding fixed rainbow stars
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
• Kneser colorings of uniform hypergraphs
• On colourings of hypergraphs without monochromatic Fano planes
• Set-coloring of edges and multigraph Ramsey numbers
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• The number of oriantations having no fixed tournament

Cited in

(22)

• Counting Gallai 3-colorings of complete graphs
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Remarks on an edge-coloring problem
• Counting H-free orientations of graphs
• Improved bound on the maximum number of clique-free colorings with two and three colors
• Colourings without monochromatic disjoint pairs
• An extension of the rainbow Erdős-Rothschild problem
• Colouring set families without monochromatic \(k\)-chains
• On two problems in Ramsey-Turán theory
• On graphs with linear Ramsey numbers
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• Exact solutions to the Erdős-Rothschild problem
• Rainbow Erdös-Rothschild problem for the Fano plane
• Maximum number of triangle-free edge colourings with five and six colours
• The number of Gallai k-colorings of complete graphs
• Counting orientations of graphs with no strongly connected tournaments
• A rainbow Erdős-Rothschild problem
• On the maximum number of integer colourings with forbidden monochromatic sums
• Stability for the Erdős-Rothschild problem
• Edge colorings of graphs without monochromatic stars
• A rainbow Erdös-Rothschild problem
• On graphs with a large number of edge-colorings avoiding a rainbow triangle

This page was built for publication: The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

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