Loading...
Please wait, while we are loading the content...
Similar Documents
Vertex partitions of $(C_3,C_4,C_6)$-free planar graphs
| Content Provider | arXiv |
|---|---|
| Author | Dross, François Ochem, Pascal |
| Date of Submission | 2017-11-23 |
| Abstract | A graph is $(k_1,k_2)$-colorable if its vertex set can be partitioned into a graph with maximum degree at most $k_1$ and and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete. |
| Related Links | https://arxiv.org/pdf/1711.08710.pdf |
| arXiv | 1711.08710 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Discrete Mathematics Mathematics - Combinatorics Computer Science Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
