Geodesic
PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS
Acta mathematica Universitatis Comenianae, Tome 62 (1993) no. 1 
M. Hujter; ZS. Tuza. PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS. Acta mathematica Universitatis Comenianae, Tome 62 (1993) no. 1. http://geodesic.mathdoc.fr/item/AMUC_1993_62_1_a0/
@article{AMUC_1993_62_1_a0,
     author = {M. Hujter and ZS. Tuza},
     title = {PRECOLORING {EXTENSION.} {II.} {GRAPHS} {CLASSES} {RELATED} {TO} {BIPARTITE} {GRAPHS}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1993},
     volume = {62},
     number = {1},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1993_62_1_a0/}
}
TY  - JOUR
AU  - M. Hujter
AU  - ZS. Tuza
TI  - PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS
JO  - Acta mathematica Universitatis Comenianae
PY  - 1993
VL  - 62
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/AMUC_1993_62_1_a0/
ID  - AMUC_1993_62_1_a0
ER  - 
%0 Journal Article
%A M. Hujter
%A ZS. Tuza
%T PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS
%J Acta mathematica Universitatis Comenianae
%D 1993
%V 62
%N 1
%U http://geodesic.mathdoc.fr/item/AMUC_1993_62_1_a0/
%F AMUC_1993_62_1_a0

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

We continue the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph $G$ are assigned to some colors. Can this ``precoloring'' be extended to a proper coloring of $G$ with at most $k$ colors (for some given $k$)? Here we investigate the complexity status of precoloring extendibility on some graph classes which are related to bipartite graphs, giving a complete solution for graphs with ``co-chromatic number'' 2, i.e., admitting a partition $V=V_1\cup V_2$ of the vertex set $V$ such that each $V_i$ induces a complete subgraph or an independent set. On one hand, we show that our problem is closely related to the bipartite maximum matching problem that leads to a polynomial solution for split graphs and for the complements of bipartite graphs. On the other hand, the problem turns out to be NP-complete on bipartite graphs.