A note on the strength and minimum color sum of bipartite graphs

Adrian Kosowski

doi:10.1016/j.dam.2009.03.008

A note on the strength and minimum color sum of bipartite graphs

Abstrakt

Siłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.

Cytowania

3

CrossRef
0

Web of Science
4

Scopus

Autor (1)

Adrian Kosowski dr inż.

Cytuj jako

Pełna treść

pobierz publikację

pobrano 32 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.03.008
Licencja: Copyright (2009 Elsevier B.V.)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

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 157, strony 2552 - 2554,
ISSN: 0166-218X
Język:: angielski
Rok wydania:: 2009
Opis bibliograficzny:: Kosowski A.: A note on the strength and minimum color sum of bipartite graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 157, nr. iss. 11, June. (2009), s.2552-2554
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.03.008
Weryfikacja:: Politechnika Gdańska