Generalized Colourings (Matrix Partitions) of Cographs
Tomás Feder, Pavol Hell, Winfried Hochstättler · Birkhäuser Basel eBooks · 2006
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.