On subgraphs without large components

Glenn G. Chappell; John Gimbel

Mathematica Bohemica (2017)

  • Volume: 142, Issue: 1, page 85-111
  • ISSN: 0862-7959

Abstract

top
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.

How to cite

top

Chappell, Glenn G., and Gimbel, John. "On subgraphs without large components." Mathematica Bohemica 142.1 (2017): 85-111. <http://eudml.org/doc/287903>.

@article{Chappell2017,
abstract = {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.},
author = {Chappell, Glenn G., Gimbel, John},
journal = {Mathematica Bohemica},
keywords = {component; independence; graph coloring; Ramsey number},
language = {eng},
number = {1},
pages = {85-111},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On subgraphs without large components},
url = {http://eudml.org/doc/287903},
volume = {142},
year = {2017},
}

TY - JOUR
AU - Chappell, Glenn G.
AU - Gimbel, John
TI - On subgraphs without large components
JO - Mathematica Bohemica
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 142
IS - 1
SP - 85
EP - 111
AB - 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.
LA - eng
KW - component; independence; graph coloring; Ramsey number
UR - http://eudml.org/doc/287903
ER -

References

top
  1. Albertson, M., Open Problem 2, The Theory and Applications of Graphs. Proc. 4th Int. Conf., Kalamazoo, 1980 (1981), John Wiley & Sons, New York. (1981) Zbl0459.00006MR0634511
  2. Alon, N., Ding, G., Oporowski, B., Vertigan, D., 10.1016/S0095-8956(02)00006-0, J. Comb. Theory, Ser. B 87 (2003), 231-243. (2003) Zbl1023.05045MR1957474DOI10.1016/S0095-8956(02)00006-0
  3. Berke, R., Coloring and Transversals of Graphs. Ph.D. thesis, ETH, Zurich (2008). (2008) 
  4. Boesch, F., Tindell, R., 10.1002/jgt.3190080406, J. Graph Theory 8 (1984), 487-499. (1984) Zbl0549.05048MR0766498DOI10.1002/jgt.3190080406
  5. Burr, S. A., 10.1002/jgt.3190070108, J. Graph Theory 7 (1983), 57-69. (1983) Zbl0513.05041MR0693021DOI10.1002/jgt.3190070108
  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. (1989) Zbl0678.05039MR0992396
  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). (2011) Zbl1211.05001MR2766107
  10. Cockayne, E. J., Mynhardt, C. M., 10.7151/dmgt.1088, Discuss. Math., Graph Theory 19 (1999), 93-110. (1999) Zbl0932.05061MR1704453DOI10.7151/dmgt.1088
  11. Cowen, L. J., Cowen, R. H., Woodall, D. R., 10.1002/jgt.3190100207, J. Graph Theory 10 (1986), 187-195. (1986) Zbl0596.05024MR0890224DOI10.1002/jgt.3190100207
  12. Cowen, L., Goddard, W., Jesurum, C. E., 10.1002/(SICI)1097-0118(199703)24, J. Graph Theory 24 (1997), 205-219. (1997) Zbl0877.05019MR1431666DOI10.1002/(SICI)1097-0118(199703)24
  13. Eaton, N., Hull, T., Defective list colorings of planar graphs, Bull. Inst. Combin. Appl. 25 (1999), 79-87. (1999) Zbl0916.05026MR1668108
  14. Ekim, T., Gimbel, J., 10.1007/s00373-011-1111-5, Graphs Combin. 29 (2013), 213-224. (2013) Zbl1263.05028MR3027597DOI10.1007/s00373-011-1111-5
  15. Era, H., Urabe, M., On the k -independent sets of graphs, Proc. Fac. Sci. Tokai Univ. 26 (1991), 1-4. (1991) Zbl0752.05032MR1148560
  16. Erdős, P., 10.1090/S0002-9904-1947-08785-1, Bull. Am. Math. Soc. 53 (1947), 292-294. (1947) Zbl0032.19203MR0019911DOI10.1090/S0002-9904-1947-08785-1
  17. Erdős, P., Szekeres, G., A combinatorial problem in geometry, Compos. Math. 2 (1935), 463-470. (1935) Zbl0012.27010MR1556929
  18. Esperet, L., Joret, G., 10.1017/S0963548314000170, Comb. Probab. Comput. 23 (2014), 551-570. (2014) Zbl06325560MR3217360DOI10.1017/S0963548314000170
  19. Esperet, L., Ochem, P., 10.1137/140957883, SIAM J. Discrete Math. 30 (2016), 206-219. (2016) Zbl1329.05105MR3455135DOI10.1137/140957883
  20. Farrugia, A., Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, Electron. J. Comb. 11 (2004), research paper R46, 9 pages. (2004) Zbl1053.05046MR2097312
  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. (1985) Zbl0573.05050MR0812672
  22. Garey, M. R., Johnson, D. S., 10.1137/0132071, SIAM J. Appl. Math. 32 (1977), 826-834. (1977) Zbl0396.05009MR0443426DOI10.1137/0132071
  23. Garey, M. R., Johnson, D. S., Stockmeyer, L., 10.1016/0304-3975(76)90059-1, Theor. Comput. Sci. 1 (1976), 237-267. (1976) Zbl0338.05120MR0411240DOI10.1016/0304-3975(76)90059-1
  24. Gimbel, J., Hartman, C., 10.1016/S0012-365X(03)00177-8, Discrete Math. 272 (2003), 139-154. (2003) Zbl1028.05032MR2009539DOI10.1016/S0012-365X(03)00177-8
  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. (1959) Zbl0089.39506MR0116320
  26. Haxell, P., Szabó, T., Tardos, G., 10.1016/S0095-8956(03)00031-5, J. Comb. Theory, Ser. B 88 (2003), 281-297. (2003) Zbl1033.05083MR1983359DOI10.1016/S0095-8956(03)00031-5
  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. (1997) 
  28. Linial, N., Matoušek, J., Sheffet, O., Tardos, G., 10.1017/S0963548308009140, Comb. Probab. Comput. 17 (2008), 577-589. (2008) Zbl1171.05021MR2433942DOI10.1017/S0963548308009140
  29. Lortz, R., Mengersen, I., 10.1007/BF03322761, Result. Math. 41 (2002), 140-149. (2002) Zbl1009.05100MR1888725DOI10.1007/BF03322761
  30. Lovász, L., On decomposition of graphs, Stud. Sci. Math. Hung. 1 (1966), 237-238. (1966) Zbl0151.33401MR0202630
  31. Matoušek, J., Přívětivý, A., 10.1137/070684112, SIAM J. Discrete Math. 22 (2008), 295-311. (2008) Zbl1159.05021MR2383243DOI10.1137/070684112
  32. Nešetřil, J., Rapaud, A., Sopena, E., 10.1016/S0012-365X(96)00198-7, Discrete Math. 165/166 (1997), 519-530. (1997) Zbl0873.05042MR1439297DOI10.1016/S0012-365X(96)00198-7
  33. Radziszowski, S. P., Small Ramsey numbers. Revision # 14: January 12, 2014, Electron. J. Comb. DS1, Dynamic Surveys (electronic only) (1996), 94 pages. (1996) Zbl0953.05048MR1670625
  34. Thomassen, C., 10.1006/jctb.1993.1057, J. Comb. Theory, Ser. B 59 (1993), 89-105. (1993) Zbl0794.05026MR1234386DOI10.1006/jctb.1993.1057
  35. Thomassen, C., 10.1016/S0095-8956(03)00029-7, J. Comb. Theory, Ser. B 88 (2003), 189-192. (2003) Zbl1025.05022MR1974149DOI10.1016/S0095-8956(03)00029-7

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.