| Title:
|
On subgraphs without large components (English) |
| Author:
|
Chappell, Glenn G. |
| Author:
|
Gimbel, John |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
142 |
| Issue:
|
1 |
| Year:
|
2017 |
| Pages:
|
85-111 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
component |
| Keyword:
|
independence |
| Keyword:
|
graph coloring |
| Keyword:
|
Ramsey number |
| MSC:
|
05C55 |
| MSC:
|
05C69 |
| MSC:
|
05C85 |
| MSC:
|
68Q17 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 06738572 |
| idMR:
|
MR3619989 |
| DOI:
|
10.21136/MB.2017.0013-14 |
| . |
| Date available:
|
2017-02-21T17:23:11Z |
| Last updated:
|
2020-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146011 |
| . |
| Reference:
|
[1] Albertson, M.: Open Problem 2.The Theory and Applications of Graphs. Proc. 4th Int. Conf., Kalamazoo, 1980 (1981), John Wiley & Sons, New York. Zbl 0459.00006, MR 0634511 |
| Reference:
|
[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. Zbl 1023.05045, MR 1957474, 10.1016/S0095-8956(02)00006-0 |
| Reference:
|
[3] Berke, R.: Coloring and Transversals of Graphs. Ph.D. thesis.ETH, Zurich (2008). |
| Reference:
|
[4] Boesch, F., Tindell, R.: Circulants and their connectivities.J. Graph Theory 8 (1984), 487-499. Zbl 0549.05048, MR 0766498, 10.1002/jgt.3190080406 |
| Reference:
|
[5] Burr, S. A.: Diagonal Ramsey numbers for small graphs.J. Graph Theory 7 (1983), 57-69. Zbl 0513.05041, MR 0693021, 10.1002/jgt.3190070108 |
| Reference:
|
[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. Zbl 0678.05039, MR 0992396 |
| Reference:
|
[7] Chappell, G. G.: GraphR [computer software]. August 26, 2016.Available at https://www.cs.uaf.edu/users/chappell/public_html/papers/graphr/. |
| Reference:
|
[8] Chappell, G. G., Gimbel, J.: On defective Ramsey numbers.Avaible at https://www.cs.uaf.edu/users/chappell/public_html/papers/defram/. |
| Reference:
|
[9] Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs.CRC Press, Boca Raton (2011). Zbl 1211.05001, MR 2766107 |
| Reference:
|
[10] 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:
|
[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. Zbl 0596.05024, MR 0890224, 10.1002/jgt.3190100207 |
| Reference:
|
[12] Cowen, L., Goddard, W., Jesurum, C. E.: Defective coloring revisited.J. Graph Theory 24 (1997), 205-219. Zbl 0877.05019, MR 1431666, 10.1002/(SICI)1097-0118(199703)24 |
| Reference:
|
[13] Eaton, N., Hull, T.: Defective list colorings of planar graphs.Bull. Inst. Combin. Appl. 25 (1999), 79-87. Zbl 0916.05026, MR 1668108 |
| Reference:
|
[14] Ekim, T., Gimbel, J.: Some defective parameters in graphs.Graphs Combin. 29 (2013), 213-224. Zbl 1263.05028, MR 3027597, 10.1007/s00373-011-1111-5 |
| Reference:
|
[15] Era, H., Urabe, M.: On the $k$-independent sets of graphs.Proc. Fac. Sci. Tokai Univ. 26 (1991), 1-4. Zbl 0752.05032, MR 1148560 |
| Reference:
|
[16] Erdős, P.: Some remarks on the theory of graphs.Bull. Am. Math. Soc. 53 (1947), 292-294. Zbl 0032.19203, MR 0019911, 10.1090/S0002-9904-1947-08785-1 |
| Reference:
|
[17] Erdős, P., Szekeres, G.: A combinatorial problem in geometry.Compos. Math. 2 (1935), 463-470. Zbl 0012.27010, MR 1556929 |
| Reference:
|
[18] Esperet, L., Joret, G.: Colouring planar graphs with three colours and no large monochromatic components.Comb. Probab. Comput. 23 (2014), 551-570. Zbl 06325560, MR 3217360, 10.1017/S0963548314000170 |
| Reference:
|
[19] Esperet, L., Ochem, P.: Islands in graphs on surfaces.SIAM J. Discrete Math. 30 (2016), 206-219. Zbl 1329.05105, MR 3455135, 10.1137/140957883 |
| Reference:
|
[20] Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard.Electron. J. Comb. 11 (2004), research paper R46, 9 pages. Zbl 1053.05046, MR 2097312 |
| Reference:
|
[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. Zbl 0573.05050, MR 0812672 |
| Reference:
|
[22] Garey, M. R., Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete.SIAM J. Appl. Math. 32 (1977), 826-834. Zbl 0396.05009, MR 0443426, 10.1137/0132071 |
| Reference:
|
[23] Garey, M. R., Johnson, D. S., Stockmeyer, L.: Some simplified NP-complete graph problems.Theor. Comput. Sci. 1 (1976), 237-267. Zbl 0338.05120, MR 0411240, 10.1016/0304-3975(76)90059-1 |
| Reference:
|
[24] Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph.Discrete Math. 272 (2003), 139-154. Zbl 1028.05032, MR 2009539, 10.1016/S0012-365X(03)00177-8 |
| Reference:
|
[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. Zbl 0089.39506, MR 0116320 |
| Reference:
|
[26] Haxell, P., Szabó, T., Tardos, G.: Bounded size components - partitions and transversals.J. Comb. Theory, Ser. B 88 (2003), 281-297. Zbl 1033.05083, MR 1983359, 10.1016/S0095-8956(03)00031-5 |
| Reference:
|
[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. |
| Reference:
|
[28] Linial, N., Matoušek, J., Sheffet, O., Tardos, G.: Graph colouring with no large monochromatic components.Comb. Probab. Comput. 17 (2008), 577-589. Zbl 1171.05021, MR 2433942, 10.1017/S0963548308009140 |
| Reference:
|
[29] Lortz, R., Mengersen, I.: Bounds on Ramsey numbers of certain complete bipartite graphs.Result. Math. 41 (2002), 140-149. Zbl 1009.05100, MR 1888725, 10.1007/BF03322761 |
| Reference:
|
[30] Lovász, L.: On decomposition of graphs.Stud. Sci. Math. Hung. 1 (1966), 237-238. Zbl 0151.33401, MR 0202630 |
| Reference:
|
[31] Matoušek, J., Přívětivý, A.: Large monochromatic components in two-colored grids.SIAM J. Discrete Math. 22 (2008), 295-311. Zbl 1159.05021, MR 2383243, 10.1137/070684112 |
| Reference:
|
[32] Nešetřil, J., Rapaud, A., Sopena, E.: Colorings and girth of oriented planar graphs.Discrete Math. 165/166 (1997), 519-530. Zbl 0873.05042, MR 1439297, 10.1016/S0012-365X(96)00198-7 |
| Reference:
|
[33] Radziszowski, S. P.: Small Ramsey numbers. Revision \# 14: January 12, 2014.Electron. J. Comb. DS1, Dynamic Surveys (electronic only) (1996), 94 pages. Zbl 0953.05048, MR 1670625 |
| Reference:
|
[34] Thomassen, C.: Five-coloring maps on surfaces.J. Comb. Theory, Ser. B 59 (1993), 89-105. Zbl 0794.05026, MR 1234386, 10.1006/jctb.1993.1057 |
| Reference:
|
[35] Thomassen, C.: A short list color proof of Grötzsch's theorem.J. Comb. Theory, Ser. B 88 (2003), 189-192. Zbl 1025.05022, MR 1974149, 10.1016/S0095-8956(03)00029-7 |
| . |
