On the structure of balanced matrices and perfect graph

The central claim of this thesis is that the ideas and results obtained in the study of balanced matrices and balanced 0, $pm$1 matrices can be used to study perfect graphs.;To make the connection between perfect graphs and balanced matrices we consider the following signed bipartite graph representation for a 0, $pm$1 matrix A: the nodes of the bipartite graph are partitioned into two sets $Vsp{r}$ and $Vsp{c}$. The nodes in $Vsp{r}$ represent the rows of A and the nodes in $Vsb{c}$ the columns of A. If the $asb{ij}$ entry in A is not zero there is an edge between the modes representing row i and column j. The edge is labelled +1 if $asb{ij}$ = 1 and $-$1 otherwise. There are no other edges in the graph. A signed bipartite graph that represents a balanced 0, $pm$1 matrix is called a balanced signed bipartite graph. To represent a 0, 1 matrix we may remove all edge labels or equivalently label all edges +1.;A 0, 1 matrix is balanced if it does not contain a square sub-matrix of odd order with two ones in every row and every column. This implies that a bipartite graph represents a balanced 0, 1 matrix if it contains no hole of length 2 mod 4. Notice that in a bipartite graph all cycles are of length either 0 mod 4 or 2 mod 4. We refer to the cycles of length 2 mod 4 as unquad and the others as quad.;Perfect graphs are contained in the class of graphs which contain no odd holes. By understanding the structure of these graphs better we hope to gain insight into the structure of perfect graphs. The analogy between excluding holes of odd parity in graphs and unquad hole in bipartite graphs is unmistakable. The techniques used to obtain the decomposition theorem and polynomial recognition algorithm for balanced matrices rely on the graph representation. We show that a similar result may be possible for graphs with no odd holes, by proving a decomposition theorem whenever a special configuration is present in the graph.;The only known result on the complexity of checking if a graph contains an odd hole is due to D. Bienstock. He showed that it is NP-complete to determine if a graph contains an odd hole using any particular node. In a similar vein we show that it is NP-complete to determine if a bipartite graph contains a unquad hole using any particular node. All the same there exists a polynomial time algorithm to recognize if a bipartite graph contains a unquad hole (27). This makes us believe that it may be possible check in polynomial time if a graph contains an odd hole. (Abstract shortened by UMI.).