Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
component; independence; graph coloring; Ramsey number
component; independence; graph coloring; Ramsey number
Summary:
We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$-divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for $2$-coloring a planar triangle-free graph. Lastly, we consider Ramsey-type problems where graphs or their complements with large enough order must contain a large $k$-divided subgraph. We study the asymptotic behavior of ``$k$-divided Ramsey numbers''. We conclude by mentioning a number of open problems.
References:
[1] Albertson, M.: Open Problem 2. The Theory and Applications of Graphs. Proc. 4th Int. Conf., Kalamazoo, 1980 (1981), John Wiley & Sons, New York. MR 0634511 | Zbl 0459.00006
[2] Alon, N., Ding, G., Oporowski, B., Vertigan, D.: Partitioning into graphs with only small components. J. Comb. Theory, Ser. B 87 (2003), 231-243. DOI 10.1016/S0095-8956(02)00006-0 | MR 1957474 | Zbl 1023.05045
[3] Berke, R.: Coloring and Transversals of Graphs. Ph.D. thesis. ETH, Zurich (2008).
[4] Boesch, F., Tindell, R.: Circulants and their connectivities. J. Graph Theory 8 (1984), 487-499. DOI 10.1002/jgt.3190080406 | MR 0766498 | Zbl 0549.05048
[5] Burr, S. A.: Diagonal Ramsey numbers for small graphs. J. Graph Theory 7 (1983), 57-69. DOI 10.1002/jgt.3190070108 | MR 0693021 | Zbl 0513.05041
[6] Burr, S. A., Erdős, P., Faudree, R. J., Schelp, R. H.: On the difference between consecutive Ramsey numbers. Util. Math. 35 (1989), 115-118. MR 0992396 | Zbl 0678.05039
[7] Chappell, G. G.: GraphR [computer software]. August 26, 2016. Available at https://www.cs.uaf.edu/users/chappell/public_html/papers/graphr/
[8] Chappell, G. G., Gimbel, J.: On defective Ramsey numbers. Avaible at https://www.cs.uaf.edu/users/chappell/public_html/papers/defram/
[9] Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs. CRC Press, Boca Raton (2011). MR 2766107 | Zbl 1211.05001
[10] 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
[11] Cowen, L. J., Cowen, R. H., Woodall, D. R.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory 10 (1986), 187-195. DOI 10.1002/jgt.3190100207 | MR 0890224 | Zbl 0596.05024
[12] Cowen, L., Goddard, W., Jesurum, C. E.: Defective coloring revisited. J. Graph Theory 24 (1997), 205-219. DOI 10.1002/(SICI)1097-0118(199703)24 | MR 1431666 | Zbl 0877.05019
[13] Eaton, N., Hull, T.: Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. 25 (1999), 79-87. MR 1668108 | Zbl 0916.05026
[14] Ekim, T., Gimbel, J.: Some defective parameters in graphs. Graphs Combin. 29 (2013), 213-224. DOI 10.1007/s00373-011-1111-5 | MR 3027597 | Zbl 1263.05028
[15] Era, H., Urabe, M.: On the $k$-independent sets of graphs. Proc. Fac. Sci. Tokai Univ. 26 (1991), 1-4. MR 1148560 | Zbl 0752.05032
[16] Erdős, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53 (1947), 292-294. DOI 10.1090/S0002-9904-1947-08785-1 | MR 0019911 | Zbl 0032.19203
[17] Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2 (1935), 463-470. MR 1556929 | Zbl 0012.27010
[18] Esperet, L., Joret, G.: Colouring planar graphs with three colours and no large monochromatic components. Comb. Probab. Comput. 23 (2014), 551-570. DOI 10.1017/S0963548314000170 | MR 3217360 | Zbl 06325560
[19] Esperet, L., Ochem, P.: Islands in graphs on surfaces. SIAM J. Discrete Math. 30 (2016), 206-219. DOI 10.1137/140957883 | MR 3455135 | Zbl 1329.05105
[20] Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Comb. 11 (2004), research paper R46, 9 pages. MR 2097312 | Zbl 1053.05046
[21] Fink, J. F., Jacobson, M. S.: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science. Proc. 5th Quadr. Int. Conf. on the Theory and Applications of Graphs with special emphasis on Algorithms and Computer Science Applications, Kalamazoo, 1984 (Y. Alavi et al., eds.) Wiley-Interscience Publication, John Wiley & Sons, New York (1985), 301-311. MR 0812672 | Zbl 0573.05050
[22] Garey, M. R., Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977), 826-834. DOI 10.1137/0132071 | MR 0443426 | Zbl 0396.05009
[23] Garey, M. R., Johnson, D. S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976), 237-267. DOI 10.1016/0304-3975(76)90059-1 | MR 0411240 | Zbl 0338.05120
[24] Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discrete Math. 272 (2003), 139-154. DOI 10.1016/S0012-365X(03)00177-8 | MR 2009539 | Zbl 1028.05032
[25] Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Natur. Reihe 8 (1959), 109-120. MR 0116320 | Zbl 0089.39506
[26] Haxell, P., Szabó, T., Tardos, G.: Bounded size components - partitions and transversals. J. Comb. Theory, Ser. B 88 (2003), 281-297. DOI 10.1016/S0095-8956(03)00031-5 | MR 1983359 | Zbl 1033.05083
[27] Kleinberg, J., Motwani, R., Raghavan, P., Venkatasubramanian, S.: Storage management for evolving databases. Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS 97) (1997), 353-362.
[28] Linial, N., Matoušek, J., Sheffet, O., Tardos, G.: Graph colouring with no large monochromatic components. Comb. Probab. Comput. 17 (2008), 577-589. DOI 10.1017/S0963548308009140 | MR 2433942 | Zbl 1171.05021
[29] Lortz, R., Mengersen, I.: Bounds on Ramsey numbers of certain complete bipartite graphs. Result. Math. 41 (2002), 140-149. DOI 10.1007/BF03322761 | MR 1888725 | Zbl 1009.05100
[30] Lovász, L.: On decomposition of graphs. Stud. Sci. Math. Hung. 1 (1966), 237-238. MR 0202630 | Zbl 0151.33401
[31] Matoušek, J., Přívětivý, A.: Large monochromatic components in two-colored grids. SIAM J. Discrete Math. 22 (2008), 295-311. DOI 10.1137/070684112 | MR 2383243 | Zbl 1159.05021
[32] Nešetřil, J., Rapaud, A., Sopena, E.: Colorings and girth of oriented planar graphs. Discrete Math. 165/166 (1997), 519-530. DOI 10.1016/S0012-365X(96)00198-7 | MR 1439297 | Zbl 0873.05042
[33] Radziszowski, S. P.: Small Ramsey numbers. Revision \# 14: January 12, 2014. Electron. J. Comb. DS1, Dynamic Surveys (electronic only) (1996), 94 pages. MR 1670625 | Zbl 0953.05048
[34] Thomassen, C.: Five-coloring maps on surfaces. J. Comb. Theory, Ser. B 59 (1993), 89-105. DOI 10.1006/jctb.1993.1057 | MR 1234386 | Zbl 0794.05026
[35] Thomassen, C.: A short list color proof of Grötzsch's theorem. J. Comb. Theory, Ser. B 88 (2003), 189-192. DOI 10.1016/S0095-8956(03)00029-7 | MR 1974149 | Zbl 1025.05022
Search
Partner of
