Publication

On two coloring problems in mixed graphs

Dominique de Werra, Bernard Ries
2008
Journal paper
Abstract

We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one we want adjacent vertices to have different colors and the tail of an arc to get a color strictly less than the head of this arc; in the second problem we allow vertices linked by an arc to have the same color. For both cases we present bounds on the mixed chromatic number and we give some complexity results which strengthen former results given in B.Ries "Coloring some classes of mixed graphs".

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.