On incidence coloring for some cubic graphs

Wai Chee SHIU, Peter Che Bor Lam, Dong Ling Chen

Research output: Contribution to journalJournal articlepeer-review

24 Citations (Scopus)
28 Downloads (Pure)


In 1993, Brualdi and Massey conjectured that every graph can be incidence-colored with Δ+ 2 colors, where Δ is the maximum degree of a graph. Although this conjecture was solved in the negative by an example in I. Algor and N. Alon (Discrete Math. 75 (1989) 11) it might hold for some special classes of graphs. In this paper, we consider graphs with maximum degree Δ = 3 and show that the conjecture holds for cubic Hamiltonian graphs and some other cubic graphs.

Original languageEnglish
Pages (from-to)259-266
Number of pages8
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 31 May 2002

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Cubic graph
  • Incidence coloring
  • Restrained decomposition


Dive into the research topics of 'On incidence coloring for some cubic graphs'. Together they form a unique fingerprint.

Cite this