Title of article :
Matrix partitions of perfect graphs Original Research Article
Author/Authors :
Tomas Feder ، نويسنده , , Pavol Hell، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Pages :
11
From page :
2450
To page :
2460
Abstract :
Given a symmetric m by m matrix M over image, the M-partition problem asks whether or not an input graph G can be partitioned into m parts corresponding to the rows (and columns) of M so that two distinct vertices from parts i and j (possibly with image) are non-adjacent if image, and adjacent if image. These matrix partition problems generalize graph colourings and homomorphisms, and arise frequently in the study of perfect graphs; example problems include split graphs, clique and skew cutsets, homogeneous sets, and joins. In this paper we study M-partitions restricted to perfect graphs. We identify a natural class of ‘normal’ matrices M for which M-partitionability of perfect graphs can be characterized by a finite family of forbidden induced subgraphs (and hence admits polynomial time algorithms for perfect graphs). We further classify normal matrices into two classes: for the first class, the size of the forbidden subgraphs is linear in the size of M; for the second class we only prove exponential bounds on the size of forbidden subgraphs. (We exhibit normal matrices of the second class for which linear bounds do not hold.) We present evidence that matrices M which are not normal yield badly behaved M-partition problems: there are polynomial time solvable M-partition problems that do not have finite forbidden subgraph characterizations for perfect graphs. There are M-partition problems that are NP-complete for perfect graphs. There are classes of matrices M for which even proving ‘dichotomy’ of the corresponding M-partition problems for perfect graphs—i.e., proving that these problems are all polynomial or NP-complete—is likely to be difficult.
Keywords :
Matrix partition , Trigraph homomorphism , NP-complete problem , Forbidden subgraph characterization , MM-partition , Perfect graph , Polynomial time algorithm
Journal title :
Discrete Mathematics
Serial Year :
2006
Journal title :
Discrete Mathematics
Record number :
948098
Link To Document :
بازگشت