Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

DOI10.1016/j.dam.2004.06.008zbMath1056.05099OpenAlexW2152515622MaRDI QIDQ1765527

Takayuki Nagoya, Seinosuke Toda, Ryuhei Uehara

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

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)

Related Items (24)

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

Cites Work

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

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