New charactrisations and algorithmic studies on chordal graphs and k-trees

Abstract

A wealth of literature on graph theory has appeared in the last few centuries. This is to a large extent due to the increase in the applications of graph theory to problems of practical interest. Graph theory is also closely related to many branches of mathematics, such as combinatorics, abstract group theory, and matrix theory. The study of efficient algorithms has been of immense interest to both theoreticians and practitioners alike— to the former because algorithmic approaches often lead to novel theoretical results, and to the latter for obvious reasons. Of the various graph structures which have received wide attention, planar graphs, perfect graphs, regular graphs, bipartite graphs, trees, etc., occupy a special place. Studies on such restricted classes of graphs are well motivated from the following point of view: in typical real-life situations, one does not encounter arbitrary graph structures, but special classes of graphs which are of topical relevance. Such special classes of graphs can be expected to be more easily amenable to problem-solving strategies because of the presence of better structure. Further, such an approach could shed light on the problems for arbitrary graphs. Besides these, on many occasions, restricted graph structures are studied for their intrinsic mathematical interest. In this thesis, some combinatorial and algorithmic results on a class of graphs called the chordal (triangulated) graphs, with emphasis on k-trees, a proper subclass of chordal graphs, are presented. Chordal graphs find applications in the study of evolutionary trees, in facility location and scheduling problems, and in the solution of sparse systems of linear equations. Also, they arise in the study of relational database theory. It is further interesting to note that chordal graphs are a proper subclass of perfect graphs. The class k-trees enjoys a lot of nice properties and has been studied extensively in the literature. The work reported in this thesis is the following: A new Perfect Elimination Ordering (PEO) scheme for chordal graphs called the Maximal Element in Index is introduced. The properties of this scheme with respect to the existing PEO schemes are studied. This leads to new abstract characterizations of k-trees. Using one of these characterizations, a polynomial-time algorithm for counting the PEOs of a k-tree is developed. Then, closed-form expressions for chromatic polynomials of chordal graphs and k-trees are obtained. It is further shown that no other graph structures have these forms of chromatic polynomials. A linear-time algorithm for finding the chromatic polynomial of a chordal graph is given. Finding the chromatic polynomial of an arbitrary graph is discussed, and a new algorithm for computing the same is presented. Finally, a specific partitioning problem (which is NP-complete for general graphs) is shown to have a linear-time algorithm for k-trees. The time complexity of this problem for chordal graphs is open.