Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
defective Ramsey number; $k$-dense; $k$-sparse; $k$-dependent; extremal graph
defective Ramsey number; $k$-dense; $k$-sparse; $k$-dependent; extremal graph
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.
References:
[1] Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Comb. Theory, Ser. A 29 (1980), 354-360. DOI 10.1016/0097-3165(80)90030-8 | MR 0600598 | Zbl 0455.05045
[2] Akdemir, A., Ekim, T.: Advances on defective parameters in graphs. Discrete Optim. 16 (2015), 62-69. DOI 10.1016/j.disopt.2015.01.002 | MR 3327669 | Zbl 1387.05077
[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. DOI 10.1016/j.dam.2014.03.016 | MR 3202286 | Zbl 1298.05220
[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. DOI 10.1007/978-3-319-68705-6_9 | MR 3746149 | Zbl 1483.05172
[5] Chappell, G., Gimbel, J.: On defective Ramsey numbers. Available at https://www.cs.uaf.edu/ {chappell/papers/defram/defram.pdf}.
[6] Cockayne, E. J., Mynhardt, C. M.: On 1-dependent Ramsey numbers for graphs. Discuss. Math., Graph Theory 19 (1999), 93-110. DOI 10.7151/dmgt.1088 | MR 1704453 | Zbl 0932.05061
[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. DOI 10.1016/j.disopt.2021.100673 | MR 4337783 | Zbl 1506.05134
[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. DOI 10.1007/s00373-023-02612-4 | MR 4544255 | Zbl 1509.05125
[9] Ekim, T., Gimbel, J.: Some defective parameters in graphs. Graphs Comb. 29 (2013), 213-224. DOI 10.1007/s00373-011-1111-5 | MR 3027597 | Zbl 1263.05028
[10] Ekim, T., Gimbel, J., Şeker, O.: Small 1-defective Ramsey numbers in perfect graphs. Discrete Optim. 34 (2019), Article ID 100548, 25 pages. DOI 10.1016/j.disopt.2019.06.001 | MR 4028725 | Zbl 1506.05135
[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).
[12] Jones, K. Fraughnaugh: Independence in graphs with maximum degree four. J. Comb. Theory, Ser. B 37 (1984), 254-269. DOI 10.1016/0095-8956(84)90058-3 | MR 0769368 | Zbl 0547.05057
[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. DOI 10.1002/(SICI)1097-0118(199710)26:2<61::AID-JGT1>3.0.CO;2-D | MR 1469353 | Zbl 0883.05104
[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. DOI 10.1002/rsa.3240070302 | MR 1369063 | Zbl 0832.05084
[15] Lovász, L.: On decomposition of graphs. Stud. Sci. Math. Hung. 1 (1966), 237-238. MR 0202630 | Zbl 0151.33401
[16] Matthews, M. M., Sumner, D. P.: Longest paths and cycles in $K_{1,3}$-free graphs. J. Graph Theory 9 (1985), 269-277. DOI 10.1002/jgt.3190090208 | MR 0797514 | Zbl 0591.05041
[17] McKay, B. D., Piperno, A.: Practical graph isomorphism. II. J. Symb. Comput. 60 (2014), 94-112. DOI 10.1016/j.jsc.2013.09.003 | MR 3131381 | Zbl 1394.05079
[18] Poljak, S.: A note on stable sets and colorings of graphs. Commentat. Math. Univ. Carol. 15 (1974), 307-309. MR 0351881 | Zbl 0284.05105
[19] Staton, W.: Some Ramsey-type numbers and the independence ratio. Trans. Am. Math. Soc. 256 (1979), 353-370. DOI 10.1090/S0002-9947-1979-0546922-6 | MR 0546922 | Zbl 0428.05028
[20] Steinberg, R., Tovey, C. A.: Planar Ramsey numbers. J. Comb. Theory, Ser. B 59 (1993), 288-296. DOI 10.1006/jctb.1993.1070 | MR 1244935 | Zbl 0794.05091
[21] Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. MR 0018405 | Zbl 0026.26903
Search
Partner of
