Mathematics – Combinatorics
Scientific paper
2006-07-04
Mathematics
Combinatorics
11 pages
Scientific paper
The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most ${\it \Delta}+2$, where ${\it \Delta}$ 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 ${\it \Delta}\leq 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.
Li Xueliang
Tu Jianhua
No associations
LandOfFree
NP-completeness of 4-incidence colorability of semi-cubic graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with NP-completeness of 4-incidence colorability of semi-cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-completeness of 4-incidence colorability of semi-cubic graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-240047