NP-completeness of 4-incidence colorability of semi-cubic graphs |
| |
Authors: | Xueliang Li Jianhua Tu |
| |
Institution: | Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China |
| |
Abstract: | The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most Δ+2, where Δ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, in 2005 Maydanskiy proved that the conjecture holds for any graph with Δ?3. It is easily deduced that the incidence coloring number of a semi-cubic graph is 4 or 5. In this paper, we show that it is already NP-complete to determine if a semi-cubic graph is 4-incidence colorable, and therefore it is NP-complete to determine if a general graph is k-incidence colorable. |
| |
Keywords: | 05C15 68Q17 |
本文献已被 ScienceDirect 等数据库收录! |
|