## 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.

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 language | English |
---|---|

Pages (from-to) | 2042-2052 |

Journal | Discrete Mathematics |

Volume | 307 |

Issue number | 16 |

Early online date | 4 Dec 2006 |

DOIs | |

Publication status | Published - 28 Jul 2007 |

## Keywords

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