TY - JOUR
T1 - Invalid proofs on incidence coloring
AU - Shiu, W. C.
AU - Sun, P. K.
N1 - Funding Information:
The authors would like to thank the referee for valuable suggestions on the original manuscript. The authors were partially supported by the Pentecostal Holiness Church Incorporation (Hong Kong).
PY - 2008/12/28
Y1 - 2008/12/28
N2 - Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ = 4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ ≥ 7 is Δ + 1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ + 1)-incidence colorable.
AB - Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ = 4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ ≥ 7 is Δ + 1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ + 1)-incidence colorable.
KW - Complete bipartite graph
KW - Incidence coloring
KW - Outerplanar graph
UR - http://www.scopus.com/inward/record.url?scp=56649103846&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2007.11.030
DO - 10.1016/j.disc.2007.11.030
M3 - Journal article
AN - SCOPUS:56649103846
SN - 0012-365X
VL - 308
SP - 6575
EP - 6580
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 24
ER -