## 摘要

An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power G^{k} (k ≥ 2) of an AT-free graph G is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs.

原文 | ???core.languages.en_GB??? |
---|---|

頁（從 - 到） | 161-173 |

頁數 | 13 |

期刊 | Ars Combinatoria |

卷 | 67 |

出版狀態 | 已出版 - 4月 2003 |