| Title:
|
Sparse sets in triangle-free graphs (English) |
| Author:
|
Ekim, Tınaz |
| Author:
|
Erdem, Burak Nur |
| Author:
|
Gimbel, John |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0011-4642 |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
151 |
| Issue:
|
3 |
| Year:
|
2026 |
| Pages:
|
385-405 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
A set of vertices is $k$-sparse if it induces a graph with a maximum degree of at most $k$. In this missive, we consider the order of the largest $k$-sparse set in a triangle-free graph of fixed order. We show, for example, that every triangle-free graph of order 11 contains a 1-sparse 5-set; every triangle-free graph of order 13 contains a 2-sparse 7-set; and every triangle-free graph of order 8 contains a 3-sparse 6-set. Further, these are all best possible. \endgraf For fixed $k$, we consider the growth rate of the largest $k$-sparse set of a triangle-free graph of order $n$. Also, we consider Ramsey numbers of the following type. Given $i$, what is the smallest $n$ having the property that all triangle-free graphs of order $n$ contain a 4-cycle or a $k$-sparse set of order $i$. We use both direct proof techniques and an efficient graph enumeration algorithm to obtain several values for defective Ramsey numbers and a parameter related to largest sparse sets in triangle-free graphs, along with their extremal graphs. (English) |
| Keyword:
|
defective Ramsey number |
| Keyword:
|
$k$-dense |
| Keyword:
|
$k$-sparse |
| Keyword:
|
$k$-dependent |
| Keyword:
|
extremal graph |
| MSC:
|
05C30 |
| MSC:
|
05C35 |
| MSC:
|
05C55 |
| DOI:
|
10.21136/MB.2025.0079-24 |
| . |
| Date available:
|
2026-08-24T07:50:53Z |
| Last updated:
|
2026-08-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/153713 |
| . |
| Reference:
|
[1] Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers.J. Comb. Theory, Ser. A 29 (1980), 354-360. Zbl 0455.05045, MR 0600598, 10.1016/0097-3165(80)90030-8 |
| Reference:
|
[2] Akdemir, A., Ekim, T.: Advances on defective parameters in graphs.Discrete Optim. 16 (2015), 62-69. Zbl 1387.05077, MR 3327669, 10.1016/j.disopt.2015.01.002 |
| Reference:
|
[3] Belmonte, R., Heggernes, P., Hof, P. van't, Rafiey, A., Saei, R.: Graph classes and Ramsey numbers.Discrete Appl. Math. 173 (2014), 16-27. Zbl 1298.05220, MR 3202286, 10.1016/j.dam.2014.03.016 |
| Reference:
|
[4] Belmonte, R., Lampis, M., Mitsou, V.: Defective coloring on classes of perfect graphs.Graph-Theoretic Concepts in Computer Science Lecture Notes in Computer Science 10520. Springer, Cham (2017), 113-126. Zbl 1483.05172, MR 3746149, 10.1007/978-3-319-68705-6_9 |
| Reference:
|
[5] Chappell, G., Gimbel, J.: On defective Ramsey numbers.Available at https://www.cs.uaf.edu/ {chappell/papers/defram/defram.pdf}. |
| Reference:
|
[6] Cockayne, E. J., Mynhardt, C. M.: On 1-dependent Ramsey numbers for graphs.Discuss. Math., Graph Theory 19 (1999), 93-110. Zbl 0932.05061, MR 1704453, 10.7151/dmgt.1088 |
| Reference:
|
[7] Demirci, Y. E., Ekim, T., Gimbel, J., z, M. A. Yıldı: Exact values of defective Ramsey numbers in graph classes.Discrete Optim. 42 (2021), Article ID 100673, 26 pages. Zbl 1506.05134, MR 4337783, 10.1016/j.disopt.2021.100673 |
| Reference:
|
[8] Demirci, Y. E., Ekim, T., z, M. A. Yıldı: Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs.Graphs Comb. 39 (2023), Article ID 18, 23 pages. Zbl 1509.05125, MR 4544255, 10.1007/s00373-023-02612-4 |
| Reference:
|
[9] Ekim, T., Gimbel, J.: Some defective parameters in graphs.Graphs Comb. 29 (2013), 213-224. Zbl 1263.05028, MR 3027597, 10.1007/s00373-011-1111-5 |
| Reference:
|
[10] Ekim, T., Gimbel, J., Şeker, O.: Small 1-defective Ramsey numbers in perfect graphs.Discrete Optim. 34 (2019), Article ID 100548, 25 pages. Zbl 1506.05135, MR 4028725, 10.1016/j.disopt.2019.06.001 |
| Reference:
|
[11] Erdem, B. N.: Sparse sets in triangle-free graphs.Available at \def{ } \brokenlink{https://github.com/{buraknurerdem/sparse-sets-in-triangle-free-graphs}} (2024). |
| Reference:
|
[12] Jones, K. Fraughnaugh: Independence in graphs with maximum degree four.J. Comb. Theory, Ser. B 37 (1984), 254-269. Zbl 0547.05057, MR 0769368, 10.1016/0095-8956(84)90058-3 |
| Reference:
|
[13] Fraughnaugh, K. L., Locke, S. C.: Lower bounds on size and independence in $K_4$-free graphs.J. Graph Theory 26 (1997), 61-71. Zbl 0883.05104, MR 1469353, 10.1002/(SICI)1097-0118(199710)26:2<61::AID-JGT1>3.0.CO;2-D |
| Reference:
|
[14] Kim, J. H.: The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$.Random Struct. Algorithms 7 (1995), 173-207. Zbl 0832.05084, MR 1369063, 10.1002/rsa.3240070302 |
| Reference:
|
[15] Lovász, L.: On decomposition of graphs.Stud. Sci. Math. Hung. 1 (1966), 237-238. Zbl 0151.33401, MR 0202630 |
| Reference:
|
[16] Matthews, M. M., Sumner, D. P.: Longest paths and cycles in $K_{1,3}$-free graphs.J. Graph Theory 9 (1985), 269-277. Zbl 0591.05041, MR 0797514, 10.1002/jgt.3190090208 |
| Reference:
|
[17] McKay, B. D., Piperno, A.: Practical graph isomorphism. II.J. Symb. Comput. 60 (2014), 94-112. Zbl 1394.05079, MR 3131381, 10.1016/j.jsc.2013.09.003 |
| Reference:
|
[18] Poljak, S.: A note on stable sets and colorings of graphs.Commentat. Math. Univ. Carol. 15 (1974), 307-309. Zbl 0284.05105, MR 0351881 |
| Reference:
|
[19] Staton, W.: Some Ramsey-type numbers and the independence ratio.Trans. Am. Math. Soc. 256 (1979), 353-370. Zbl 0428.05028, MR 0546922, 10.1090/S0002-9947-1979-0546922-6 |
| Reference:
|
[20] Steinberg, R., Tovey, C. A.: Planar Ramsey numbers.J. Comb. Theory, Ser. B 59 (1993), 288-296. Zbl 0794.05091, MR 1244935, 10.1006/jctb.1993.1070 |
| Reference:
|
[21] Turán, P.: On an extremal problem in graph theory.Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. Zbl 0026.26903, MR 0018405 |
| . |
