Digraph functors which admit both left and right adjoints. (English) Zbl 1305.05087
Summary: For our purposes, two functors \(\Lambda\) and \(\Gamma\) are said to be adjoint if for any digraphs \(G\) and \(H\), there exists a homomorphism of \(\Lambda(G)\) to \(H\) if and only if there exists a homomorphism of \(G\) to \(\Gamma(H)\). We investigate the right adjoints characterised by A. Pultr [Lect. Notes Math. 137, 100–113 (1970; Zbl 0203.31401)]. We find necessary conditions for these functors to admit right adjoints themselves. We give many examples where these necessary conditions are satisfied, and the right adjoint indeed exists. Finally, we discuss a connection between these right adjoints and homomorphism dualities.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 18A40 | Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) |
Citations:
Zbl 0203.31401References:
| [1] | Foniok, J.; Tardif, C., Adjoint functors and tree duality, Discrete Math. Theor. Comput. Sci., 11, 2, 97-110 (2009) · Zbl 1196.05035 |
| [2] | Hajiabolhassan, H.; Taherkhani, A., Graph powers and graph homomorphisms, Electron. J. Combin., 17, R17 (2010), 16 pages · Zbl 1215.05065 |
| [3] | Hell, P.; Nešetřil, J., (Graphs and Homomorphisms. Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28 (2004), Oxford University Press) · Zbl 1062.05139 |
| [4] | Komárek, P., Good characterisations in the class of oriented graphs (1987), Czechoslovak Academy of Sciences: Czechoslovak Academy of Sciences Prague, In Czech (Dobré charakteristiky ve třídě orientovaných grafů) |
| [5] | Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B, 80, 1, 80-97 (2000) · Zbl 1024.05078 |
| [6] | Pultr, A., The right adjoints into the categories of relational systems, (Reports of the Midwest Category Seminar, IV. Reports of the Midwest Category Seminar, IV, Lecture Notes in Mathematics, vol. 137 (1970), Springer: Springer Berlin), 100-113 · Zbl 0203.31401 |
| [7] | Tardif, C., Multiplicative graphs and semi-lattice endomorphisms in the category of graphs, J. Combin. Theory Ser. B, 95, 2, 338-345 (2005) · Zbl 1078.05081 |
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.
