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

2008/12/06 by Maurice Pouzet, Pouzet, Maurice, Hamza Si Kaddour +1
Mathematics · #04A05 #05C60 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:04A05 #msc:05C60

paper · pdf · doi:10.48550/arxiv.0812.1278

10 pages, 2 figures

arxiv created 2008/12/06 · arxiv updated 2009/12/01

Abstract

We describe Forb\K_1,3, K_1,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 or isolated vertices, and of the complements of these graphs. Considering the hypergraph \mathcal H ⁽³⁾(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.

Related

• Graph Reconstruction from Connected Triples
• Reconstruction and Edge Reconstruction of Triangle-free Graphs
• Graph Reconstruction with Connectivity Queries
• Degree sum conditions and a 2-factor with a bounded number of cycles in claw-free graphs
• Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ