Complexity of generalized colourings of chordal graphs
Juraj Stacho · Summit (Simon Fraser University) · 2008
The generalized graph colouring problem (GCOL) for a fixed integer k, and fixed classes of graphs P1,...,Pk (usually describing some common graph properties), is to decide, for a given graph G, whether the vertex set of G can be partitioned into sets V1,...,Vk such that, for each i, the induced subgraph of G on Vi belongs to Pi. It can be seen that GCOL generalizes many natural colouring and partitioning problems on graphs. In this thesis, we focus on generalized colouring problems in chordal graphs. The structure of chordal graphs is known to allow solving many difficult combinatorial problems, such as the graph colouring, maximum clique and others, in polynomial, and in many cases in linear time. Our study of generalized colouring problems focuses on those problems in which the sets Pi are characterized by a single forbidden induced subgraph. We show, that for k = 2, all such problems where the forbidden graphs have at most three vertices are polynomial time solvable in chordal graphs, whereas, it is known that almost all of them are NP-complete in general. On the other hand, we show infinite families of such problems which are NP-complete in chordal graphs. By combining a polynomial algorithm and an