Two-colourings that decompose perfect graphs (Q2640608): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:23, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-colourings that decompose perfect graphs |
scientific article |
Statements
Two-colourings that decompose perfect graphs (English)
0 references
1990
0 references
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.
0 references
perfect graphs
0 references
graph decomposition
0 references