Defective 2-colorings of planar graphs without 4-cycles and 5-cycles |
| |
Authors: | Pongpat Sittitrai Kittikorn Nakprasit |
| |
Affiliation: | Department of Mathematics, Faculty of Science, Khon Kaen University, 40002, Thailand |
| |
Abstract: | A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and |
| |
Keywords: | Defective coloring Planar graph Cycle |
本文献已被 ScienceDirect 等数据库收录! |
|