UNIVERSALLY SIGNABLE GRAPHS

In a graph, a chordless cycle of length greater than three is called a hole. Let gamma be a {0, 1} vector whose entries are in one-to-one co rrespondence with the holes of a graph G. We characterize graphs for w hich, for all choices of the vector gamma, we can pick a subset F of t he edge set of G such that \F boolean AND H\ = gamma(H) (mod 2), for a ll holes H of G and \F boolean AND T\ = 1 for all triangles T of G. We call these graphs universally signable. The subset F of edges is said to be labelled odd. Ail other edges are said to be labelled even. Cle arly graphs with no holes (triangulated graphs) are universally signab le with a labelling of odd on all edges, for all choices of the vector gamma. We give a decomposition theorem which leads to a good characte rization of graphs that are universally signable. This is a generaliza tion of a theorem due to Hajnal and Suranyi [3] for triangulated graph s.