On subgraphs without large components
Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 85-111.
Voir la notice de l'article dans Czech Digital Mathematics Library
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
Mots-clés : component; independence; graph coloring; Ramsey number
Mots-clés : 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}, publisher = {mathdoc}, volume = {142}, number = {1}, year = {2017}, doi = {10.21136/MB.2017.0013-14}, mrnumber = {3619989}, zbl = {06738572}, language = {en}, url = {https://geodesic-test.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 PB - mathdoc UR - https://geodesic-test.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 -
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. https://geodesic-test.mathdoc.fr/articles/10.21136/MB.2017.0013-14/
Cité par Sources :