×

Generalized colouring (matrix partitions) of cographs. (English) Zbl 1114.05060

Bondy, Adrian (ed.) et al., Graph theory in Paris. Proceedings of a conference, GT04, in memory of Claude Berge, Paris, France, July 2004. Basel: Birkhäuser (ISBN 3-7643-7228-1/hbk). Trends in Mathematics, 149-167 (2007).
Summary: 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.
For the entire collection see [Zbl 1098.05001].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite