Portal de Periódicos da CAPES

A mickey-mouse decomposition theorem

1995; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-59408-6_61

1611-3349

Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vušković,

Computability, Logic, AI Algorithms

A graph is signable to be without odd holes if we can assign labels "even" or "odd" to its edges in such a way that the number of edges labelled "odd" in every triangle is odd and the number of edges labelled "odd" in every chordless cycle of length greater than three is even. Note that a graph has no odd holes if it is signed to be without odd holes with every edge having an "odd" label. We derive a co-NP characterization of such graphs. A mickey-mouse M is a cycle C=x 1,⋯, x n, x 1 with two chords x ixj and x i+1 x j (indices taken modulo n). The chordless cycles C 1=x j,⋯, x i, x j and C 2=x i+1,⋯, x j, x i+1 are the ears of the mickey-mouse. A mickey-mouse has big ears if both C 1 and C 2 have length greater than three. In this paper we show that if a graph G is signable to be without odd holes and contains a mickey-mouse with big ears, with chords x ixj and x i+1x j, then the removal of the nodes adjacent to x j, together with the nodes adjacent to both x i and x i+1 disconnects G.