Title of article :
Weighted coloring on planar, bipartite and split graphs: Complexity and approximation Original Research Article
Author/Authors :
D. de Werra، نويسنده , , M. Demange، نويسنده , , B. Escoffier، نويسنده , , J. Monnot، نويسنده , , V.Th. Paschos، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighte
Keywords :
Planar graphs , Bipartite graphs , Split graphs , Weighted node coloring , Graph coloring , Weighted edge coloring , NP-completeness , Approximability
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics
