Minimax relations for the partial q-colorings of a graph (Q1825878)

A partial q-coloring of a graph is a family of q disjoint stable sets, each one representing a color; the largest number of colored vertices in a partial q-coloring is a number \(\alpha_ q(G)\), extension of the stability number \(\alpha (G)=\alpha_ 1(G)\). It is defined, by three conditions, an association between a partial q-coloring of G and a clique-family of G. In this paper, for \(1\leq q\leq \gamma (G)\), \(\alpha_ q(G)\) is expressed by a minimax equality in terms of the associated clique-families. It is shown that some known properties of balanced hypergraphs give easily some new classes of graphs for which the optimal q-colorings have an associate clique-family. It is proved also that the cartesian sum \(G+K_ q(2\leq q\leq \gamma (G))\) is perfect if and only if \(q=2\) and G is a parity graph, or \(q\geq 3\) and G is a graph whose blocks are cliques. Also, if G is the line-graph of a tree and \(q\leq \gamma (G)\), then \(G+K_ q\) is perfect and for every optimal q-coloring of G, an associated clique family can be efficiently constructed.