Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem

Abstract

We describe $\mathrm{Forb}\{K_{1,3},\overline{K_{1,3}}\}$, the class of graphs $G$ such that $G$ and its complement $\bar{G}$ are claw-free. With few exceptions, it is made of graphs whose connected components consist of cycles of length at least 4, paths, and of the complements of these graphs. Considering the hypergraph ${\mathcal{H}}^{(3)}(G)$ made of the 3-element subsets of the vertex set of a graph $G$ on which $G$ induces a clique or an independent subset, we deduce from above a description of the Boolean sum $G\dot{+}{G}^{\prime }$ of two graphs $G$ and $G^{\prime }$ giving the same hypergraph. We indicate the role of this latter description in a reconstruction problem of graphs up to complementation.

This paper has no DOI, published version available at: http://cdm.ucalgary.ca/cdm/index.php/cdm/article/view/189