On perfectness of sums of graphs (Q1296974): Difference between revisions

The sum (also known as Cartesian product) \(G+H\) of two graphs \(G= (X,U)\) and \(H= (Y,V)\) has vertex set \(Z= \{(x,y)\mid x\in X, y\in Y\}\) and edge set \(W= \{[(x,y),(x',y')]\mid x= x',[y,y']\in V\) or \(y= y'\), \([x,x']\in U\}\). The authors motivate the study of the characterization of perfect sum graphs through the result that a graph \(G\) can be coloured with \(q\) colours if and only if \(G+ K_q\) has an independent set \(S\) with \(|S|=|X|\). A triangulated diamond-free graph is called a TDF graph, also known as block graph, characterized by the fact that its maximal 2-connected components are cliques. It is proved that a graph \(G\) is TDF if and only if \(G+ K_q\) is perfect, for some (each) positive integer \(q\geq 3\). A Berge graph is a graph which does not have an odd cycle or its complement (on at least 5 vertices) as an induced subgraph. A triangle with a pendant edge attached is called a flat (also known as paw). A BFF graph is a Berge flag-free graph. The authors prove the following characterization of perfect sum graphs: The sum of two connected graphs with at least three nodes each is perfect if and only if one of the following mutually exclusive cases holds: (a) both are bipartite, (b) one is TDF and the other a clique, (c) one is BFF with an induced diamond and the other is a tree. The case when one of the factors has only two vertices is dealt with as follows: \(G+K_2\) is perfect if and only if \(G\) is a parity graph (i.e. a graph in which for any two vertices, all chordless chains between them have the same parity). Though most of the results are known, the presentation is new and interesting.