On graphs without a C₄ or a diamond

DOI10.1016/J.DAM.2010.04.015MaRDI QIDQ531598zbMATH OpenOpenAlexFDO

Authors Elaine M. Eschen, Chính T. Hoàng, Jeremy P. Spinrad, R. Sritharan

Publication date 19 April 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.04.015

zbMATH Keywords

\(C_{4}\)-free graphsdiamond-free graphsrecognition algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Recognition algorithm for diamond-free graphs
• Finding and counting small induced subgraphs efficiently
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• Large cliques in \(C_4\)-free graphs
• Strong cliques in diamond-free graphs

Cites work

• A Linear Recognition Algorithm for Cographs
• Algorithmic graph theory and perfect graphs
• Computing independent sets in graphs with large girth
• Efficient graph representations
• Graph Classes: A Survey
• Graph theory
• scientific article; zbMATH DE number 3760892 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• On diameters and radii of bridged graphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(22)

• Graphs without \(K_ 4\) and well-quasi-ordering
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Finding a sun in building-free graphs
• Detecting and enumerating small induced subgraphs in c-closed graphs
• Isolation of the diamond graph
• Decomposition of directed graphs and the Turán problem
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Map graphs having witnesses of large girth
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Recognition algorithm for diamond-free graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Finding cliques in social networks: a new distribution-free model
• Finding cliques in social networks: a new distribution-free model
• Diamond-free degree sequence
• Decomposing and clique-coloring (diamond, odd-hole)-free graphs
• A polynomial kernel for distance-hereditary vertex deletion
• Strong cliques in diamond-free graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Essentially tight kernels for (weakly) closed graphs
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Induced subgraph isomorphism: are some patterns substantially easier than others?

This page was built for publication: On graphs without a \(C_{4}\) or a diamond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q531598)