Abstrakt
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.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
4
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.10.007
- Licencja
- Copyright (2013 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 166,
strony 131 - 140,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2014
- Opis bibliograficzny:
- Janczewski R., Małafiejska A., Małafiejski M.: Interval incidence coloring of bipartite graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 166, (2014), s.131-140
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.10.007
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 172 razy