Graph coloring with rejection

L. Epstein, A. Levin, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Citaten (Scopus)


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.
Originele taal-2Engels
TitelAlgorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006)
RedacteurenY. Azar, T. Erlebach
Plaats van productieBerlin
ISBN van geprinte versie3-540-38875-3
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Graph coloring with rejection'. Samen vormen ze een unieke vingerafdruk.

Citeer dit