On two coloring problems in mixed graphs

DOI10.1016/j.ejc.2007.03.006zbMath1154.05036OpenAlexW2075902025MaRDI QIDQ2426450

Dominique de Werra, Bernard Ries

Publication date: 22 April 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/324623/files/coloringmixedgraphsii.pdf

zbMATH Keywords

computational complexitybipartite graphmixed graphk-treestrong mixed graph colouringweak mixed graph colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ Parameterized mixed graph coloring ⋮ Coloring mixed and directional interval graphs ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ Routing equal-size messages on a slotted ring ⋮ On weighted directed graphs ⋮ Complexity of two coloring problems in cubic planar bipartite mixed graphs ⋮ Mixed graph edge coloring

Cites Work

• Coloring some classes of mixed graphs
• Reasoning about qualitative temporal information
• Mixed graph colorings
• Hard coloring problems in low degree planar bipartite graphs
• Scheduling Problems and Mixed Graph Colorings
• Smallest-last ordering and clustering and graph coloring algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On two coloring problems in mixed graphs