×

Visibility properties and forbidden holes in graphs. (English) Zbl 1134.05326

Summary: The aim of this paper is to point out results of the following type: for \(A\) and \(B\) disjoint subsets of vertices in a graph, in some structural conditions, there is a vertex or an edge which sees all the vertices seen by the set \(A\) in \(B\). We shall refer such properties as visibility properties and we shall deduce some applications of these visibility results in the study of structural properties of some particular classes of graphs. More precisely we prove that every maximal clique in a triangulated graph is a cutset or contains a simplicial vertex. Furthermore, a new characterisation of this class of graph is given by restricting the well-known characterization of this class of graphs is given by restricting the well-known characterization of Hayward, Hong and Maffray for weakly triangulated graphs. We characterize the class of \(\overline C_6\)-free graphs without large induced holes and finally we point out some interesting properties of minimal imperfect \(2K_2\)-free graphs.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)