A Family of Counter Examples to an Approach to Graph Isomorphism

2008/01/11 by Jin‐Yi Cai, Cai, Jin-Yi, Pinyan Lu +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.0801.1766

openalex publication_date 2008/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a family of counter examples showing that the two sequences of polytopes Φ_n,n and Ψ_n,n are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.

Related

• Recent Advances on the Graph Isomorphism Problem
• Le probleme de l'isomorphisme de graphes est dans P
• On the Solution of Graph Isomorphism by Dynamical Algorithms
• The graph isomorphism problem is polynomial
• Graph Isomorphism is PSPACE-complete