The d-precoloring problem for k-degenerate graphs

Janka Chlebikova, Klaus Jansen

Research output: Contribution to journalArticlepeer-review

71 Downloads (Pure)

Abstract

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem
is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at
most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.

We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted
to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted
to the class of partial k-trees (without any size restriction on S).We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use
for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and
its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.
Original languageEnglish
Pages (from-to)2042-2052
JournalDiscrete Mathematics
Volume307
Issue number16
Early online date4 Dec 2006
DOIs
Publication statusPublished - 28 Jul 2007

Keywords

  • PRECOLORING EXTENSION problem
  • Linear time algorithm
  • k-degenerate graphs
  • Partial k-trees

Fingerprint

Dive into the research topics of 'The d-precoloring problem for k-degenerate graphs'. Together they form a unique fingerprint.

Cite this