×

Homomorphisms to oriented paths. (English) Zbl 0819.05030

A 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\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0761.05040
PDFBibTeX XMLCite
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.; 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, (Ph.D. Thesis (1991), Freie Universität Berlin) · 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.; 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, (Ph.D. Thesis (1988), Simon Fraser University)
[18] Zhu, X., Multiplicative structures, (Ph.D. Thesis (1990), The University of Calgary)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.