On generating graphs with bounded degree and a given chromatic number

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

Warianty tytułu

PL

Generowanie grafów z ograniczonym stopniem o danej liczbie chromatycznej

• Języki publikacji: EN

Abstrakty

EN

The distribution of the chromatic number χ of random graphs with bounded degree (f-graphs) of order n generated in the G (n, f) model is studied. Introducing the predominant chromatic number results in determining values of parameters f and n that can be chosen in this model to generate graphs with a given χ.

PL

Rozważa się zależność rozkładu prawdopodobieństwa liczby chromatycznej χ grafów losowych G (n, f) od parametrów modelu n (liczba wierzchołków) i f (ograniczenie stopnia). Grafy generowane w tym modelu są to maksymalne (krawędziowo) grafy z ograniczonym stopniem (f-grafy) odpowiadające stanom końcowym losowego procesu grafowego RfGP. W obszernym eksperymencie obliczeniowym wykorzystano algorytm generowania grafów G (n, f) i wprowadzając pojęcie dominującej liczby chromatycznej określono wartości f i n, przy których generowane są f-grafy o danej wartości χ.

Słowa kluczowe

EN

generating graphs; chromatic number

PL

generowanie grafów; liczba chromatyczna

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

Twórcy

autor

Balińska K.

autor

Quintas L.

autor

Zwierzyński K.

• Poznan University of Technology, pl. M. Sklodowskiej-Curie 5, 60-965 Poznan, Poland,

Bibliografia

• [1] Achlioptas D., Naor A., The Two Possible Values of the Chromatic Number of a Random Graph, Annals of Mathematics, 162 (2005), pp. 1335-1351.
• [2] Balińska K. T., Quintas L. V., Random Graphs with Bounded Degree, Publ. House , Poznań Univ. of Techn. Poznań (2006).
• [3] Balińska K. T., Quintas L. V., Zwierzyński K. T., The Chromatic Number of Edge Maximal Graphs with Bounded Degree, CSC Report No 545, Poznań Univ. of Techn., Poznań (2007), pp. 1-30.
• [4] Brooks R. L., On Colouring the Nodes of a Network , Proc. Cambridge Phios. Soc. 37 (1941), pp. 194-197.
• [5] Kennedy J. W., Quintas L. V., Probability Models for Random f-graphs, In: Combinatorial Mathematics (New York, 1985), Ann. N. Y. Acad. Sci., 555, (1989), pp. 248-261.
• [6] Sysło M. M., Deo N. Kowalik J. S., Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall (1983).
• [7] The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/squences/