**
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE **

Vol. 62, 1 (1993)

pp. 1-11

PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS

M. HUJTER and ZS. TUZA

**Abstract**.
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**.
05C15

**Keywords**.

**Download:** Adobe PDF Compressed Postscript

Acta Mathematica Universitatis Comenianae

Institute of Applied
Mathematics

Faculty of Mathematics,
Physics and Informatics

Comenius University

842 48 Bratislava, Slovak Republic

Telephone: + 421-2-60295111 Fax: + 421-2-65425882

e-Mail: amuc@fmph.uniba.sk
Internet: www.iam.fmph.uniba.sk/amuc
© Copyright 2001, ACTA MATHEMATICA
UNIVERSITATIS COMENIANAE