Geodesic
Singular Turán Numbers and Worm-Colorings
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1061-1074.

Voir la notice de l'article provenant de la source Library of Science

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 TS(n, G). Caro and Tuza in [Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32] obtained the asymptotics of TS(n, G) for every graph G, but determined the exact value of this function only in the case G = K3 and n ≡ 2 (mod 4). We determine TS(n, K3) for all n ≡ 0 (mod 4) and n ≡ 1 (mod 4), and also TS(n, Kr+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 
@article{DMGT_2022_42_4_a2,
     author = {Gerbner, D\'aniel and Patk\'os, Bal\'azs and Vizer, M\'at\'e and Tuza, Zsolt},
     title = {Singular {Tur\'an} {Numbers} and {Worm-Colorings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1061--1074},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a2/}
}
TY  - JOUR
AU  - Gerbner, Dániel
AU  - Patkós, Balázs
AU  - Vizer, Máté
AU  - Tuza, Zsolt
TI  - Singular Turán Numbers and Worm-Colorings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1061
EP  - 1074
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a2/
LA  - en
ID  - DMGT_2022_42_4_a2
ER  - 
%0 Journal Article
%A Gerbner, Dániel
%A Patkós, Balázs
%A Vizer, Máté
%A Tuza, Zsolt
%T Singular Turán Numbers and Worm-Colorings
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1061-1074
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a2/
%G en
%F DMGT_2022_42_4_a2
Gerbner, Dániel; Patkós, Balázs; Vizer, Máté; Tuza, Zsolt. Singular Turán Numbers and Worm-Colorings. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1061-1074. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a2/

[1] M. Albertson, Turán theorems with repeated degrees, Discrete Math. 100 (1992) 235–241. https://doi.org/10.1016/0012-365X(92)90644-U

[2] K. Amin, J. Faudree, R.J. Gould and E. Sidorowicz, On the non-( p − 1)-partite Kp-free graphs, Discuss. Math. Graph Theory 33 (2013) 9–23. https://doi.org/10.7151/dmgt.1654

[3] B. Andrásfai, Graphentheoretische Extremalprobleme, Acta Math. Hungar. 15 (1964) 413–418. https://doi.org/10.1007/BF01897150

[4] A. Brouwer, Some lotto numbers from an extension of Turán’s theorem, in: Afdeling Zuivere Wiskunde 152 (Stichting Mathematish Centrum, Amsterdam, 1981).

[5] Y. Caro and Zs. Tuza, Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32.

[6] P. Erdős, Extremal problems in graph theory, in: Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963 (1964) 29–36.

[7] 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

[8] P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57.

[9] 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

[10] D. Gerbner and B. Patkós, Extremal Finite Set Theory (CRC Press, 2018).

[11] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571–584. https://doi.org/10.7151/dmgt.1814

[12] D. Hanson and B. Toft, k-saturated graphs of chromatic number at least k, Ars Combin. 31 (1991) 159–164.

[13] M. Kang and O. Pikhurko, Maximum Kr+1-free graphs which are not r-partite, Mat. Stud. 24 (2005) 12–20.

[14] P. Turán, Egy gráfelméleti szélsőértékfeladatról, Mat. Fiz. Lapok 48 (1941) 436–452.