Interval incidence coloring of bipartite graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Interval incidence coloring of bipartite graphs

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

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

Publikacje, które mogą cię zainteresować

Meta Tagi