GRAPHS OF (0,1)-MATRICES.
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Pagination or Media Count:
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 Berges 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 KG of a graph G is bipartite, then the chromatic number chiG of G equals the number of points omegaG in the largest complete subgraph of G. Author
- Theoretical Mathematics