Sum coloring of bipartite graphs with bounded degree.

Michał Małafiejski; Krzysztof Giaro; Robert Janczewski; Marek Kubale

Sum coloring of bipartite graphs with bounded degree.

Abstract

Artykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.

Authors (4)

Michał Małafiejski dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Krzysztof Giaro prof. dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Robert Janczewski dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Marek Kubale prof. dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie z listy filadelfijskiej
Language:: English
Publication year:: 2004
Bibliographic description:: Małafiejski M., Giaro K., Janczewski R., Kubale M.: Sum coloring of bipartite graphs with bounded degree.// . -., (2004), s.0-0
Verified by:: Gdańsk University of Technology