×

Density via duality. (English) Zbl 1058.05062

Summary: We present an unexpected correspondence between homomorphism duality theorems and gaps in the poset of graphs and their homomorphisms. This gives a new proof of the density theorem for undirected graphs and solves the density problem for directed graphs.

MSC:

05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[2] Duffus, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi’s conjecture, Discrete Math., 152, 125-139 (1996) · Zbl 0853.06006
[3] El-Zahar, H.; Sauer, N., The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica, 5, 121-126 (1985) · Zbl 0575.05028
[4] Erdős, P., Graph theory and probability, Canad. J. Math., 11, 34-38 (1959) · Zbl 0084.39602
[5] T. Gallai, On directed paths and circuits, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, 115-118.; T. Gallai, On directed paths and circuits, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, 115-118.
[6] S.H. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan, Technical Report 03105-44-T, 1966.; S.H. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan, Technical Report 03105-44-T, 1966.
[7] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colourings, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[8] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc., 348, 1281-1297 (1996) · Zbl 0877.05055
[9] P. Komárek, Good characterizations in the class of oriented graphs, Ph. D. Thesis, Charles University, Prague, 1987 (in Czech).; P. Komárek, Good characterizations in the class of oriented graphs, Ph. D. Thesis, Charles University, Prague, 1987 (in Czech).
[10] Lovász, L., Operations with structures, Acta Math. Acad. Sci. Hungar., 18, 321-328 (1967) · Zbl 0174.01401
[11] Minty, G. J., A theorem on \(n\)-coloring the points of a linear graph, Amer. Math. Monthly, 69, 623-624 (1962) · Zbl 0108.36601
[12] Nešetřil, J., The homomorphism structure of classes of graphs, recent trends in combinatorics (Mátraháza, 1995), Combin. Probab. Comput., 8, 177-184 (1999)
[13] 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
[14] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterizing gaps and good characterizations), J. Combin. Theory Ser. B, 80, 80-97 (2000) · Zbl 1024.05078
[15] Roy, B., Nombre chromatique et plus longs chemins d’un graphe, Rev. Francaise Informat. Recherche Opérationelle, 1, 129-132 (1967) · Zbl 0157.31302
[16] Stanley, R. P., Acyclic orientations of graphs, Discrete Math., 5, 171-178 (1973) · Zbl 0258.05113
[17] Welzl, E., Color-families are dense, J. Theoret. Comput. Sci., 17, 29-41 (1982) · Zbl 0482.68063
[18] Zhu, X., A survey on Hedetniemi’s conjecture, Taiwan. J. Math., 2, 1-24 (1998) · Zbl 0906.05024
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.