ﻻ يوجد ملخص باللغة العربية
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.
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For every real $alphainleft[ 0,1right] $, write $A_{alpha}left( Gright) $ for the matrix [ A_{alpha}left( Gright) =alpha Dleft( Gright) +(1-a
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph con
We show that for $dge d_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)frac{n}{d}log d$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers
We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge
The age $mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is the collection of finite induced subgraphs of $G$, considered up to isomorphy and ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it contains no infin