GRAPHS OF (0,1)-MATRICES.

A class of graphs is defined which is naturally suggested by a classical theorem of Konig-Egervary on (0,1)-matrices. Several characterizations of this class of graphs are obtained which reveal close connections between these graphs and line graphs, clique graphs, bipartite graphs and Berge's perfect graphs. Finally, as a result of these characterizations and another well-known theorem of Konig we obtain the following result: if the clique graph K(G) of a graph G is bipartite, then the chromatic number chi(G) of G equals the number of points omega(G) in the largest complete subgraph of G. (Author)
Report on the Theory and Applications of Automaton Theory.