Complexity issues in switching of graphs



: Ehrenfeucht A, Hage J, Harju T, Rozenberg G

: 2000

Lecture Notes in Computer Science

THEORY AND APPLICATION TO GRAPH TRANSFORMATIONS

: LECT NOTES COMPUT SC

: 1764

: 59

: 70

: 12

: 3-540-67203-6

: 0302-9743


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. We compare the complexity of a number of problems on graphs with the complexity of these problems extended to the set of switches of a graph. Within this framework, we prove a modification of Yannakakis' result and use it to show NP-completeness for the embedding problem. Finally we prove NP-completeness for the 3-colourability problem.



Last updated on 2025-13-10 at 14:07