On switching classes, NLC-width, cliquewidth and treewidth

Jurriaan Hage, Hans L. Bodlaender

Research output: Contribution to journalArticlepeer-review


In this paper we consider a connection between switching (of undirected graphs), and the notions of NLC-width, cliquewidth and treewidth. In particular, we show that the NLC-widths and the cliquewidths of two graphs in a switching class are at most a constant factor apart (2 for the former, 4 for the latter). A similar result can be shown not to hold for treewidth: it is easy to find a switching classes in which the distance between the lowest treewidth and the highest is dependent on the number of vertices of the graph. We also show that for NLC-width every width between the lowest and the highest of the switching class is attained by some graph in that switching class. We prove that this also holds for treewidth.
Original languageEnglish
Pages (from-to)30-35
Number of pages6
JournalTheoretical Computer Science
Publication statusPublished - 20 Apr 2012


Dive into the research topics of 'On switching classes, NLC-width, cliquewidth and treewidth'. Together they form a unique fingerprint.

Cite this