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