On subgraphs without large components
| Autor: | Glenn G. Chappell, John Gimbel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Mathematica Bohemica, Vol 142, Iss 1, Pp 85-111 (2017) |
| Druh dokumentu: | article |
| ISSN: | 0862-7959 2464-7136 |
| DOI: | 10.21136/MB.2017.0013-14 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|