Some Problems On Intersection Graph Theory

If every vertex of a graph is in correspondence with an element of a family of sets S such that two different vertices are adjacent in G if and only if the intersection of their corresponding sets is not empty, then we call G is the intersection graph of S. Intersection graphs have real application to topics like biology, computing, matrix analysis and statistics. The intersection graph theory develops quickly in recent twenty years just because of it wide applications. This thesis concentrates on some problems of the intersection graph theory. We study the economical intersection representations of graphs with different constraints , the intersection numbers and the problem of unique representability. We also give new characterizations for some important classes of intersection graphs.This thesis consists six chapters.The first chapter is devoted to the summarization of the dissertation. We introduce the background and the situations around our research and also present a list of our main results.In the second chapter, we study the problem of economical set representations without any constraints. The determination of the intersection number of a graph is NP-hard in general[54]. We can give some estimations of intersection number by fractional intersection number. For the graph with the same intersection number and fractional intersection number, we can determine the value of its intersection number in polynominal time. Scheinerman and Trenk [90] have shown that if a graph G is chordal then i(G) = i_f(G) holds. We show that if the edge clique graph of a graph G is weakly θ-perfect then it satisfies i(G) = i_f(G), which is a generalization of the work of Scheinerman and Trenk. As some applications of this result we characterize those graphs whose edge clique graphs are perfect from different points of view. In particular, we identify a hierarchy of those graph classes, we present a greedy algorithm...