Graphs with no induced C4 and 2K2

TitleGraphs with no induced C4 and 2K2
Publication TypeJournal Article
Year of Publication1993
AuthorsBlázsik Z, Hujter M, Pluhár A, Tuza Z.
JournalDiscrete Mathematics
Volume115
Pagination51–55
Date Published5
PublisherElsevier
ISSN0012-365X
Abstract

We characterize the structure of graphs containing neither the 4-cycle nor its complement as an induced subgraph. This self-complementary class G of graphs includes split graphs, which are graphs whose vertex set is the union of a clique and an independent set. In the members of G, the number of cliques (as well as the number of maximal independent sets) cannot exceed the number of vertices. Moreover, these graphs are almost extremal to the theorem of Nordhaus and Gaddum (1956).

DOI10.1016/0012-365X(93)90477-B