A note on the strength and minimum color sum of bipartite graphs - Publication - Bridge of Knowledge

Search

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

Cite as

Full text

download paper
downloaded 27 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.)

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

seen 66 times

Recommended for you

Meta Tags