Name
Title | ||
|---|---|---|
Partitioning sparse graphs into an independent set and a graph with bounded size components |
Abstract | ||
|---|---|---|
We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph G admits an (I,Ok)-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most k. We prove that every graph G with mad(G)<52 admits an (I,O3)-partition. This implies that every planar graph with girth at least 10 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph G with mad(G)<8k3k+1=831−13k+1 admits an (I,Ok)-partition. This implies that every planar graph with girth at least 9 can be partitioned into an independent set and a set that induces a graph whose components have order at most 9. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.disc.2020.111921 | Discrete Mathematics |
Keywords | DocType | Volume |
Planar graphs,Vertex partition,Bounded component,Discharging method,Improper coloring,Islands | Journal | 343 |
Issue | ISSN | Citations |
8 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilkyoo Choi | 1 | 0 | 0.34 |
| François Dross | 2 | 10 | 5.83 |
| Pascal Ochem | 3 | 258 | 36.91 |