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/