An algorithm for colouring perfect planar graphs
type: Item
instance of: scholarly article
title: An algorithm for colouring perfect planar graphs
zbMATH Open document ID: 0684.05019
DOI: 10.1016/0020-0190(89)90075-6
author: Iain Stewart
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: A graph G is perfect if for every induced subgraph \(G'\) of G the chromatic number of \(G'\) equals the size of the largest clique of \(G'\). This paper uses the Lipton-Tarjan separator algorithm for planar graphs to construct an \(O(n^{3/2})\) algorithm to minimally color a perfect planar graph. A set of vertices C is called a separator if the n vertices of G can be partitioned into sets A, B, C such that no edge of G joins a vertex of A with a vertex of B and further neither A nor B contains more than 2n/3 vertices. The Lipton-Tarjan algorithm finds a separator of size at most \((8n)^{1/2}\) in a planar graph in linear time.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4120190
zbMATH Keywords: perfect graph
zbMATH Keywords: planar graphs
zbMATH Keywords: perfect planar graph
reviewed by: Alan C. Tucker
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90075-6
OpenAlex ID: W2043646993
cites work: On the Problem of Partitioning Planar Graphs
cites work: Q3328583
cites work: The strong perfect graph conjecture for toroidal graphs
cites work: Some simplified NP-complete graph problems
cites work: A Separator Theorem for Planar Graphs
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: Perfect Graphs and an Application to Optimizing Municipal Services
cites work: The Strong Perfect Graph Conjecture for Planar Graphs
cites work: Critical perfect graphs and perfect 3-chromatic graphs
cites work: An O(N2) algorithm for coloring perfect planar graphs
description: scientific article; zbMATH DE number 4120190