On color isomorphic subdivisions

DOI10.1016/J.DISC.2022.112805zbMATH Open1491.05113arXiv2009.01074OpenAlexW4205965597MaRDI QIDQ2113360FDOQ2113360

Zixiang Xu, Gennian Ge

Publication date: 14 March 2022

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

Abstract: Given a graph $H$ and an integer $kgeqslant2$, let $f_k(n,H)$ be the smallest number of colors $C$ such that there exists a proper edge-coloring of the complete graph $K_n$ with $C$ colors containing no $k$ vertex-disjoint color isomorphic copies of $H$. In this paper, we prove that $f_2(n,H_t)=Omega(n^{1+frac12t-3})$ where $H_t$ is the $1$-subdivision of the complete graph $K_t$. This answers a question of Conlon and Tyomkyn (arXiv: 2002.00921).

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

zbMATH Keywords

extremal problemsedge-coloringsubdivisioncolor isomorphic

Mathematics Subject Classification ID

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

Cites Work

• The History of Degenerate (Bipartite) Extremal Graph Problems
• Number of Points of Varieties in Finite Fields
• Repeated Patterns in Proper Colorings
• Turán number of bipartite graphs with no 𝐾_{𝑡,𝑡}
• On the Extremal Number of Subdivisions
• On the rational Turán exponents conjecture
• Random algebraic construction of extremal graphs
• Improved bounds for the extremal number of subdivisions
• More on the extremal number of subdivisions
• Turán Numbers of Subdivided Graphs
• Color Isomorphic Even Cycles and a Related Ramsey Problem

Cited In (2)

• Lower bounds on the Erdős–Gyárfás problem via color energy graphs
• Subdivisions and the chromatic index ofr-graphs

This page was built for publication: On color isomorphic subdivisions

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