Paper Info
Title
Recognizing Brittle Graphs - Remarks On A Paper Of Hoang And Khouzam
Abstract
A graph is perfect if the size of the maximum clique equals the chromatic number in every induced subgraph. Chvatal defined a subclass of perfect graphs known as perfectly-orderable graphs, which have the property that a special ordering on the vertices leads to a trivial algorithm to find an optimum coloring. He also identified a subclass of the perfectly-orderable graphs, which he called brittle graphs, characterized by the property that every nonempty induced subgraph contains a vetex x such that x is either not an endpoint of a P4 or is not in the middle of a P4. The brittle graphs were studied in a recent paper of Honag and Khouzam [J. Graph Theory 12 (1988) 391-404] where the authors gave alternate characterizations one of which leads to an O(n3m) time recognition algorithm for brittle graphs, where n is the number of vertices and m is the number of edges. In contrast, no polynomial-time recognition algorithms are known for either perfect graphs or perfectly-orderable graphs. We point out that an O(n2m) time recognition algorithm for brittle graphs can be derived from Chvatal's definition, and we present a more complicated O(m2) time recognition algorithm.
Year
DOI
Venue
1991
10.1016/0166-218X(91)90030-Z
DISCRETE APPLIED MATHEMATICS
Field
DocType
Volume
Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Clique-sum,Cograph,Pathwidth,1-planar graph,Mathematics,Split graph,Strong perfect graph theorem
Journal
31
Issue
ISSN
Citations 
1
0166-218X
7
PageRank 
References 
Authors
0.61
3
1
Name
Order
Citations
PageRank
Alejandro A. Schäffer1827136.66