Two-colourings that decompose perfect graphs (Q2640608): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3222874 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Star-cutsets and perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new property of critical imperfect graphs and some consequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on even pairs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a property of the class of n-colorable graphs / rank | |||
Normal rank |
Latest revision as of 14:33, 21 June 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