Name
Abstract | ||
|---|---|---|
We consider certain partition problems typified by the following two questions. When is a given graph the join of two k -colourable graphs? When is a given graph the join of a k -colourable graph and a graph whose complement is k -colourable? We focus on the class of chordal graphs, and employ the language of matrix partitions. Our emphasis is on forbidden induced subgraph characterizations. We describe all chordal minimal obstructions to the existence of such partitions; they are surprisingly small and regular. We also give another characterization which yields a more efficient recognition algorithm. By contrast, most of these partition problems are NP-complete if chordality is not assumed. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.disc.2015.06.005 | Discrete Mathematics |
Keywords | Field | DocType |
Graph partition,Graph homomorphism,Forbidden subgraph characterization,Chordal graph,Split graph | Discrete mathematics,Block graph,Outerplanar graph,Combinatorics,Interval graph,Forbidden graph characterization,Chordal graph,Distance-hereditary graph,Cograph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
338 | 12 | 0012-365X |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavol Hell | 1 | 2638 | 288.75 |
| Pei-Lan Yen | 2 | 1 | 0.36 |