O złożoności problemów F-dekompozycji grafów>

• Autorzy: Jesse-Józefczyk K.

Warianty tytułu

EN

On the complexity of problems of F-decomposition of graphs

• Języki publikacji: PL

Abstrakty

PL

W pracy tej zostało przedstawionych kilka problemów związanych z F-dekompozycją grafów i jej złożonością obliczeniową. F-dekompozycję będziemy utożsamiać z częściowym dwukolorowaniem wierzchołków grafu. Kolorowanie to musi spełniać kilka warunków, z których najważniejszym jest to, aby krawędzie czerwono-niebieskie tworzyły zbiór rozspajający dany graf oraz wraz z wierzchołkami w tych kolorach nie indukowały pewnych grafów dwudzielnych.

EN

This paper presents selected problems concerning F-decomposition of graphs and its complexity. We identify the F-decomposition with a colouring of vertices of a graph. This colouring must satisfy several conditions and the most important of them is that the red-blue edges must be a cut-set of the given graph and together with the vertices coloured red and blue they cannot induce some bipartite graphs.

Słowa kluczowe

PL

F-dekompozycja grafów; kolorowanie grafów; dwukolorowanie wierzchołków grafów

EN

F-decomposition graphs; colouring graphs; vertices colouring graphs; bipartite graphs

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 419--426
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Jesse-Józefczyk K.

• Zakład Matematyki Dyskretnej i Informatyki, Uniwersytet Zielonogórski

Bibliografia

• [1] Spinrad J., Rusu 1.: Forbidden subgraph decomposition, Discrete Math. 247, 2002, s. 159-168.
• [2] Chvatal V.: Recognizing decomposable graphs, J. Graph Theory 8, 1984, s. 51-53.
• [3] Moshi A.M.: Matching cutsets in graphs, J. Graph Theory 13, 1989, s. 527-536.
• [4] Borowiecki M., Jesse-Józefczyk K.: On F-decomposition of graphs, w opracowaniu.
• [5] Boiron P., Sopena E., Vignal L, Acyclic Improper Colourings of Graphs with bounded degree, Discrete Math. And Comput. Sci. 49,1997, s. 1-10.
• [6] Cunningham M.: Decomposition of directed graphs, SIAM Journal of Algebraic and Discrete Methods 3, 1982, s. 214-228.
• [7] Rao M.: Coloring a graph using split decomposition, Lecture Notes in Computer Science 3353, 2004, s. 129-141.
• [8] Bixby R.: A composition for perfect graphs, Annals of Discrete Math. 21, 1984, s. 221-224.
• [9] Spinrad J.: Recognition of circle graph, Journal of Algorithms 16, 1994, s. 264-282.
• [10] Cicerone S., Di Sterano D.: On the extension of bipartite graphs to parity graphs, Discrete Applied Math. 95, 1999, s.181-195.
• [11] Dahlhaus E. Efficient parallel and linear time sequential split decomposition, Lecture Notes in Computer Science 880, 1994, s. 171-180.