CLAW-FREENESS, 3-HOMOGENEOUS SUBSETS OF A GRAPH AND A RECONSTRUCTION PROBLEM

Abstract. We describe Forb{K1,3,K1,3}, the class of graphs G such that G and its complement 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 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+̇G ′ of two graphs G and G ′ giving the same hypergraph. We indicate the role of this latter description in a reconstruction problem of graphs up to complementation. 1. Results and motivation Our notations and terminology mostly follow [3]. The graphs we consider in this paper are undirected, simple and have no loop. That is a graph is a pair G: = (V, E), where E is a subset of [V]2, the set of 2-element subsets of V. Elements of V are the vertices of G and elements of E its edges. We denote by V (G) the vertex set of G and by E(G) its edge set. We look at members of [V]2 as unordered pairs o