We describe some metric properties of incomparability graphs. We consider the problem of the existence of infinite paths, either induced or isometric, in the incomparability graph of a poset. Among other things, we show that if the incomparability graph of a poset is connected and has infinite diameter then it contains an infinite induced path and furthermore if the diameter of set of vertices of degree at least $3$ is unbounded the graph contains as an induced subgraph either a comb or a kite. This result allows to draw a line between ages of permutation graphs which are well quasi order and those which are not.
تحميل البحث