Polynomial time computability of some graph parameters for superclasses of perfect graphs
type: Item
instance of: scholarly article
title: Polynomial time computability of some graph parameters for superclasses of perfect graphs
zbMATH Open document ID: 1264.05132
DOI: 10.1504/IJMOR.2012.046687
author: Arnaud Pêcher
author: Annegret K. Wagler
published in: International Journal of Mathematics in Operational Research
publication date: 2012-11-16T00:00:00Z
review text: \textit{X. Zhu} [J. Graph Theory 48, No. 3, 186--209 (2005; Zbl 1071.05037)] defined the circular chromatic number and the circular clique number of a graph and introduced circular-perfect graphs similar to perfect graphs. So far we do not have polynomial time algorithms computing these parameters, even if the inputs are restricted to circular perfect graphs. The authors restrict the inputs further to graphs \(G=(V,E)\) where \(G[N(v)]\) is perfect for every vertex \(v \in V\), and use polyhedral arguments to obtain polynomial time algorithms computing weighted versions of the circular chromatic number and the circular clique number.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C17
zbMATH DE Number: 6108303
zbMATH Keywords: circular-perfect graph
zbMATH Keywords: polytope
zbMATH Keywords: circular clique
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6108303