### Abstract

We consider the following vertex coloring problem. We are
given an undirected graph G = (V,E), where each vertex v is associated
with a penalty rejection cost rv. We need to choose a subset of vertices,
V ??, and to find a proper coloring of the induced subgraph of G over V ??.
We are interested in both the number of colors used to color the vertices
of V ??, and in the total rejection cost of all other vertices. The goal is to
minimize the sum of these two amounts. In this paper we consider both
the online and the offline versions of this problem. In the online version,
vertices arrive one at a time, revealing the rejection cost of the current
vertex and the set of edges connecting it to previously revealed vertices.
We also consider the classical online coloring problem on bounded degree
graphs and on (k + 1)-claw free graphs.

Original language | English |
---|---|

Title of host publication | Algorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006) |

Editors | Y. Azar, T. Erlebach |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 364-375 |

ISBN (Print) | 3-540-38875-3 |

DOIs | |

Publication status | Published - 2006 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 4168 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'Graph coloring with rejection'. Together they form a unique fingerprint.

## Cite this

Epstein, L., Levin, A., & Woeginger, G. J. (2006). Graph coloring with rejection. In Y. Azar, & T. Erlebach (Eds.),

*Algorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006)*(pp. 364-375). (Lecture Notes in Computer Science; Vol. 4168). Springer. https://doi.org/10.1007/11841036_34