ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

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