On maximal finite antichains in the homomorphism order of directed graphs

Jaroslav Nesetril; Claude Tardif

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 325-332
  • ISSN: 2083-5892

Abstract

top
We show that the pairs T , D T where T is a tree and D T its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.

How to cite

top

Jaroslav Nesetril, and Claude Tardif. "On maximal finite antichains in the homomorphism order of directed graphs." Discussiones Mathematicae Graph Theory 23.2 (2003): 325-332. <http://eudml.org/doc/270213>.

@article{JaroslavNesetril2003,
abstract = {We show that the pairs $\{T,D_T\}$ where T is a tree and $D_T$ its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.},
author = {Jaroslav Nesetril, Claude Tardif},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chromatic number; homomorphism duality; tree; homomorphism ordering},
language = {eng},
number = {2},
pages = {325-332},
title = {On maximal finite antichains in the homomorphism order of directed graphs},
url = {http://eudml.org/doc/270213},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Jaroslav Nesetril
AU - Claude Tardif
TI - On maximal finite antichains in the homomorphism order of directed graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 325
EP - 332
AB - We show that the pairs ${T,D_T}$ where T is a tree and $D_T$ its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
LA - eng
KW - chromatic number; homomorphism duality; tree; homomorphism ordering
UR - http://eudml.org/doc/270213
ER -

References

top
  1. [1] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38, doi: 10.4153/CJM-1959-003-9. Zbl0084.39602
  2. [2] P. Hell, J. Nesetril and X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996) 1281-1297, doi: 10.1090/S0002-9947-96-01537-1. Zbl0877.05055
  3. [3] P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica 13 421-433, doi: 10.1007/BF01303514. Zbl0794.05037
  4. [4] P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. on Disc. Math. 8 (1995) 208-222. Zbl0831.05059
  5. [5] P. Komárek, Good characterisations in the class of oriented graphs (in Czech), Ph. D. Thesis (Charles University, Prague, 1987). 
  6. [6] P. Komárek, Some new good characterizations for directed graphs, Casopis Pest. Mat. 109 (1984) 348-354. Zbl0569.05022
  7. [7] J. Nesetril and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978) 287-300, doi: 10.1016/0012-365X(78)90062-6. Zbl0388.05039
  8. [8] J. Nesetril and S. Shelah, On the Order of Countable Graphs, ITI Series 200-002 (to appear in European J. Combin.). 
  9. [9] J. Nesetril and C. Tardif, Duality Theorems for Finite Structures (Characterizing Gaps and Good Characterizations), J. Combin. Theory (B) 80 (2000) 80-97, doi: 10.1006/jctb.2000.1970. 
  10. [10] J. Nesetril and C. Tardif, Density via Duality, Theoret. Comp. Sci. 287 (2002) 585-591, doi: 10.1016/S0304-3975(01)00263-8. Zbl1058.05062
  11. [11] J. Nesetril and X. Zhu, Path homomorphisms, Math. Proc. Cambridge Philos. Soc. 120 (1996) 207-220, doi: 10.1017/S0305004100074806. Zbl0857.05057

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.