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

DOI10.1017/S0305004116001031zbMATH Open1371.05095arXiv1605.05074MaRDI QIDQ5360466FDOQ5360466

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)

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.

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

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

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)

Cites Work

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

Cited In (22)

• Counting Gallai 3-colorings of complete graphs
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Counting H-free orientations of graphs
• Remarks on an edge-coloring problem
• 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
• On two problems in Ramsey-Turán theory
• Colouring set families without monochromatic \(k\)-chains
• 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
• Counting orientations of graphs with no strongly connected tournaments
• The number of Gallai \(k\)-colorings of complete graphs
• 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)