Search
Abstract
In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=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 and we show that 5-coloring is easy and 6-coloring is hard (NP-complete). Moreover, we construct an O(nΔ^3.5logΔ) time optimal algorithm for trees.
Citations
-
3
CrossRef
-
0
Web of Science
-
4
Scopus
Authors (3)
Cite as
Full text
download paper
downloaded 22 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.10.007
- License
- Copyright (2013 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 166,
pages 131 - 140,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2014
- Bibliographic description:
- Janczewski R., Małafiejska A., Małafiejski M.: Interval incidence coloring of bipartite graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 166, (2014), s.131-140
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.10.007
- Verified by:
- Gdańsk University of Technology
seen 168 times