A note on perfect graphs (Q1084108): Difference between revisions

A simple graph G is called perfect if every induced subgraph G' of G satisfies \(\chi (G')=\omega (G')\), where X(G') is the chromatic number and \(\omega\) (G') is the size of a maximum clique of G'. \textit{L. Lovász} had shown that the complement of a perfect is perfect [Discrete Math. 2, 253-267 (1972; Zbl 0239.05111)]. The following generalization is proved here. Let the lines of a complete graph be \(\gamma\)-colored with colors red, green and black, so that no triangle gets all three colors. Suppose that the two graphs formed by the red lines and green lines, respectively, are perfect. Then so is the graph formed by the black lines. It is then conjectured that the hypothesis can be weakened in a specific way.