On basic chordal graphs and some of its subclasses

PABLO DE CARIA; MARISA GUTIERREZ

Open Door

Congreso; 5 th Latin American Workshop on cliques in Graphs; 2012

Universidad de Buenos Aires

Chordal graphs are defined as those graphs without induced cycles of length greater than or equal to four. Chordal graphs can also be characterized through clique trees. A clique tree of a graph G is a tree T such that its vertices are the cliques of G, and for every vertex v of G, the family Cv of cliques of G containing v induces a subtree of T. A graph is chordal if and only if it has a clique tree.The image of the class of chordal graphs via the clique operator is another well known class, i.e., dually chordal graphs. This class can also be characterized in terms of trees. A compatible tree of a graph G is a spanning tree T such that every clique of G induces a subtree of T. A graph is dually chordal if and only if it has a compatible tree.The clique operator not only relates chordal and dually chordal graphs, but also relates their characteristic trees. More precisely, every clique tree of a chordal graph is a compatible tree of its clique graph. However, it is not necessarily true that a compatible tree of the clique graph is a clique tree of the original graph.A graph G is said to be basic chordal if it is chordal and its clique trees are exactly the compatible trees of K(G). Two of the major results known about basicchordal graphs are a characterization of them that gives a method to efficiently decide whether a graph is basic chordal by looking at its minimal vertex separators,and the fact that the image through the clique operator of the class of basic chordal graphs is the class of dually chordal graphs.Chordal graphs have subclasses such as DV and RDV graphs, that are characterized by the existence of special types of clique trees, namely, DV -clique trees and RDV-clique trees. The images of these classes through the clique operator, i.e., dually DV and dually RDV graphs, are in turn characterized by the existence ofspecial types of compatible trees, namely, DV -compatible trees and RDV -compatible trees. In this context, basic DV and basic RDV graphs can be defined similarly tobasic chordal graphs.In this work, basic DV and basic RDV graphs are introduced and characterized, and their clique graphs are studied.