Edge-colorings avoiding patterns in a triangle

DOI10.1016/J.DISC.2024.113896MaRDI QIDQ6197754zbMATH OpenWikidataFDO

Authors Carlos Hoppen, Hanno Lefmann, Dionatan Ricardo Schmidt

Publication date 19 February 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

edge coloringErdős-Rothchild problemextremal graph theory

Mathematics Subject Classification ID

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

Abstract: For positive integers $n$ and $r$, we consider $n$-vertex graphs with the maximum number of $r$-edge-colorings with no copy of a triangle where exactly two colors appear. We prove that, if $2leqrleq26$ and $n$ is sufficiently large, the maximum is attained by the bipartite Tur'{a}n graph $T_2(n)$ on $n$ vertices. This is best possible, as $T_2(n)$ is not extremal for $rgeq27$ colors and $ngeq3$.

Recommendations

• Remarks on an edge-coloring problem
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Maximum number of triangle-free edge colourings with five and six colours

Cites work

• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• A rainbow Erdös-Rothschild problem
• An extension of the rainbow Erdős-Rothschild problem
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Exact solutions to the Erdős-Rothschild problem
• scientific article; zbMATH DE number 3487496 (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?)
• Improved bound on the maximum number of clique-free colorings with two and three colors
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Remarks on an edge-coloring problem
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The number of Gallai k-colorings of complete graphs
• The number of oriantations having no fixed tournament
• The Typical Structure of Gallai Colorings and Their Extremal Graphs

Cited in

(3)

• Remarks on an edge-coloring problem
• Maximum number of triangle-free edge colourings with five and six colours
• Combinatorics. Abstracts from the workshop held January 4--9, 2026

This page was built for publication: Edge-colorings avoiding patterns in a triangle

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