Two inequalities are established connecting the graph invariants of incidence chromatic number, star arboricity and domination number. Using these, upper and lower bounds are deduced for the incidence chromatic number of a graph and further reductions are made to the upper bound for a planar graph. It is shown that cubic graphs with orders not divisible by four are not 4-incidence colorable. Sharp upper bounds on the incidence chromatic numbers are determined for Cartesian products of graphs, and for joins and unions of graphs.
|Number of pages||8|
|Journal||Australasian Journal of Combinatorics|
|Publication status||Published - 2012|
Scopus Subject Areas
- Discrete Mathematics and Combinatorics