On-line P-coloring of graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

On-line P-coloring of graphs

Abstrakt

For a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line P-coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy P-coloring. A class of graphs for which a greedy algorithm always generates optimal P-colorings for the property P = K3-free is given.

Cytowania

  • 2

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
Discussiones Mathematicae Graph Theory nr 26, wydanie 3, strony 389 - 401,
ISSN: 1234-3099
Język:
angielski
Rok wydania:
2006
Opis bibliograficzny:
Borowiecki P.: On-line P-coloring of graphs// Discussiones Mathematicae Graph Theory. -Vol. 26, iss. 3 (2006), s.389-401
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1331
Weryfikacja:
Politechnika Gdańska

wyświetlono 24 razy

Publikacje, które mogą cię zainteresować

Meta Tagi