TY - JOUR

T1 - Sub-coloring and hypo-coloring interval graphs

AU - Gandhi, Rajiv

AU - Greening, Bradford

AU - Pemmaraju, Sriram

AU - Raman, Rajiv

N1 - Publisher Copyright:
© 2010 World Scientific Publishing Company.

PY - 2010/9/1

Y1 - 2010/9/1

N2 - In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O(log n)-approximation algorithm for it.

AB - In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O(log n)-approximation algorithm for it.

KW - NP-complete

KW - Sub-coloring

KW - approximation algorithm

KW - hypo-coloring

KW - interval graphs

UR - http://www.scopus.com/inward/record.url?scp=85044536115&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044536115&partnerID=8YFLogxK

U2 - 10.1142/S1793830910000693

DO - 10.1142/S1793830910000693

M3 - Article

AN - SCOPUS:85044536115

SN - 1793-8309

VL - 2

SP - 331

EP - 345

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

IS - 3

ER -