Article in volume
Authors:
Title:
Singular Turán numbers and WORM-colorings
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1061-1074
Received: 2019-09-12 , Revised: 2020-04-26 , Accepted: 2020-04-30 , Available online: 2020-06-04 , https://doi.org/10.7151/dmgt.2335
Abstract:
A subgraph $G$ of $H$ is singular if the vertices of $G$ either have
the same degree in $H$ or have pairwise distinct degrees in $H$. The largest
number of edges of a graph on $n$ vertices that does not contain a singular
copy of $G$ is denoted by $T_S(n,G)$. Caro and Tuza in [Singular
Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32] obtained the
asymptotics of $T_S(n,G)$ for every graph $G$, but determined the exact value
of this function only in the case $G=K_3$ and $n\equiv 2$ (mod 4). We determine
$T_S(n,K_3)$ for all $n\equiv 0$ (mod 4) and $n\equiv 1$ (mod 4), and also
$T_S(n,K_{r+1})$ for large enough $n$ that is divisible by $r$.
We also explore the connection to the so-called $G$-WORM colorings (vertex
colorings without rainbow or monochromatic copies of $G$) and obtain new results
regarding the largest number of edges that a graph with a $G$-WORM coloring can
have.
Keywords:
Turán number, WORM-coloring, singular Turán numbers
References:
- M. Albertson, Turán theorems with repeated degrees, Discrete Math. 100 (1992) 235–241.
https://doi.org/10.1016/0012-365X(92)90644-U - K. Amin, J. Faudree, R.J. Gould and E. Sidorowicz, On the non-$(p-1)$-partite $K_p$-free graphs, Discuss. Math. Graph Theory 33 (2013) 9–23.
https://doi.org/10.7151/dmgt.1654 - B. Andrásfai, Graphentheoretische Extremalprobleme, Acta Math. Hungar. 15 (1964) 413–418.
https://doi.org/10.1007/BF01897150 - A. Brouwer, Some lotto numbers from an extension of Turán's theorem, in: Afdeling Zuivere Wiskunde 152, (Stichting Mathematish Centrum, Amsterdam 1981).
- Y. Caro and Zs. Tuza, Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32.
- P. Erdős, Extremal problems in graph theory, in: Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963 (1964) 29–36.
- P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar. 10 (1959) 337–356.
https://doi.org/10.1007/BF02024498 - P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57.
- Z. Füredi and M. Simonovits, The history of degenerate $($bipartite$)$ extremal graph problems, in: Erdős Centennial, Bolyai Soc. Math. Stud. 25, (Springer, Berlin, Heidelberg 2013) 169–264.
https://doi.org/10.1007/978-3-642-39286-3_7 - D. Gerbner and B. Patkós, Extremal Finite Set Theory (CRC Press, 2018).
- W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571–584.
https://doi.org/10.7151/dmgt.1814 - D. Hanson and B. Toft, $k$-saturated graphs of chromatic number at least $k$, Ars Combin. 31 (1991) 159–164.
- M. Kang and O. Pikhurko, Maximum $K_{r+1}$-free graphs which are not $r$-partite, Mat. Stud. 24 (2005) 12–20.
- P. Turán, Egy gráfelméleti szélsőértékfeladatról, Mat. Fiz. Lapok 48 (1941) 436–452.
Close