Interval incidence graph coloring

In this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number  χiiχii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete kk-partite graphs. We also study the complexity of the interval incidence coloring problem for subcubic graphs for which we show that the problem of determining whether χii≤4χii≤4 can be solved in polynomial time whereas χii≤5χii≤5 is NPNP-complete.