Reducing prime graphs and recognizing circle graphs
type: Item
instance of: scholarly article
title: Reducing prime graphs and recognizing circle graphs
zbMATH Open document ID: 0666.05037
DOI: 10.1007/BF02579301
author: André Bouchet
published in: Combinatorica
publication date: 1987-01-01T00:00:00Z
review text: A reduction theorem for prime (simple) graphs in \textit{W. H. Cunningham}'s sense [SIAM J. Algebraic Discrete Methods 3, 214-228 (1982; Zbl 0497.05031)] is presented. It says that every prime graph of order \(n>5\) contains a smaller prime graph of order n-1. As an application a polynomial algorithm for recognizing circle graphs in \((n^ 5)\) time is presented.
reviewed by: Maciej M. Sysło
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 4089581
zbMATH Keywords: reduction theorem
zbMATH Keywords: prime graph
MaRDI profile type: Publication
cites work: Q3097395
cites work: Q5635462
cites work: Isotropic systems
cites work: Graphic presentations of isotropic systems
cites work: Decomposition of Directed Graphs
cites work: Q4156464
cites work: A characterization of circle graphs
cites work: Q3328583
cites work: Q3934405
cites work: Connectivity in Matroids
cites work: Lectures on matroids
cites work: Q3708048
cites work: Recognizing circle graphs in polynomial time
cites work: Reconnaissance des graphes de cordes
full work available at URL: https://doi.org/10.1007/bf02579301
OpenAlex ID: W2015381896
description: scientific article; zbMATH DE number 4089581