Two-colourings that decompose perfect graphs (Q2640608): Difference between revisions

A theorem of the first author and Hoàng [the first author, J. Comb. Theory, Ser. B 39, 189-199 (1985; Zbl 0674.05058)] states that if the vertices of a graph G are coloured red and white in such a way that every induced path \(P_ 4\) with four vertices has an even number of red vertices, then G is perfect if and only if each of the two subgraphs induced by all the vertices of the same colour is perfect. Such decomposition results are interesting, for example in connection with the question if perfectness is an NP problemtype. The present paper provides a complete answer to the question: ``What sets of constraints (on the ways in which each \(P_ 4\) can be coloured) have the above property?'' Five new theorems of the above type are obtained.