Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Jurriaan Hage, Tero Harju, Emo Welzl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)


In the context of graph transformations we look at the operation of switching, which can be viewed as an elegant method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.

Continuing the line of research in Ehrenfeucht et al. we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.
Original languageEnglish
Title of host publicationGraph Transformation. ICGT 2002
EditorsA. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg
Number of pages13
ISBN (Electronic)9783540458326
ISBN (Print)9783540443100
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes'. Together they form a unique fingerprint.

Cite this