Invalid proofs on incidence coloring

Wai Chee SHIU*, Pak Kiu SUN

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

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 languageEnglish
Pages (from-to)6575-6580
Number of pages6
JournalDiscrete Mathematics
Volume308
Issue number24
DOIs
Publication statusPublished - 28 Dec 2008

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Complete bipartite graph
  • Incidence coloring
  • Outerplanar graph

Fingerprint

Dive into the research topics of 'Invalid proofs on incidence coloring'. Together they form a unique fingerprint.

Cite this