Minimax relations for the partial q-colorings of a graph
type: Item
instance of: scholarly article
title: Minimax relations for the partial q-colorings of a graph
zbMATH Open document ID: 0685.05021
DOI: 10.1016/0012-365X(89)90193-3
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4122018
zbMATH Keywords: chromatic number
zbMATH Keywords: perfect graph
zbMATH Keywords: minimax relations
zbMATH Keywords: partial q-coloring
zbMATH Keywords: hypergraphs
zbMATH Keywords: clique-family
zbMATH Keywords: cartesian sum
Wikidata QID: Q56001748
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q4099676
cites work: Q3216697
cites work: Q5636932
cites work: Q3222874
cites work: On perfectness of sums of graphs
cites work: Q4133404
cites work: Strong versions of Sperner's theorem
cites work: On partitions of a partially ordered set
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q3682511
cites work: Perfect product graphs
cites work: Q5659563
cites work: Coloring perfect \((K_ 4\)-e)-free graphs
full work available at URL: 0012-365x(89)90193-3
OpenAlex ID: W1977563107
DBLP publication ID: journals/dm/Berge89
Recommended article: A min-max relation for the partial q-colourings of a graph. II: Box perfection
Recommended article: The Min-max Edge q-Coloring Problem
Recommended article: The Min-Max Edge q-Coloring Problem
Recommended article: Maximizing the number of q -colorings
Recommended article: Q4871063
Recommended article: Q5187313
Recommended article: Minimal coloring and strength of graphs
Recommended article: Minimum order of graphs with given coloring parameters
Recommended article: The minimum color sum of bipartite graphs
Recommended article: Total colorings of graphs with minimum sum of colors
author: C. Berge
description: scientific article; zbMATH DE number 4122018