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

Abstract

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.

Citations

3

CrossRef
0

Web of Science
4

Scopus

Author (1)

Adrian Kosowski dr inż.

Cite as

Full text

download paper

downloaded 34 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.03.008
License: Copyright (2009 Elsevier B.V.)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: DISCRETE APPLIED MATHEMATICS no. 157, pages 2552 - 2554,
ISSN: 0166-218X
Language:: English
Publication year:: 2009
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.03.008
Verified by:: Gdańsk University of Technology