Homomorphisms to oriented paths.

*(English)*Zbl 0819.05030A homomorphism of a digraph \(G= (V, A)\) to a digraph \(H= (V', A')\) is a mapping \(f: V\to V'\) of the vertices of \(G\) to the vertices of \(H\) (not necessarily onto) which preserves arcs, i.e., such that \(xy\in A\) implies \(f(x) f(y)\in A'\). If such a homomorphism exists, \(G\) is said to be homomorphic to \(H\) and the notation \(G\to H\) is used. Otherwise the notation \(G\nrightarrow H\) is used.

Given an oriented path \(P\), the authors characterize those digraphs \(G\) which are homomorphic to \(P\). The characterization equates the nonexistence of a homomorphism \(G\to P\) with the existence of a homomorphism \(W\to G\), for some oriented path \(W\) which is not homomorphic to \(P\). This result complements the recent polynomial time algorithm of W. Gutjahr, E. Welzl and G. Woeginger to find such a homomorphism (if one exists) [Polynomial graph-colorings, Discrete Appl. Math. 35, No. 1, 29-45 (1992; Zbl 0761.05040)].

Say that \(H\) has tree-duality if \(G\nrightarrow H\) if and only if there is an oriented tree \(T\) such that \(T\to G\) and \(T\nrightarrow H\). The main result in this paper is that oriented paths have tree-duality. In another recent paper with J. Nešetřil, the authors have proved that whenever \(H\) has tree-duality then there is a polynomial algorithm to test for the existence of homomorphisms to \(H\).

Given an oriented path \(P\), the authors characterize those digraphs \(G\) which are homomorphic to \(P\). The characterization equates the nonexistence of a homomorphism \(G\to P\) with the existence of a homomorphism \(W\to G\), for some oriented path \(W\) which is not homomorphic to \(P\). This result complements the recent polynomial time algorithm of W. Gutjahr, E. Welzl and G. Woeginger to find such a homomorphism (if one exists) [Polynomial graph-colorings, Discrete Appl. Math. 35, No. 1, 29-45 (1992; Zbl 0761.05040)].

Say that \(H\) has tree-duality if \(G\nrightarrow H\) if and only if there is an oriented tree \(T\) such that \(T\to G\) and \(T\nrightarrow H\). The main result in this paper is that oriented paths have tree-duality. In another recent paper with J. Nešetřil, the authors have proved that whenever \(H\) has tree-duality then there is a polynomial algorithm to test for the existence of homomorphisms to \(H\).

Reviewer: J.Bang-Jensen (Odense)

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

05C38 | Paths and cycles |

05C75 | Structural characterization of families of graphs |

05C15 | Coloring of graphs and hypergraphs |

##### Keywords:

\(H\)-colourings; homomorphism; digraph; oriented path; characterization; tree-duality; polynomial algorithm
PDF
BibTeX
XML
Cite

\textit{P. Hell} and \textit{X. Zhu}, Discrete Math. 132, No. 1--3, 107--114 (1994; Zbl 0819.05030)

Full Text:
DOI

##### References:

[1] | Bang-Jensen, J.; Hell, P., On the effect of two cycles on the complexity of colouring, Discrete appl. math., 26, 1-23, (1990) · Zbl 0697.05029 |

[2] | Bang-Jensen, J.; MacGillivray, G.; Hell, P., The complexity of colouring by semicomplete digraphs, SIAM J. discrete math., 1, 281-298, (1988) · Zbl 0678.05018 |

[3] | Bang-Jensen, J.; Hell, P.; MacGillivray, G., On the complexity of colouring by superdigraphs of bipartite graphs, Discrete math., 109, 27-44, (1992) · Zbl 0783.05047 |

[4] | J. Bang-Jensen, P. Hell and G. MacGillivray, Hereditarily hard-colouring problems, Discrete Math., to appear. · Zbl 0816.68090 |

[5] | Burr, S.; Erdős, P.; Lovász, On graphs of Ramsey type, Ars combin., 1, 167-190, (1976) |

[6] | Gutjahr, W., Graph colorings, () · Zbl 0761.05040 |

[7] | Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph colourings, Discrete appl. math., 35, 29-46, (1992) |

[8] | Häggkvist, R.; Hell, P.; Miller, D.J.; Neumann-Lara, V., On multiplicative graphs and the product conjecture, Combinatorica, 8, 71-81, (1988) · Zbl 0657.05028 |

[9] | Hell, P.; Nešetřil, J., On the complexity of H-colouring, J. combin. theory ser. B, 48, 92-110, (1990) · Zbl 0639.05023 |

[10] | Hell, P.; Zhou, H.; Zhu, X., Homomorphisms to oriented cycles, Combinatorica, 13, 421-433, (1993) · Zbl 0794.05037 |

[11] | P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. Discrete Math, to appear. · Zbl 0831.05059 |

[12] | Komárek, P., Some new good characterizations of directed graphs, Časopis Pěst. mat., 51, 348-354, (1984) · Zbl 0569.05022 |

[13] | MacGillivray, G., On the complexity of colourings by vertex-transitive and arc-transitive digraphs, SIAM J. discrete math., 4, 397-408, (1991) |

[14] | Maurer, H.A.; Sudborough, J.H.; Welzl, E., On the complexity of the general coloring problem inform. and control, 51, 123-145, (1981) · Zbl 0502.68015 |

[15] | Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete math., 22, 287-300, (1978) · Zbl 0388.05039 |

[16] | Welzl, E., Symmetric graphs and interpretations, J. combin. theory ser. B, 37, 235-244, (1984) · Zbl 0547.05058 |

[17] | Zhou, H., Homomorphism properties of graph products, () |

[18] | Zhu, X., Multiplicative structures, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.