Join colourings of chordal graphs

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 lang...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2015-12, Vol.338 (12), p.2453-2461
Main Authors: Hell, Pavol, Yen, Pei-Lan
Format: Article
Language:English
Subjects:
Algorithms
Chordal graph
Colouring
Complement
Forbidden subgraph characterization
Graph homomorphism
Graph partition
Graphs
Mathematical analysis
Obstructions
Partitions
Recognition
Split graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2015.06.005