Paper Info
Title
On Subfamilies of AT-Free Graphs
Abstract
We introduce two subfamilies of AT-free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs 驴 path orderable graphs 驴 strong asteroid free graphs 驴 AT-free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP-complete whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.
Year
DOI
Venue
2001
10.1007/3-540-45477-2_22
WG
Keywords
Field
DocType
at-free graphs,cocomparability graph,at-free graph,new class,recognition question,recognition problem,natural generalization,comparability graph,path orderable graph,fundamental work,strong asteroid free graph,polynomial time,linear order
Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Clique-sum,Chordal graph,Cograph,Pathwidth,Longest path problem,Mathematics,Maximal independent set
Conference
ISBN
Citations 
PageRank 
3-540-42707-4
3
0.39
References 
Authors
4
4
Name
Order
Citations
PageRank
Köhler Ekkehard142039.30
Derek G. Corneil21397218.67
Stephan Olariu344456.26
Lorna Stewart436128.05