2012/03/28 by Pak Kiu Sun, Sun, Pak Kiu, Wai Chee Shiu +1
Computer Science · Mathematics · #05C15 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C15 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1203.6143
8 pages
arxiv created 2012/03/28 · openalex publication_date 2012/03/28 · arxiv updated 2012/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two inequalities bridging the three isolated graph invariants, incidence chromatic number, star arboricity and domination number, were established. Consequently, we deduced an upper bound and a lower bound of the incidence chromatic number for all graphs. Using these bounds, we further reduced the upper bound of the incidence chromatic number of planar graphs and showed that cubic graphs with orders not divisible by four are not 4-incidence colorable. The incidence chromatic numbers of Cartesian product, join and union of graphs were also determined.