Color isomorphic even cycles and a related Ramsey problem

DOI10.1137/20M1329652MaRDI QIDQ5128499zbMATH OpenFDO

Authors Gennian Ge, Yifan Jing, Zixiang Xu, Tao Zhang

Publication date 27 October 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algebraic constructionedge coloringgeneralized Ramsey number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Ramsey theory (05D10) Polynomials over finite fields (11T06)

Abstract: In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). 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$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_n$ and show that $f_k(n,C_4)=Theta(n)$ when $kgeqslant3$ and $nightarrowinfty$. The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$, such that the edges of every copy of $HsubseteqG$ together receive at least $q$ distinct colors. Establishing the relation to the Tur'{a}n number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$.

Recommendations

• A generalized Ramsey problem
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• An explicit construction for a Ramsey problem
• On color isomorphic subdivisions
• scientific article; zbMATH DE number 3494450

Cites work

• A polynomial approach to linear algebra
• A variant of the classical Ramsey problem
• Cycles of even length in graphs
• Decompositions into spanning rainbow structures
• Generalized Ramsey numbers: forbidding paths with few colors
• scientific article; zbMATH DE number 3763932 (Why is no real title available?)
• scientific article; zbMATH DE number 2197930 (Why is no real title available?)
• Improved bounds for the extremal number of subdivisions
• Linearly many rainbow trees in properly edge-coloured complete graphs
• Local properties in colored graphs, distinct distances, and difference sets
• Local properties via color energy graphs and forbidden configurations
• More distinct distances under local conditions
• More on the extremal number of subdivisions
• Number of Points of Varieties in Finite Fields
• On a class of degenerate extremal graph problems
• On a problem of K. Zarankiewicz
• On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• On generalized Ramsey theory: The bipartite case
• On multicolor Ramsey numbers for complete bipartite graphs
• Ramsey-type problem for an almost monochromatic \(K_4\)
• Random algebraic construction of extremal graphs
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• Turán numbers of theta graphs

Cited in

(4)

• On color isomorphic subdivisions
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Rainbow subgraphs in edge-colored planar and outerplanar graphs
• A polynomial resultant approach to algebraic constructions of extremal graphs

This page was built for publication: Color isomorphic even cycles and a related Ramsey problem

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