Properly colored C₄'s in edge-colored graphs

DOI10.1016/J.DISC.2020.112116MaRDI QIDQ2005704zbMATH OpenOpenAlexFDO

Authors Colton Magnant, Chuandong Xu, Shenggui Zhang

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

threshold graphanti-Ramsey numberextremal graphcolor degreeproperly colored cycle

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: When many colors appear in edge-colored graphs, it is only natural to expect rainbow subgraphs to appear. This anti-Ramsey problem has been studied thoroughly and yet there remain many gaps in the literature. Expanding upon classical and recent results forcing rainbow triangles to appear, we consider similar conditions which force the existence of a properly colored copy of $C_4$.

Recommendations

• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• Monochromatic subgraphs in the absence of a properly colored 4-cycle
• Rainbow cycles in edge-colored graphs
• Rainbow subgraphs in properly edge‐colored graphs

Cites work

• scientific article; zbMATH DE number 3494450 (Why is no real title available?)
• An anti-Ramsey theorem
• An anti-Ramsey theorem on cycles
• Color degree and heterochromatic cycles in edge-colored graphs
• Complete solution for the rainbow numbers of matchings
• Graphs \& digraphs
• Minimal colorings for properly colored subgraphs
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Monochromatic subgraphs in the absence of a properly colored 4-cycle
• On a problem of K. Zarankiewicz
• On maximal paths and circuits of graphs
• On sufficient conditions for rainbow cycles in edge-colored graphs
• Properly edge-colored theta graphs in edge-colored complete graphs
• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Rainbow cliques in edge-colored graphs
• Rainbow numbers for matchings and complete graphs
• Rainbow triangles in edge-colored graphs
• The history of degenerate (bipartite) extremal graph problems

Cited in

(14)

• Balanced edge-colorings avoiding rainbow cliques of size four
• scientific article; zbMATH DE number 5879543 (Why is no real title available?)
• On the maximal colorings of complete graphs without some small properly colored subgraphs
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• scientific article; zbMATH DE number 5532005 (Why is no real title available?)
• Proper edge colorings of Cartesian products with rainbow \(C_4\)-s
• Monochromatic subgraphs in the absence of a properly colored 4-cycle
• The edge C₄graph of some graph classes
• scientific article; zbMATH DE number 6531808 (Why is no real title available?)
• Properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs
• Counting rainbow triangles in edge-colored graphs
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• More on rainbow cliques in edge-colored graphs
• Edge‐colored complete graphs without properly colored even cycles: A full characterization

This page was built for publication: Properly colored \(C_4\)'s in edge-colored graphs

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