Singular Turán Numbers and Worm-Colorings

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

Keywords

• turán number
• worm-coloring
• singular turán numbers
• 05c35
• 05d10