Sub-coloring and hypo-coloring interval graphs

Rajiv Gandhi, Bradford Greening, Sriram Pemmaraju, Rajiv Raman

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)331-345
Number of pages15
JournalDiscrete Mathematics, Algorithms and Applications
Volume2
Issue number3
DOIs
StatePublished - Sep 1 2010

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Keywords

  • NP-complete
  • Sub-coloring
  • approximation algorithm
  • hypo-coloring
  • interval graphs

Fingerprint

Dive into the research topics of 'Sub-coloring and hypo-coloring interval graphs'. Together they form a unique fingerprint.

Cite this