## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 6575-6580 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 24 |

DOIs | |

Publication status | Published - 28 Dec 2008 |

## Scopus Subject Areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## User-Defined Keywords

- Complete bipartite graph
- Incidence coloring
- Outerplanar graph