1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Singular Turán Numbers and Worm-Colorings

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1061 - 1074
Received: 12 Sep 2019
Accepted: 30 Apr 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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.

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

MSC 2010

[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 Search in Google Scholar

[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 Search in Google Scholar

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

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

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

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

[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 Search in Google Scholar

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

[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_710.1007/978-3-642-39286-3_7 Search in Google Scholar

[10] D. Gerbner and B. Patkós, Extremal Finite Set Theory (CRC Press, 2018).10.1201/9780429440809 Search in Google Scholar

[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 Search in Google Scholar

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

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo