Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

1 2007

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grafy pełne k-dzielne

Sortuj według:

Ogranicz wyniki do:

Zwarte końcówkowe kolorowanie grafów

Janczewski R., Małafiejska A., Małafiejski M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2007

T. 13

481-488

W pracy rozważamy nowy model kolorowania grafów, mianowicie zwartego kolorowania końcówek (incydencji) grafu. W klasycznym zwartym kolorowaniu krawędzi grafu staramy się zapewnić, aby zbiór kolorów krawędzi sąsiednich do danego wierzchołka tworzył przedział (zwarty zbiór). Podobny warunek można nałożyć na zbiór kolorów incydencji wychodzących z wierzchołka w końcówkowym kolorowaniu grafu. W pracy, obok zdefiniowania problemu i wskazania potencjalnych zastosowań, wyznaczone zostały oszacowania dolne i górne na wartość szukanego kryterium, ponadto zaproponowane zostały dokładne wartości zwartego końcówkowego indeksu chromatycznego dla wybranych klas grafów: ścieżek, cykli, gwiazd, 2-gwiazd, k-gwiazd, wachlarzy, kół, grafów pełnych, pełnych dwudzielnych oraz pełnych k-dzielnych.

In the paper we present a new model of consecutive incidence graph coloring arising from two previous known models: consecutive (interval) edge coloring and incidence coloring. We formulate the problem and present same applications. We proposed same lower and upper bounds for consecutive incidence chromatic index and constructed polynomial time algorithms solving the problem for same classes of graphs: paths, cycles, stars and k-stars, wheels, fang, complete graphs and complete k-partite graphs.