Graphs with no induced C4 and 2K2
|Title||Graphs with no induced C4 and 2K2|
|Publication Type||Journal Article|
|Year of Publication||1993|
|Authors||Blázsik Z, Hujter M, Pluhár A, Tuza Z.|
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).