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)
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
Sum coloring of bipartite graphs with bounded degree.
- M. Małafiejski,
- K. Giaro,
- R. Janczewski
- + 1 authors
2004
Distributed largest-first algorithm for graph coloring.
- Ł. Kuszner,
- A. Nadolski,
- M. Kubale
- + 1 authors
2004