Properly colored C₄'s in edge-colored graphs

DOI10.1016/J.DISC.2020.112116zbMATH Open1448.05078arXiv1905.10584OpenAlexW3080909369MaRDI QIDQ2005704FDOQ2005704

Authors: Colton Magnant, Chuandong Xu, Shenggui Zhang 

Publication date: 8 October 2020

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

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$.

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

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

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)

Cites Work

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

Cited In (14)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs
• Counting rainbow triangles in edge-colored graphs
• More on rainbow cliques in edge-colored graphs
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Edge‐colored complete graphs without properly colored even cycles: A full characterization
• Balanced edge-colorings avoiding rainbow cliques of size four

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)