List matrix partitions of chordal graphs

详细信息    查看全文

• 作者：Tomá ; s Feder ; Pavol Hell ; Sulamita Klein ; Loana Tito Nogueira and Fá ; bio Protti
• 关键词：Chordal graphs ; List-colourings ; List homomorphisms ; Matrix partitions ; Forbidden subgraph characterizations ; Dichotomy
• 刊名：Theoretical Computer Science
• 出版年：2005
• 出版时间：12 December 2005
• 年：2005
• 卷：349
• 期：1
• 页码：52-66
• 全文大小：265 K

文摘

It is well known that a clique with k+1 vertices is the only minimal obstruction to k-colourability of chordal graphs. A similar result is known for the existence of a cover by ℓ cliques. Both of these problems are in fact partition problems, restricted to chordal graphs. The first seeks partitions into k independent sets, and the second is equivalent to finding partitions into ℓ cliques. In an earlier paper we proved that a chordal graph can be partitioned into k independent sets and ℓ cliques if and only if it does not contain an induced disjoint union of ℓ+1 cliques of size k+1. (A linear time algorithm for finding such partitions can be derived from the proof.)

In this paper we expand our focus and consider more general partitions 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 certain pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix M. Moreover, the vertices of the input chordal graph can be equipped with lists, restricting the parts to which a vertex can be placed. Such (list) partitions generalize (list) colourings and (list) 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 (without lists) that remain NP-complete for chordal graphs. It is not known whether or not each list M-partition problem is NP-complete or polynomial, but it has been shown that each is NP-complete or quasi-polynomial (n^O(logn)). For chordal graphs even this ‘quasi-dichotomy’ is not known, but we do identify large families of matrices M for which dichotomy, or at least quasi-dichotomy, holds.

We also discuss forbidden subgraph characterizations of graphs admitting an M-partition. Such characterizations have recently been investigated for partitions of perfect graphs, and we focus on highlighting the improvements one can obtain for the class of chordal, rather than just perfect, graphs.