Title of article :
Complexity of two coloring problems in cubic planar bipartite mixed graphs
Author/Authors :
B. Ries، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
5
From page :
592
To page :
596
Abstract :
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both image-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) .
Keywords :
List coloring , Computational complexity , Mixed graph coloring , Scheduling , Bipartite graph
Journal title :
Discrete Applied Mathematics
Serial Year :
2010
Journal title :
Discrete Applied Mathematics
Record number :
887371
Link To Document :
بازگشت