Which claw-free graphs are perfectly orderable?
type: Item
instance of: scholarly article
title: Which claw-free graphs are perfectly orderable?
zbMATH Open document ID: 0783.05086
DOI: 10.1016/0166-218X(93)90221-9
author: Vašek Chvátal
published in: Discrete Applied Mathematics
publication date: 1994-03-13T00:00:00Z
review text: Given an undirected graph it is perfectly orderable (p.o.) if it permits a perfect linear order \(<\) on the vertices, i.e., one such that no chordless path with vertices \(\{a,b,c,d\}\) and edges \(\{ab,bc,cd\}\) has \(a<b\) and \(d<c\). Since p.o. graphs are both interesting graphs and since recognizing them is NP-complete, determining subclasses (along with suitable algorithms) which may be determined in polynomial time is quite useful. P.o. line-graphs have been so characterized by the author. The class of p.o. complements of bipartite graphs has also been among classes characterized in this manner. A claw is an induced subgraph on \(V=\{x,a,b,c\}\) with edges \(E=\{xa,xb,xc\}\). It is shown that line-graphs and complements of bipartite graphs are claw-free. Furthermore, a complete characterization of p.o. claw-free graphs is provided by describing nine infinite families of forbidden induced subgraphs and in the development of the proof of this important theorem the wherewithal for a polynomial time recognition algorithm on the class of claw-free graphs is also created. As a byproduct a generalization of the characterization of totally balanced matrices found by Anstee and Farber, Edmonds and Lubiw, Kolen and Sakarovitch is immediate via the observation that this characterization is precisely the case of complements of bipartite graphs in the present setting.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 06F99
zbMATH DE Number: 428102
zbMATH Keywords: perfectly orderable
zbMATH Keywords: perfect linear order
zbMATH Keywords: NP-complete
zbMATH Keywords: claw
zbMATH Keywords: line- graphs
zbMATH Keywords: complements of bipartite graphs
zbMATH Keywords: claw-free graphs
zbMATH Keywords: characterization
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Characterizations of totally balanced matrices
cites work: Which line-graphs are perfectly orderable?
cites work: Four classes of perfectly orderable graphs
cites work: Recognizing claw-free perfect graphs
cites work: On rigid circuit graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Bipartable graphs
cites work: On brittle graphs
cites work: \(P_ 4\)-comparability graphs
cites work: Some classes of perfectly orderable graphs
cites work: Totally-Balanced and Greedy Matrices
cites work: Q3880849
cites work: Doubly Lexical Orderings of Matrices
cites work: On the complexity of recognizing perfectly orderable graphs
cites work: An algorithm for finding clique cut-sets
description: scientific article; zbMATH DE number 428102