On graphs without a C4 or a diamond

2009/09/25 by Elaine M. Eschen, Eschen, Elaine M., Chı́nh T. Hoàng +5 · 1 citation
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.0909.4719

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.

Cited by

• A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection

Related

• Cliques in C₄-free graphs of large minimum degree
• Colouring Diamond-free Graphs
• Strong cliques in diamond-free graphs
• Structure and coloring of some (P₇,C₄)-free graphs
• Structure of (bull, diamond)-free graphs and its applications