Graph Partitions and Integer Flows

This dissertation, "Graph Partitions and Integer Flows" by Xujin, Chen, 陳旭瑾, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled GRAPH PARTITIONS AND INTEGER FLOWS submitted by CHEN Xujin for the degree of Doctor of Philosophy at The University of Hong Kong in June 2004 Many important problems in the areas of combinatorics and optimization can be formulated in terms of graph partitions and/or integer ows, and the extensive study of these objects has led to a rich and beautiful theory. The present thesis is concerned with some graph partition and integer ow problems, and explores the theoretical and algorithmic connections between graph partitions and integer ows, and applies various algorithmic ideas in addition to the \structure-driven" approach. The partition problems for graph G with vertex set V (G) studied in this thesis fall into three categories: (1) The odd k-partition problem, which is to partition V (G) into k disjoint subsets, such that each subset induces a connected subgraph and has an odd-sized intersection with every prespecied vertex subset. (2) The vertex coloring problem, which is to partition V (G) into as few as possible disjoint subsets such that no subset contains adjacent vertices. (3) The cycle packing problem, which is to partition the vertex or edge set of a graph arising from G into as many as possible disjoint subsets such that no subset induces an acyclic graph. The integer ows under investigation include nowhere-zero integer ows and integer maximum ows. Given a connected multigraph G and three nonempty even-sized subsets A; B; C of V (G), when does V (G) have a partitionfS; Sg such that each of S and S induces a connected subgraph and has an odd-sized intersection with each of A, B, and C? This problem was settled by Chakravati and Roberston (1980) for the special case whenjAj =jBj =jCj = 2, which is a variation of a seminal result on disjoint paths obtained independently by Seymour, Shiloach, and Thomassen (1980). The problem is solved completely in this thesis, and the corresponding structural characterization can be used as a powerful tool to tackle some important problems on nowhere-zero integer ows. A well-known theorem due to Catlin (1979) asserts that every graph containing no odd K is 3-colorable. In this thesis, the following dual of Catlin's theorem is established: Every 2-edge-connected multigraph with no odd K -partition admits a nowhere-zero 3- ow, where an odd K -partition of a multigraph G is a partition fV; V; V; V g of V (G) such that for any 1 i; j 4, V [ V induces a connected 1 2 3 4 i j subgraph, and V contains an odd number of odd-degree vertices. This result reveals a close connection between graph partitions and integer ows, and suggests a new research direction in the integer ow theory.The vertex coloring of circular-arc graphs arises in a variety of applications. In this thesis an O(n m) combinatorial algorithm for nding a minimum coloring of any perfect circular-arc graph with n vertices and m edges is obtained. A nice feature of this algorithm is its practical eciency. Reducible ow graphs are used extensively for code optimization and global data 2 2 ow analysis. In this thesis an O(n m log(n =m)) algorithm for nding a maximum cycle packing in any weighted reducible ow graph with n vertices and m arcs is given. This algorithm captures more structural information and achieves more eciency compared with the existing one obtained by Ramachandran (1990). DOI: 10.5353/th_b3028625