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

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.

Vertex partitions of $(C_{3}, C_{4}, C_{6})$ -free planar graphs

文献摘要

讨论

讲解博客

AI智能校验

Vertex partitions of $(C_{3}, C_{4}, C_{6})$ -free planar graphs

文献摘要

讨论

讲解博客

AI智能校验

Vertex partitions of (C3,C4,C6)(C3​,C4​,C6​)-free planar graphs

文献摘要

讨论

|讲解博客

|AI智能校验

Vertex partitions of (C3,C4,C6)(C3​,C4​,C6​)-free planar graphs

文献摘要

讨论

|讲解博客

|AI智能校验

Vertex partitions of $(C_{3}, C_{4}, C_{6})$ -free planar graphs

讲解博客

AI智能校验

Vertex partitions of $(C_{3}, C_{4}, C_{6})$ -free planar graphs

讲解博客

AI智能校验