zbMATH — the first resource for mathematics

Precoloring extension. II. Graphs classes related to bipartite graphs. (English) Zbl 0821.05026
Summary: 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 the 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.

05C15 Coloring of graphs and hypergraphs
Full Text: EMIS EuDML