Triangulated neighborhoods in even-hole-free graphs

DOI10.1016/j.disc.2006.07.027zbMath1115.05078DBLPjournals/dm/SilvaV07OpenAlexW2120261735WikidataQ57949076 ScholiaQ57949076MaRDI QIDQ870966

Murilo V. G. da Silva, Kristina Vušković

Publication date: 15 March 2007

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

Full work available at URL: http://eprints.whiterose.ac.uk/74353/2/ehf.pdf

zbMATH Keywords

structural characterizationtriangulated graphsgenerating all maximal cliques

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (16)

Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ Forbidden induced subgraphs ⋮ Temporal interval cliques and independent sets ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Finding a shortest even hole in polynomial time ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Bounds on regularity of quadratic monomial ideals ⋮ Algorithms for induced biclique optimization problems ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Bisimplicial vertices in even-hole-free graphs ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences ⋮ Combinatorial optimization with 2-joins ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Matrix multiplication via arithmetic progressions
• Bisimplicial vertices in even-hole-free graphs
• On diameters and radii of bridged graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Recognizing Berge graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• Arboricity and Subgraph Listing Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Even and odd holes in cap-free graphs
• Algorithm Theory - SWAT 2004

This page was built for publication: Triangulated neighborhoods in even-hole-free graphs