Odd Cycles, Bipartite Subgraphs, and Approximate Graph Coloring (thesis)
Report ID: TR-208-89Author: Yeh, Susan S.
Date: 1989-06-00
Pages: 138
Download Formats: |PDF|
Abstract:
The graph coloring problem is to color the vertices of a graph so that no two adjacent vertices have the same color. This problem is not only NP-complete but also seems hard to approximate. In this thesis, we investigate the interplay of three different topics: odd cycles, bipartite subgraphs, and approximate graph coloring. Our primary goal is to design efficient approximate graph coloring algorithms with good performance. Our focus is on odd cycles and our central approach is to find bipartite subgraphs of graphs. We examine the role played by odd cycles of graphs in connection with graph coloring. We show that the presence or absence of certain size odd cycles gives graphs more structure and hence simplifies graph coloring. More specifically, we show that the absence of small odd cycles enables us to find large bipartite subgraphs. On the other hand, the absence of large odd cycles in a biconnected graph implies the absence of large even cycles, and these conditions imply that the graph contains special structures. We present efficient polynomial-time graph coloring algorithms which improve the performance guarantee on certain graphs, sometimes by a large margin, over the existing approximate graph coloring algorithms. For example, we can color triangle-free graphs with O(sqrt n) colors, and in most cases, optimally color graphs with only 3-cycles and 5-cycles in odd cycles. We also present efficient polynomial-time algorithms for finding a maximum bipartite subgraph for special classes of graphs which include proper circular-arc, circular-arc permutation, and split graphs. On numerous occasions, we use one technique, namely dynamic programming, for the development of the algorithms. Furthermore, we show that we can modify the algorithms in a slight way to find a maximum bipartite subgraph that includes a nontrivial subset of vertices.