Sequential colorings and perfect graphs
type: Item
instance of: scholarly article
title: Sequential colorings and perfect graphs
zbMATH Open document ID: 0930.05041
DOI: 10.1016/S0166-218X(99)00026-8
author: Frédéric Maffray
author: Myriam Preissmann
published in: Discrete Applied Mathematics
publication date: 2000-02-09T00:00:00Z
review text: The sequential-X algorithm is an algorithm for coloring the vertices of graph \(G\) which, given an ordering \(v_1,\dots, v_n\), colors the vertices of \(G\) greedily using the idea of bichromatic interchange. Clearly, every graph has an ordering such that every execution of the sequential-X algorithm on this ordering provides a chromatic coloring. An ordering of the vertices is called sequential-X perfect if for each induced ordered subgraph the sequential-X perfect algorithm produces an optimal coloring. Furthermore, a vertex \(v\) of \(G\) is called excellent if it does not lie in an odd hole of \(G\) and its neighborhood contains no induced \(P_4\), \(3K_2\) or \(P_3+ K_2\). An ordering \(v_1,\dots, v_n\) of the vertices of graph \(G\) is called excellent if \(v_i\) is excellent in the subgraph of \(G\) induced by \(v_1,\dots, v_i\). The authors show that the sequential-X algorithm when applied to \(G\) with an excellent ordering provides a coloring with \(\omega(G)\) colors. This implies that any excellent ordering is sequential-X perfect. They conclude with a polynomial algorithm which, given a graph \(G\), either answers that \(G\) has no excellent ordering or gives an \(\omega(G)\)-coloring (even if \(G\) has no excellent ordering).
reviewed by: Marek Kubale
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1309394
zbMATH Keywords: perfect graphs
zbMATH Keywords: chromatic number
zbMATH Keywords: coloring
zbMATH Keywords: bichromatic interchange
MaRDI profile type: Publication
cites work: Q4099676
cites work: Q3347930
cites work: A Linear Recognition Algorithm for Cographs
cites work: On rigid circuit graphs
cites work: Q4198056
cites work: Q3216686
cites work: Q4142699
cites work: A characterization of perfect graphs
cites work: A generalization of simplicial elimination orderings
cites work: On a property of the class of n-colorable graphs
cites work: Coloring perfect \((K_ 4\)-e)-free graphs
full work available at URL: s0166-218x(99)00026-8
OpenAlex ID: W1982847918
description: scientific article; zbMATH DE number 1309394