ACTA MATHEMATICA UNIVERSITATIS COMENIANAE
Vol. 62,   1   (1993)
PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS
M. HUJTER and ZS. TUZA
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.
AMS subject classification.
Download:     Adobe PDF     Compressed Postscript
Acta Mathematica Universitatis Comenianae
Institute of Applied
Faculty of Mathematics,
Physics and Informatics
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
© Copyright 2001, ACTA MATHEMATICA