Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

Stefan Kratsch*, Pascal Schweitzer

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    15 Citations (Scopus)

    Abstract

    We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither of the forbidden graphs is a clique, a pan, or a complement of these graphs. Further reducing the remaining open cases we show that (with respect to graph isomorphism) forbidding a pan is equivalent to forbidding a clique of size three.

    Original languageEnglish
    Title of host publicationGraph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Revised Selcted Papers
    Pages34-45
    Number of pages12
    DOIs
    Publication statusPublished - 2012
    Event38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012 - Jerusalem, Israel
    Duration: 26 Jun 201228 Jun 2012

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7551 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012
    Country/TerritoryIsrael
    CityJerusalem
    Period26/06/1228/06/12

    Fingerprint

    Dive into the research topics of 'Graph isomorphism for graph classes characterized by two forbidden induced subgraphs'. Together they form a unique fingerprint.

    Cite this