Universally signable graphs (Q1375057)

A chordless cycle of length greater then three in a graph \(G\) is called a hole. A graph is universally signable if for any \(\{0,1\}\) vector \(\gamma\) with entries in one-to-one correspondence with the holes of \(G\), odd and even labels to the edges of \(G\) can be associated such that the number of odd edges in every triangle is odd while the number of odd edges in every hole stands in accordance with \(\gamma\). In this paper a characterization of universaly signable graphs is given. The main result is a generalization of a decomposition theorem of Hajnal and Surányi for triangulated graphs. From this decomposition result also a polynomial time recognition algorithm for universally signable graphs is obtained. Several related problems are discussed.