Max-Coloring of Vertex-Weighted Graphs
Journal
Graphs and Combinatorics
Date Issued
2015
Author(s)
Abstract
A proper vertex coloring of a graph (Formula presented.) is a partition (Formula presented.) of the vertex set (Formula presented.) into stable sets. For a graph (Formula presented.) with a positive vertex-weight (Formula presented.) be the minimum value of (Formula presented.)over all proper vertex coloring (Formula presented.) the minimum value of(Formula presented.) for a proper vertex coloring (Formula presented.). This paper establishes an upper bound on (Formula presented.) for a weighted (Formula presented.), and a Nordhaus–Gaddum type inequality for (Formula presented.). It also studies the $$c$$c-perfection for a weighted graph (Formula presented.).
Type
journal article