
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 KonigEgervary 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 wellknown 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