Coloring some classes of mixed graphs |
| |
| Authors: | B. Ries |
| |
| Affiliation: | Ecole Polytechnique Fédérale de Lausanne, FSB-IMA-ROSE, Station 8, CH-1015 Lausanne, Switzerland |
| |
| Abstract: | We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [xi,xj], c(xi)≠c(xj) and for every arc (xp,xq), c(xp)<c(xq). We will analyse the complexity status of this problem for some special classes of graphs. |
| |
| Keywords: | Mixed graphs Bipartite graphs Partial k-trees Precoloring extension SAT |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
