Geodesic
PRECOLORING EXTENSION WITH FIXED COLOR BOUND
Acta mathematica Universitatis Comenianae, Tome 62 (1993) no. 2 
J. Kratochvil. PRECOLORING EXTENSION WITH FIXED COLOR BOUND. Acta mathematica Universitatis Comenianae, Tome 62 (1993) no. 2. http://geodesic.mathdoc.fr/item/AMUC_1993_62_2_a0/
@article{AMUC_1993_62_2_a0,
     author = {J. Kratochvil},
     title = {PRECOLORING {EXTENSION} {WITH} {FIXED} {COLOR} {BOUND}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1993},
     volume = {62},
     number = {2},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1993_62_2_a0/}
}
TY  - JOUR
AU  - J. Kratochvil
TI  - PRECOLORING EXTENSION WITH FIXED COLOR BOUND
JO  - Acta mathematica Universitatis Comenianae
PY  - 1993
VL  - 62
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AMUC_1993_62_2_a0/
ID  - AMUC_1993_62_2_a0
ER  - 
%0 Journal Article
%A J. Kratochvil
%T PRECOLORING EXTENSION WITH FIXED COLOR BOUND
%J Acta mathematica Universitatis Comenianae
%D 1993
%V 62
%N 2
%U http://geodesic.mathdoc.fr/item/AMUC_1993_62_2_a0/
%F AMUC_1993_62_2_a0

Voir la notice de l'article provenant de la source Comenius University

Precoloring Extension (shortly PrExt) is the following problem: Given a graph $G$ with some \pd vertices and a color bound $k$, can the \PI of $G$ be extended to a proper coloring of all vertices of $G$ using not more than $k$ colors? Answering an open problem from Ref. 6, we prove that PrExt with fixed color bound $k=3$ is \np for bipartite (and even planar) graphs, and we prove a general result on parametrized PrExt. We also give a simplified argument why PrExt with fixed color bound is solvable in polynomial time for graphs of bounded treewidth (and hence also for chordal graphs).