Published in

Elsevier, Discrete Mathematics, 1-3(113), p. 131-142, 1993

DOI: 10.1016/0012-365x(93)90512-r

Links

Tools

Export citation

Search in Google Scholar

A characterization and hereditary properties for partition graphs

Journal article published in 1993 by Kevin McAvaney, Jack Robertson, Duane DeTemple
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

A general partition graph 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. It is shown that such graphs are characterized by there existing a clique cover of G so that every maximal independent set has a vertex from each clique in the cover. A process is described showing how to construct a partition graph with certain prescribed graph theoretic invariants starting with an arbitrary graph with similar invariants. Hereditary properties for various graph products are examined. It is also shown that partition graphs are preserved by removal of any vertex whose closed neighborhood properly contains the closed neighborhood of some other vertex.