The effect of two cycles on the complexity of colourings by directed graphs (Q911612): Difference between revisions

Let H be a fixed digraph. An H-colouring of a digraph D is a mapping f: V(D)\(\to V(H)\) such that if xy is an arc in D then f(x)f(y) is an arc in H. The authors discuss various classes of digraphs H in which the existence of two directed cycles makes the H-colouring problem NP-hard.

0 references

Mathematics Subject Classification ID

05C15

0 references

0 references

0 references

graph colouring

0 references

digraphs

0 references

directed cycles

0 references

H-colouring problem

0 references

NP-hard

0 references

0 references

0 references

0 references

MaRDI publication profile

0 references

cites work

Q3758851

0 references

The Complexity of Colouring by Semicomplete Digraphs

0 references

On the complexity of colouring by superdigraphs of bipartite graphs

0 references

Hereditarily hard \(H\)-colouring problems

0 references

On unavoidable digraphs in orientations of graphs

0 references

Q4198056

0 references

On multiplicative graphs and the product conjecture

0 references

On the complexity of the general coloring problem

0 references

On classes of relations and graphs determined by subobjects and factorobjects

0 references

full work available at URL

https://doi.org/10.1016/0166-218x(90)90017-7

0 references

OpenAlex ID

W2021465457

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:911612

@@ Property / author @@
-Jörgen Bang-Jensen
@@ Property / author: Jörgen Bang-Jensen / rank @@
-Normal rank
@@ Property / author @@
-Q790131
@@ Property / author: Q790131 / rank @@
-Normal rank
@@ Property / reviewed by @@
-John W. Moon
@@ Property / reviewed by: John W. Moon / rank @@
-Normal rank
@@ Property / author @@
+Jörgen Bang-Jensen
@@ Property / author: Jörgen Bang-Jensen / rank @@
+Normal rank
@@ Property / author @@
+Pavol Hell
@@ Property / author: Pavol Hell / rank @@
+Normal rank
@@ Property / reviewed by @@
+John W. Moon
@@ Property / reviewed by: John W. Moon / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758851
@@ Property / cites work: Q3758851 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Colouring by Semicomplete Digraphs
+Normal rank
@@ Property / cites work @@
+On the complexity of colouring by superdigraphs of bipartite graphs
+Normal rank
@@ Property / cites work @@
+Hereditarily hard \(H\)-colouring problems
@@ Property / cites work: Hereditarily hard \(H\)-colouring problems / rank @@
+Normal rank
@@ Property / cites work @@
+On unavoidable digraphs in orientations of graphs
@@ Property / cites work: On unavoidable digraphs in orientations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+On multiplicative graphs and the product conjecture
+Normal rank
@@ Property / cites work @@
+On the complexity of the general coloring problem
@@ Property / cites work: On the complexity of the general coloring problem / rank @@
+Normal rank
@@ Property / cites work @@
+On classes of relations and graphs determined by subobjects and factorobjects
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0166-218x(90)90017-7
+Normal rank
@@ Property / OpenAlex ID @@
+W2021465457
@@ Property / OpenAlex ID: W2021465457 / rank @@
+Normal rank