Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems
 Title:

Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems
 Author(s):

Penev, Irena
 Thesis Advisor(s):

Chudnovsky, Maria
 Date:

2012
 Type:

Dissertations
 Department(s):

Mathematics
Industrial Engineering and Operations Research
 Persistent URL:

http://hdl.handle.net/10022/AC:P:13082
 Notes:

Ph.D., Columbia University.
 Abstract:

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 fivevertex graph consisting of a triangle and two vertexdisjoint pendant edges; a graph is said to be bullfree provided that no induced subgraph of it is a bull. The first result of this thesis is a structure theorem for bullfree 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 bullfree perfect graphs, which we then use to give a polynomial time combinatorial coloring algorithm for bullfree 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 fourvertex 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].
 Subject(s):

Mathematics
 Item views
 990
 Metadata:

text  xml
 Suggested Citation:
 Irena Penev, 2012, Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:13082.