Edge colorings of graphs without monochromatic stars

DOI10.1016/J.DISC.2020.112140zbMath1448.05071arXiv1903.04541OpenAlexW2921306487MaRDI QIDQ2005736

Lucas Colucci, Abhishek Methuku, Ervin Gyoeri

Publication date: 8 October 2020

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

Abstract: In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on $n$ vertices may admit. Our results rely on an improved application of an entropy inequality of Shearer.

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

zbMATH Keywords

edge-coloringErdős-Rothschild problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Some intersection theorems for ordered sets and graphs
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
• Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size
• The maximum number of K ₃ -free and K ₄ -free edge 4-colorings
• Improved Bound on the Maximum Number of Clique-Free Colorings with Two and Three Colors
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

Related Items (3)

Counting orientations of graphs with no strongly connected tournaments ⋮ Graphs with many edge-colorings such that complete graphs are rainbow ⋮ An extension of the rainbow Erdős-Rothschild problem

This page was built for publication: Edge colorings of graphs without monochromatic stars