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) : Hedetniemi,Stephen T.
Report Date : AUG 1969
Pagination or Media Count : 33
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)
Descriptors : (*GRAPHICS, THEORY), MATRICES(MATHEMATICS), SET THEORY, AUTOMATA, COLORS, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE