On minimal nonperfect graphs

• Autorzy: Balińska K. , Zwierzyński K.

Warianty tytułu

PL

O minimalnych grafach niedoskonałych

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

nonperfect graphs; graphs

PL

grafy niedoskonałe; grafy

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2008
• Tom: T. 33
• Strony: 7--12
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Balińska K.

autor

Zwierzyński K.

• Poznan University of Technology, Institute of Control and Information Engineering, M. Sklodowskiej-Curie Sqr. 5, 60-965 Poznan, Poland,

Bibliografia

• [1] Avis D., On Minimal 5-chromatic Triangle-free Graphs, Journal of Graph Theory, Vol. 3(4), 2006, pp. 397-400.
• [2] Chartrand G., Lesniak L., Graphs and digraphs, Chapman & Hall, London 1996.
• [3] Chvátal V., The Minimality of the Mycielski Graph, Lecture Notes in Math, Vol. 406, Springer, Berlin 1974, pp. 243-246.
• [4] Jensen T., Gordon F., R., Small Graphs with Chromatic Number 5: A Computer Search, Journal of Graph Theory, Vol. 19(1), 2006, pp. 107-116.
• [5] Jensen T., Toft B., Graph Coloring Problems, J. Wiley, New York, 1995.
• [6] Mycielski J., Sur le coloriage des graphs, Colloq. Math., Vol. 3, 1955, pp. 161-162.