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.
|Number of pages||6|
|Journal||Theoretical Computer Science|
|Publication status||Published - 20 Apr 2012|