On incidence coloring for some cubic graphs

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

Research output: Contribution to journalJournal articlepeer-review

25 Citations (Scopus)
37 Downloads (Pure)

Abstract

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
Volume252
Issue number1-3
DOIs
Publication statusPublished - 31 May 2002

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Cubic graph
  • Incidence coloring
  • Restrained decomposition

Fingerprint

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

Cite this