Wyszukiwarka
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ść
pobierz publikację
pobrano 22 razy
- 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 168 razy