The q-perfect graphs
Claude Berge · Le Matematiche · 1993
Let q be a positive integer. Many graphs admit a partial coloring with q colors and a clique partition such that each of the cliques is strongly colored, that is: contains the largest possible number of different colors. If a graph G and all its induced subgraphs have this property, we say that G is q-perfect (Lovasz). In a previous paper [4], the specific properties for the case q=2 were investigated. Here, we study some graphs which are q-perfect for other values of q, and more specially the balanced graphs.