Kolorowanie hipergrafów

• Autorzy: Kubale M. , Obszarski P. , Piwakowski K.

Warianty tytułu

EN

Hypergraph coloring

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

Hipergraf to struktura stanowiąca pewne uogólnienie grafa. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności, złożoności oraz wskażemy zastosowania.

EN

A hypergraph is a generalization of a graph in which the edges may contain any number of vertices. In this paper we discuss a few models of hypergraph coloring, namely: edge coloring, vertex coloring and mixed coloring. We present some basic properties of these models, complexity and their possible applications.

Słowa kluczowe

PL

hipergraf; kolorowanie hipergrafów; kolorowanie krawędzi; kolorowanie wierzchołków; kolorowanie CD; CD

EN

hypergraph; hypergraph coloring; edge colouring; vertex coloring; mixed coloring; CD

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 83--90
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Kubale M.

autor

Obszarski P.

autor

Piwakowski K.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

Bibliografia

• 1. Berge C: On the chromtaic index of linear hypergraph and the Chvatal conjecture. Combinatorial Mathematics: Proceedings of the Third International Conference, Ann. New York Acad. Sci, New York 1985, p. 40-44.
• 2. Chang W. L, Lawler E. L.: Edge coloring of hypergraphs and a conjecture of Erdös. Faber and Lovasz. Combinatorica 8, 1988, p. 293-295.
• 3. Dvořák T.: Chromatic index of hypergraphs and Shannon's theorem. Europ. J. Combinatorics 21, 2000, p. 585-591.
• 4. Erdös P.: Problems and results in graph theory and combinational analysis. Proc. Fifth British Comb. Conf, Congr. Numeratium 15 Winnipeg: Utilitas Mathematica, 1976, p. 169-192.
• 5. Fiedorowicz A.: Kolorowanie hipergrafów a problem składowania odpadów, praca magisterska napisana na Uniwersytecie Zielonogórskim.
• 6. Furedi Z.: The chromatic index of simple hypergraphs. Graphs and Combinatorics 2, 1986, p. 89-92.
• 7. Giaro K., Kubale M.: Chromatic scheduling of 1- and 2-processor UET tasks on dedicated machines with availability constrains. Lecture Notes in Computer Science 3911, 2006.
• 8. Jiang T., Mubayi D., Tuza Z., Voloshin V., West D.: The chromatic spectrum of mixed hypergraphs. Graphs and Combinatorics 18, 2002, p. 309-318.
• 9. Kobler D., Kündgen A.: Graps in the chromatic spectrum of face-constrained plane graphs. Electron J. Combin. 8, 2001, N3.
• 10. Král D., Kratochvil J., Proskurowski A., Voss H.: Coloring mixed hypertrees. Lecture Notes in Computer Science 1928, 2000, p. 279-289.
• 11. Král D., Kratochvil J., Proskurowski A., Voss H.: Mixed hypercacti. Discrete Mathematics 286, 2004, p. 99-113.
• 12. Krivelevich M., Sudakov B.: Approximate coloring of uniform hypergraphs. Journal of Algorithms 49, 2003, p. 2-12.
• 13. Lovász L.: Coverings and colorings of hypergraphs. Proc. 4th S.E. Conf. on Combinatorics, Graph Theory and Computing, Utilitas Math., 1973, p. 3-12.
• 14. Obszarski P., Dąbrowski J.: Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej, przyjęte do druku, 2006.
• 15. Phelps K., Rödl V.: On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems. Combinatorica 4 ,1984, p. 79-88.
• 16. Voloshin V. I.: Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. American Mathematical Society, 2002.