Some results on incidence coloring, star arboricity and domination number

Pak Kiu SUN, Wai Chee SHIU

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)107-114
Number of pages8
JournalAustralasian Journal of Combinatorics
Volume54
Issue number2
Publication statusPublished - 2012

Scopus Subject Areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Some results on incidence coloring, star arboricity and domination number'. Together they form a unique fingerprint.

Cite this