Geodesic
On subgraphs without large components
Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 85-111.

Voir la notice de l'article provenant de la source 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
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},
     publisher = {mathdoc},
     volume = {142},
     number = {1},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%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. http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0013-14/

Cité par Sources :