Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On two coloring problems in mixed graphs
 
research article

On two coloring problems in mixed graphs

Ries, Bernard
•
de Werra, Dominique  
2008
European Journal of Combinatorics

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".

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.ejc.2007.03.006
Web of Science ID

WOS:000254298700015

Author(s)
Ries, Bernard
de Werra, Dominique  
Date Issued

2008

Published in
European Journal of Combinatorics
Volume

29

Start page

712

End page

725

Subjects

mixed graph

•

bipartite graph

•

partial $k$-tree

•

precoloring extension

•

list coloring

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
December 4, 2006
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/237255
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés