On color isomorphic subdivisions

DOI10.1016/J.DISC.2022.112805MaRDI QIDQ2113360zbMATH OpenOpenAlexFDO

Authors Zixiang Xu, Gennian Ge

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

color isomorphicedge-coloringextremal problemssubdivision

Mathematics Subject Classification ID

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

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

Review text

For \(k \geq 2\) and graph \(H\), let \(f_k(n,H)\) denote the smallest positive integer \(C\) such that there is 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 work, the authors study the growth rate of \(f_2(n,H_t)\), where \(H_t\) is the 1-subdivision of \(K_t\), \(t\geq 3\). Specifically, in the main result of the paper, they prove that \[ f_2(n,H_t) = \Omega \Big(n^{1+\frac{1}{2t-3}}\Big).\] The introduction of the function \(f_k(n,H)\) originated from the work of \textit{D. Conlon} and \textit{M. Tyomkyn} [SIAM J. Discrete Math. 35, No. 3, 2249--2264 (2021; Zbl 1478.05049)].

Recommendations

• Color isomorphic even cycles and a related Ramsey problem
• Anti-Ramsey numbers of subdivided graphs
• The extremal number of the subdivisions of the complete bipartite graph
• Rainbow Turán number of clique subdivisions
• scientific article; zbMATH DE number 434896

Cites work

• Color isomorphic even cycles and a related Ramsey problem
• Improved bounds for the extremal number of subdivisions
• More on the extremal number of subdivisions
• Number of Points of Varieties in Finite Fields
• On the extremal number of subdivisions
• On the rational Turán exponents conjecture
• Random algebraic construction of extremal graphs
• Repeated patterns in proper colorings
• The history of degenerate (bipartite) extremal graph problems
• Turán number of bipartite graphs with no \(K_{t,t}\)
• Turán numbers of subdivided graphs

Cited in

(3)

• Subdivisions and the chromatic index ofr-graphs
• Color isomorphic even cycles and a related Ramsey problem
• Lower bounds on the Erdős–Gyárfás problem via color energy 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)