Rainbow clique subdivisions

DOI10.1016/J.EJC.2023.103868MaRDI QIDQ6146498zbMATH OpenOpenAlexFDO

Authors

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

rainbow subdivisionrainbow Turán number of cycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We show that for any integer $tge2$, every properly edge colored $n$-vertex graph with average degree at least $(logn{)}^{2+o(1)}$ contains a rainbow subdivision of a complete graph of size $t$. Note that this bound is within a log factor of the lower bound. This also implies a result on the rainbow Tur'{a}n number of cycles.

Recommendations

• Rainbow Turán number of clique subdivisions
• Rainbow subdivisions of cliques
• Rainbow cliques in edge-colored graphs
• Rainbow triangles and cliques in edge-colored graphs

Cites work

• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• A solution to Erdős and Hajnal’s odd cycle problem
• An extremal problem for subdivisions ofK?5
• Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
• Compact topological minors in graphs
• Dependent random choice
• Disjoint isomorphic balanced clique subdivisions
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Large Topological Cliques in Graphs Without a 4-Cycle
• On the structure of linear graphs
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Rainbow Turán number of clique subdivisions
• Rainbow Turán problem for even cycles
• Rainbow Turán Problems
• Small topological complete subgraphs of ``dense graphs
• Subdivisions of a large clique in \(C_6\)-free graphs
• Subdivisions of graphs with large minimum degree
• The extremal number of longer subdivisions
• Topological Cliques in Graphs
• Topological cliques in graphs II
• Topological minors in graphs of large girth
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Turán numbers of subdivided graphs

Cited in

(3)

• Rainbow subdivisions of cliques
• Local rainbow colorings for various graphs
• Essentially tight bounds for rainbow cycles in proper edge-colourings

This page was built for publication: Rainbow clique subdivisions

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