1. Interval incidence coloring of bipartite graphs.
- Author
-
Janczewski, Robert, Małafiejska, Anna, and Małafiejski, Michał
- Subjects
- *
BIPARTITE graphs , *GRAPH theory , *GRAPH coloring , *PROBLEM solving , *MATHEMATICAL bounds , *ALGORITHMS , *TREE graphs - Abstract
Abstract: In this paper 1 [1] The extended abstract of this paper appeared on PPAM 2009, LNCS 6067 (2010) 11–20. we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number ( ) for bipartite graphs , and we prove that 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 and we show that 5-coloring is easy and 6-coloring is hard ( -complete). Moreover, we construct an time optimal algorithm for trees. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF