Accession Number:
AD0691756
Title:
GRAPHS OF (0,1)-MATRICES.
Descriptive Note:
Technical rept.,
Corporate Author:
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Personal Author(s):
Report Date:
1969-08-01
Pagination or Media Count:
33.0
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 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
Descriptors:
Subject Categories:
- Theoretical Mathematics