Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Generalized Colourings (Matrix Partitions) of Cographs
verfasst von : Tomás Feder, Pavol Hell, Winfried Hochstättler
Erschienen in: Graph Theory in Paris
Verlag: Birkhäuser Basel
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Ordinary colourings of cographs are well understood; we focus on more general colourings, known as matrix partitions. We show that all matrix partition problems for cographs admit polynomial time algorithms and forbidden induced subgraph characterizations, even for the list version of the problems. Cographs are the largest natural class of graphs that have been shown to have this property. We bound the size of a biggest minimal
M
obstruction cograph
G
, both in the presence of lists, and (with better bounds) without lists. Finally, we improve these bounds when either the matrix
M
, or the cograph
G
, is restricted.