On two coloring problems in mixed graphs (Q2426450): Difference between revisions

A mixed graph \(G_M=(V,U,E)\) is a graph with vertex set \(V\), edge set \(E\) and arc set \(U\). A strong mixed graph \(p\)-colouring of \(G_M\) is a mapping \(c:V \to \{0,1,\dots, p-1\}\) such that, for each edge \(\{u,v\}\in E\), \(c(u)\neq c(v)\) and for each arc \((x,y)\), \(c(x)<c(y)\). The strong mixed chromatic number \(\gamma_m(G_m)\) of \(G_m\) is the smallest integer \(p\) such that \(G_m\) admits a strong mixed \(p\)-colouring. The weak mixed chromatic number is defined in analogous way with the only difference that vertices linked by an arc can have the same colour. The authors present some bounds on the strong and weak mixed chromatic numbers. Some complexity results related to bipartite planar graphs with bounded maximum degree and partial \(k\)-trees are presented as well.