Fractional Incidence Coloring and Star Arboricity of Graphs

Abstract

This paper generalizes the results of Guiduli [B. Guiduli, On incidence coloring and star arboricity of graphs. Discrete Math. \(163
(1997), 275-278]\) on the incidence coloring of graphs to the fractional incidence coloring. Tight asymptotic bounds analogous to Guiduli’s results are given for the fractional incidence chromatic number of graphs. The fractional incidence chromatic number of circulant graphs is studied. Relationships between the \(k\)-tuple incidence chromatic number and the incidence chromatic number of the direct products and lexicographic products of graphs are established. Finally, for planar graphs \(G\), it is shown that if \(\Delta(G) \neq 6\), then \(\chi_i(G) \leq \Delta(G) + 5\); if \(\Delta(G) = 6\), then \(\chi_i(G) \leq \Delta(G) + 6\); where \(\chi_i(G)\) denotes the incidence chromatic number of \(G\). This improves the bound \(\chi_i(G) \leq \Delta(G) + 7\) for planar graphs given in [M. Hosseini Dolama, E. Sopena, X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. \(283 (2004)\), no. \(1-3, 121-128]\).