pith. sign in

arxiv: 0909.4719 · v1 · submitted 2009-09-25 · 💻 cs.DM

On graphs without a C4 or a diamond

classification 💻 cs.DM
keywords diamondgraphsclassfreealgorithmefficientnumberclique
0
0 comments X
read the original abstract

We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C4, diamond)-free graph and the number of n-vertex, labeled (C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.