Powers of asteroidal triple-free graphs with applications

Jou Ming Chang, Chin Wen Ho, Ming Tat Ko

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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 Gk (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.

Original languageEnglish
Pages (from-to)161-173
Number of pages13
JournalArs Combinatoria
Volume67
StatePublished - Apr 2003

Keywords

  • Asteroidal triple
  • At-free graphs
  • Cocomparability graphs
  • Powers of graphs

Fingerprint

Dive into the research topics of 'Powers of asteroidal triple-free graphs with applications'. Together they form a unique fingerprint.

Cite this