Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423891 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
Matrix partition problems generalize graph colouring and homomorphism problems and occur frequently in the study of perfect graphs. It is difficult to decide, even for a small matrix M, whether the M-partition problem is polynomial time solvable or NP-complete (or possibly neither), and whether M-partitionable graphs can be characterized by a finite set of forbidden induced subgraphs (or perhaps some other first order condition). We discuss these problems for the class of chordal graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomás Feder, Pavol Hell, Shekoofeh Nekooei Rizi,