Geodesic
On subgraphs without large components
Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 85-111
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/MB.2017.0013-14
Classification : 05C55, 05C69, 05C85, 68Q17, 68R10
Keywords: component; independence; graph coloring; Ramsey number 
@article{10_21136_MB_2017_0013_14,
     author = {Chappell, Glenn G. and Gimbel, John},
     title = {On subgraphs without large components},
     journal = {Mathematica Bohemica},
     pages = {85--111},
     year = {2017},
     volume = {142},
     number = {1},
     doi = {10.21136/MB.2017.0013-14},
     mrnumber = {3619989},
     zbl = {06738572},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0013-14/}
}
TY  - JOUR
AU  - Chappell, Glenn G.
AU  - Gimbel, John
TI  - On subgraphs without large components
JO  - Mathematica Bohemica
PY  - 2017
SP  - 85
EP  - 111
VL  - 142
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0013-14/
DO  - 10.21136/MB.2017.0013-14
LA  - en
ID  - 10_21136_MB_2017_0013_14
ER  - 
%0 Journal Article
%A Chappell, Glenn G.
%A Gimbel, John
%T On subgraphs without large components
%J Mathematica Bohemica
%D 2017
%P 85-111
%V 142
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0013-14/
%R 10.21136/MB.2017.0013-14
%G en
%F 10_21136_MB_2017_0013_14
Chappell, Glenn G.; Gimbel, John. On subgraphs without large components. Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 85-111. doi: 10.21136/MB.2017.0013-14

[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 | JFM

[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 | MR | JFM

[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 | MR | JFM

[5] Burr, S. A.: Diagonal Ramsey numbers for small graphs. J. Graph Theory 7 (1983), 57-69. | DOI | MR | JFM

[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 | JFM

[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 | JFM

[10] Cockayne, E. J., Mynhardt, C. M.: On 1-dependent Ramsey numbers for graphs. Discuss. Math., Graph Theory 19 (1999), 93-110. | DOI | MR | JFM

[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 | MR | JFM

[12] Cowen, L., Goddard, W., Jesurum, C. E.: Defective coloring revisited. J. Graph Theory 24 (1997), 205-219. | DOI | MR | JFM

[13] Eaton, N., Hull, T.: Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. 25 (1999), 79-87. | MR | JFM

[14] Ekim, T., Gimbel, J.: Some defective parameters in graphs. Graphs Combin. 29 (2013), 213-224. | DOI | MR | JFM

[15] Era, H., Urabe, M.: On the $k$-independent sets of graphs. Proc. Fac. Sci. Tokai Univ. 26 (1991), 1-4. | MR | JFM

[16] Erdős, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53 (1947), 292-294. | DOI | MR | JFM

[17] Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2 (1935), 463-470. | MR | JFM

[18] Esperet, L., Joret, G.: Colouring planar graphs with three colours and no large monochromatic components. Comb. Probab. Comput. 23 (2014), 551-570. | DOI | MR | JFM

[19] Esperet, L., Ochem, P.: Islands in graphs on surfaces. SIAM J. Discrete Math. 30 (2016), 206-219. | DOI | MR | JFM

[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 | JFM

[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 | JFM

[22] Garey, M. R., Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977), 826-834. | DOI | MR | JFM

[23] Garey, M. R., Johnson, D. S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976), 237-267. | DOI | MR | JFM

[24] Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discrete Math. 272 (2003), 139-154. | DOI | MR | JFM

[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 | JFM

[26] Haxell, P., Szabó, T., Tardos, G.: Bounded size components - partitions and transversals. J. Comb. Theory, Ser. B 88 (2003), 281-297. | DOI | MR | JFM

[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 | MR | JFM

[29] Lortz, R., Mengersen, I.: Bounds on Ramsey numbers of certain complete bipartite graphs. Result. Math. 41 (2002), 140-149. | DOI | MR | JFM

[30] Lovász, L.: On decomposition of graphs. Stud. Sci. Math. Hung. 1 (1966), 237-238. | MR | JFM

[31] Matoušek, J., Přívětivý, A.: Large monochromatic components in two-colored grids. SIAM J. Discrete Math. 22 (2008), 295-311. | DOI | MR | JFM

[32] Nešetřil, J., Rapaud, A., Sopena, E.: Colorings and girth of oriented planar graphs. Discrete Math. 165/166 (1997), 519-530. | DOI | MR | JFM

[33] Radziszowski, S. P.: Small Ramsey numbers. Revision \# 14: January 12, 2014. Electron. J. Comb. DS1, Dynamic Surveys (electronic only) (1996), 94 pages. | MR | JFM

[34] Thomassen, C.: Five-coloring maps on surfaces. J. Comb. Theory, Ser. B 59 (1993), 89-105. | DOI | MR | JFM

[35] Thomassen, C.: A short list color proof of Grötzsch's theorem. J. Comb. Theory, Ser. B 88 (2003), 189-192. | DOI | MR | JFM

Cité par Sources :