×

List partitions of chordal graphs. (English) Zbl 1196.05060

Farach-Colton, Martin (ed.), LATIN 2004: Theoretical informatics. 6th Latin American symposium, Buenos Aires, Argentina, April 5–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21258-2/pbk). Lecture Notes in Computer Science 2976, 100-108 (2004).
Summary: In an earlier paper we gave efficient algorithms for partitioning chordal graphs into \(k\) independent sets and \(\ell\) cliques. This is a natural generalization of the problem of recognizing split graphs, and is NP-complete for graphs in general, unless \(k \leq 2\) and \(\ell \leq 2\). (Split graphs have \(k=\ell=1\).)
In this paper we expand our focus and consider general \(M\)-partitions, also known as trigraph homomorphisms, for the class of chordal graphs. For each symmetric matrix \(M\) over 0, 1, \(*\), the \(M\)-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with some pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix \(M\). Such partitions generalize graph colorings and homomorphisms, and arise frequently in the theory of graph perfection. We show that many \(M\)-partition problems that are NP-complete in general become solvable in polynomial time for chordal graphs, even in the presence of lists. On the other hand, we show that there are \(M\)-partition problems that remain NP-complete even for chordal graphs. We also discuss forbidden subgraph characterizations for the existence of \(M\)-partitions.
For the entire collection see [Zbl 1048.68003].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI