2019/09/11 by Dániel Gerbner, Balázs Patkós, Gerbner, Dániel +5 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1909.04980
A subgraph H of G is singular if the vertices of H either have the same degree in G or have pairwise distinct degrees in G. The largest number of edges of a graph on n vertices that does not contain a singular copy of H is denoted by TS(n,H). Caro and Tuza [Theory and Applications of Graphs, 6 (2019), 1--32] obtained the asymptotics of TS(n,H) for every graph H, but determined the exact value of this function only in the case H=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 H-WORM colorings (colorings without rainbow or monochromatic copies of H) and obtain new results regarding the largest number of edges that a graph with an H-WORM coloring can have.