A Hajós-like theorem for weighted coloring

Julio Araujo 1, 2 Claudia Linhares Sales 1
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The Hajós' Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116-117, 1961) shows a necessary and sufficient condition for the chromatic number of a given graph $G$ to be at least $k$ : $G$ must contain a $k$ -constructible subgraph. A graph is $k$ -constructible if it can be obtained from a complete graph of order $k$ by successively applying a set of well-defined operations. Given a vertex-weighted graph $G$ and a (proper) $r$ -coloring $c=\{C_1, \ldots , C_r\}$ of $G$ , the weight of a color class $C_i$ is the maximum weight of a vertex colored $i$ and the weight of $c$ is the sum of the weights of its color classes. The objective of the Weighted Coloring Problem [7] is, given a vertex-weighted graph $G$ , to determine the minimum weight of a proper coloring of $G$ , that is, its weighted chromatic number. In this article, we prove that the Weighted Coloring Problem admits a version of the Hajós' Theorem and so we show a necessary and sufficient condition for the weighted chromatic number of a vertex-weighted graph $G$ to be at least $k$ , for any positive real $k$.
Type de document :
Article dans une revue
Journal of the Brazilian Computer Society, Springer Verlag, 2013, 19 (3), pp.275-278. <10.1007/s13173-012-0098-y>


https://hal.inria.fr/hal-00773410
Contributeur : Julio Araujo <>
Soumis le : lundi 14 janvier 2013 - 00:52:00
Dernière modification le : mercredi 7 octobre 2015 - 01:15:15
Document(s) archivé(s) le : lundi 15 avril 2013 - 03:55:05

Fichier

hajos_journalSBC.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Claudia Linhares Sales. A Hajós-like theorem for weighted coloring. Journal of the Brazilian Computer Society, Springer Verlag, 2013, 19 (3), pp.275-278. <10.1007/s13173-012-0098-y>. <hal-00773410>

Partager

Métriques

Consultations de
la notice

240

Téléchargements du document

230