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 language | English |
---|---|
Pages (from-to) | 259-266 |
Number of pages | 8 |
Journal | Discrete Mathematics |
Volume | 252 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 31 May 2002 |
Scopus Subject Areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
User-Defined Keywords
- Cubic graph
- Incidence coloring
- Restrained decomposition