Interval incidence coloring of bipartite graphs ?
In this paper1 we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (?ii ? i i ) for bipartite graphs ?ii?2? ? i i ? 2 ? , and we prove that ?ii=2? ? i i = 2 ? holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e.we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic bipartite graphs. We also study the problem for bipartite graphs with ?=4 ? = 4 and we show that 5-coloring is easy and 6-coloring is hard (NP NP -complete). Moreover, we construct an O(n?3.5log?) O ( n ? 3.5 log ? ) time optimal algorithm for trees.
interval incidence coloring bipartite graphs subcubic graphs trees