Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 2008

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: nonperfect graphs

Sortuj według:

Ogranicz wyniki do:

On minimal nonperfect graphs

Balińska K., Zwierzyński K.

Studia z Automatyki i Informatyki

2008

T. 33

7-12

A simple graph is perfect if its chromatic number is equal to its clique number; otherwise a graph is called c-nonperfect with c ≥ 1 being the difference between these two invariants. The problem of defining the minimum number of vertices for c-nonperfect graphs as a function of the chromatic number is considered. The upper bound for this problem has been found by constructing sequences of c-nonperfect graphs with the use of Mycielski graphs and the join operation.

Graf prosty jest doskonały, jeżeli jego liczba chromatyczna χ jest równa liczbie klikowej ω. Proponuje się podział grafów, dla których ten warunek nie jest spełniony, na klasy grafów c-niedoskonałych, gdzie c = χ−ω ≥ 1. Rozważa się następujący problem: określić minimalną liczbę nmin(c,χ) wierzchołków grafów c-niedoskonałych, które jednocześnie mają minimalną liczbę krawędzi. Podano regułę konstruowania ciągów grafów Rc(χ), których pierwszymi elementami są grafy Mycielskiego Mχ. Liczba wierzchołków grafów Rc(χ) stanowi górne ograniczenie wartości nmin(c,χ), które w przypadku c = 1 może być dokładne. Wykazano, że grafy R1(χ) i R2(χ) są minimalnie χ-chromatyczne.