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:

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:

• (*GRAPHICS
• THEORY)
• MATRICES(MATHEMATICS)
• SET THEORY
• AUTOMATA
• COLORS
• THEOREMS

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE