arXiv Open Access 2017

Vertex partitions of $(C_3,C_4,C_6)$-free planar graphs

François Dross Pascal Ochem

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DM math.CO

Penulis (2)

François Dross

Pascal Ochem

Format Sitasi

APA MLA BibTeX

Dross, F., Ochem, P. (2017). Vertex partitions of $(C_3,C_4,C_6)$-free planar graphs. https://arxiv.org/abs/1711.08710

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓