Journal article

On two coloring problems in mixed graphs

    2008
Published in:
  • European Journal of Combinatorics. - 2008, vol. 29, p. 712-725
English 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 a color of the head of this arc; in the second problem, we also 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 earlier results given in [B. Ries, Coloring some classes of mixed graphs, Discrete Applied Mathematics 155 (2007) 1–6].
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307906
Statistics

Document views: 5 File downloads:
  • coloringmixedgraphsii.pdf: 1