The subchromatic index of graphs

Year, pages: 2007, 129 - 146

In an edge coloring of a graph each color class forms a subgraph without a path of length two (a matching). An edge subcoloring extends this concept: each color class in an edge subcoloring forms a subgraph without path of length three. While every graph with maximum degree at most two is edge $2$-subcolorable, we point out in this paper that recognizing edge $2$-subcolorable graphs with maximum degree three is NP@-complete, even when restricted to triangle-free graphs. As by-products, we obtain NP@-completeness results for the star index and the subchromatic number for several classes of graphs. It is also proved that recognizing edge $3$-subcolorable graphs is NP@-complete. Moreover, edge subcolorings and subchromatic index of various basic graph classes are studied. In particular, we show that every unicyclic graph is edge $3$-subcolorable and edge $2$-subcolorable unicyclic graphs have a simple structure allowing an easy linear time recognition.

Fiala, J., Van Bang Le, . 2007. The subchromatic index of graphs. In Tatra Mountains Mathematical Publications, vol. 36, no.2, pp. 129-146. 1210-3195.

Fiala, J., Van Bang Le, . (2007). The subchromatic index of graphs. Tatra Mountains Mathematical Publications, 36(2), 129-146. 1210-3195.