Physical Sciences and Mathematics Commons^™

Separability And Vertex Ordering Of Graphs, Elizabeth Gorbonos

Theses and Dissertations (Comprehensive)

Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph …

Vertex Coloring With Forbidden Subgraphs, Yingjun Dai

Theses and Dissertations (Comprehensive)

Given a set $L$ of graphs, a graph $G$ is $L$-free if $G$ does not contain any graph in $L$ as induced subgraph. A $hole$ is an induced cycle of length at least $4$. A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely related to the characterization of the line graphs in terms of forbidden subgraphs.

By using {\it clique-width} and {\it perfect graphs} theory, we show that ($claw$,$4K_1$,$hole$-$twin$)-free graphs and ($4K_1$,$hole$-$twin$,$5$-$wheel$)-free graphs are either perfect or have bounded clique-width. And thus the coloring of them can be …