Academic Commons

Theses Doctoral

Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems

Penev, Irena

Given a graph G, χ(G) denotes the chromatic number of G, and ω(G) denotes the clique number of G (i.e. the maximum number of pairwise adjacent vertices in G). A graph G is perfect provided that for every induced subgraph H of G, χ(H) = ω(H). This thesis addresses several problems from the theory of perfect graphs and generalizations of perfect graphs. The bull is a five-vertex graph consisting of a triangle and two vertex-disjoint pendant edges; a graph is said to be bull-free provided that no induced subgraph of it is a bull. The first result of this thesis is a structure theorem for bull-free perfect graphs. This is joint work with Chudnovsky, and it first appeared in [12]. The second result of this thesis is a decomposition theorem for bull-free perfect graphs, which we then use to give a polynomial time combinatorial coloring algorithm for bull-free perfect graphs. We remark that de Figueiredo and Maffray [33] previously solved this same problem, however, the algorithm presented in this thesis is faster than the algorithm from [33]. We note that a decomposition theorem that is very similar (but slightly weaker) than the one from this thesis was originally proven in [52], however, the proof in this thesis is significantly different from the one in [52]. The algorithm from this thesis is very similar to the one from [52]. A class G of graphs is said to be χ-bounded provided that there exists a function f such that for all G in G, and all induced subgraphs H of G, we have that χ(H) ≤ f(ω(H)). χ-bounded classes were introduced by Gyarfas [41] as a generalization of the class of perfect graphs (clearly, the class of perfect graphs is χ-bounded by the identity function). Given a graph H, we denote by Forb*(H) the class of all graphs that do not contain any subdivision of H as an induced subgraph. In [57], Scott proved that Forb*(T) is χ-bounded for every tree T, and he conjectured that Forb*(H) is χ-bounded for every graph H. Recently, a group of authors constructed a counterexample to Scott's conjecture [51]. This raises the following question: for which graphs H is Scott's conjecture true? In this thesis, we present the proof of Scott's conjecture for the cases when H is the paw (i.e. a four-vertex graph consisting of a triangle and a pendant edge), the bull, and a necklace (i.e. a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge). This is joint work with Chudnovsky, Scott, and Trotignon, and it originally appeared in [13]. Finally, we consider several operations (namely, "substitution," "gluing along a clique," and "gluing along a bounded number of vertices"), and we show that the closure of a χ-bounded class under any one of them, as well as under certain combinations of these three operations (in particular, the combination of substitution and gluing along a clique, as well as the combination of gluing along a clique and gluing along a bounded number of vertices) is again χ-bounded. This is joint work with Chudnovsky, Scott, and Trotignon, and it originally appeared in [14].



  • thumnail for Penev_columbia_0054D_10665.pdf Penev_columbia_0054D_10665.pdf application/pdf 916 KB Download File

More About This Work

Academic Units
Thesis Advisors
Chudnovsky, Maria
Ph.D., Columbia University
Published Here
May 1, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.