On two coloring problems in mixed graphs (Q2426450): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2075902025 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hard coloring problems in low degree planar bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mixed graph colorings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4838466 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4281630 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3949076 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smallest-last ordering and clustering and graph coloring algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloring some classes of mixed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2712373 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2784175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4120593 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling Problems and Mixed Graph Colorings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reasoning about qualitative temporal information / rank | |||
Normal rank |
Latest revision as of 21:56, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On two coloring problems in mixed graphs |
scientific article |
Statements
On two coloring problems in mixed graphs (English)
0 references
22 April 2008
0 references
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.
0 references
mixed graph
0 references
strong mixed graph colouring
0 references
weak mixed graph colouring
0 references
bipartite graph
0 references
k-tree
0 references
computational complexity
0 references