On efficient coloring of chordless graphs

Robert Janczewski; Michał Małafiejski

doi:10.7494/dmms.2009.3.2.5

On efficient coloring of chordless graphs

Abstract

Artykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (2)

Cite as

Full text

download paper

downloaded 9 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.7494/dmms.2009.3.2.5
License: open in new tab

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

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: Decision Making in Manufacturing and Services no. 3, pages 5 - 14,
ISSN: 1896-8325
Language:: English
Publication year:: 2009
Bibliographic description:: Janczewski R., Małafiejski M.: On efficient coloring of chordless graphs// Decision Making in Manufacturing and Services. -Vol. 3., (2009), s.5-14
DOI:: Digital Object Identifier (open in new tab) 10.7494/dmms.2009.3.2.5
Verified by:: Gdańsk University of Technology