Links

Tools

Export citation

Search in Google Scholar

When are chordal graphs also partition graphs?

Journal article published in 1997 by Carreen Anbeek Duane, Kevin Mca, Jack Robertson
This paper was not found in any repository; the policy of its publisher is unknown or unclear.
This paper was not found in any repository; the policy of its publisher is unknown or unclear.

Full text: Unavailable

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

A general partition graph (gpg) is an intersection graph G on a set S so that for every maximal independent set M of vertices in G, the subsets assigned to the vertices in M partition S. These graphs have been characterized by the presence of special clique covers. The Triangle Condition T for a graph G is that for any maximal independent set M and any edge uv in G M, there is a vcrtex W E M so that uvw is a triangle in G. Condition T is necessary but not sufficient for a graph to be a gpg and a computer search has found the smallest ten counterexamples, one with nine vertices and nine with ten verticcs. Any non-gpg satisfying Condition T is shown to induce a required subgraph on six vertices, and a method of generating an infinite class of such graphs is described. The main result establishes the equivalence of the following conditions in a chordal graph G: (i) G is a gpg (ii) G satisfies Condition T (iii) every edge in G is in an end-clique. The result is extended to a larger class of graphs.