Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

DOI10.1016/J.DAM.2004.06.008zbMATH Open1056.05099OpenAlexW2152515622MaRDI QIDQ1765527FDOQ1765527

Authors: Ryuhei Uehara, Takayuki Nagoya, Seinosuke Toda 

Publication date: 23 February 2005

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

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

Recommendations

• Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs
• scientific article; zbMATH DE number 4156494
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Logical Approaches to Computational Barriers
• Completeness results for graph isomorphism.

zbMATH Keywords

Chordal bipartite graphsGraph isomorphism completeGraph isomorphism problemStrongly chordal graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Graph Classes: A Survey
• Efficient graph representations
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• The graph isomorphism disease
• Graph Isomorphism is in SPP
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Title not available (Why is that?)
• Interval bigraphs and circular arc graphs
• A note on the graph isomorphism counting problem
• Graph isomorphism and identification matrices: Sequential algorithms

Cited In (30)

• Random generation and enumeration of bipartite permutation graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• Simple Geometrical Intersection Graphs
• Characterizing and computing the structure of clique intersections in strongly chordal graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Graphs with at most two moplexes
• On orthogonal ray graphs
• Searching for square-complementary graphs: complexity of recognition and further nonexistence results
• Interpretable multi-scale graph descriptors via structural compression
• Tractabilities and intractabilities on geometric intersection graphs
• Random Generation and Enumeration of Proper Interval Graphs
• Graph isomorphism parameterized by elimination distance to bounded degree
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs
• Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
• Directed path graph isomorphism
• Reformulations in mathematical programming: automatic symmetry detection and exploitation
• Title not available (Why is that?)
• Graph isomorphism restricted by lists
• Structural properties of word representable graphs
• CFI Construction and Balanced Graphs
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Symmetry in mathematical programming
• Complexity-separating graph classes for vertex, edge and total colouring
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• Rooted directed path graphs are leaf powers
• Revising Johnson's table for the 21st century

This page was built for publication: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

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