GRAPHS OF (0,1)-MATRICES.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1969
- Accession Number
- AD0691756
Entities
People
- Stephen T. Hedetniemi
Organizations
- University of Iowa