✦ LIBER ✦

Cut-sets in infinite graphs and partial orders

✍ Scribed by A. Hajnal; N. Sauer

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 859 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90328-q

No coin nor oath required. For personal study only.

✦ Synopsis

Hajnal, A. and N. Sauer, Cut-sets in infinite graphs and partial orders. Discrete Mathematics 117 (1993) 113-125.

The set S c V(U) is a cut-set of the vertex v of a graph 9 if v is not adjacent to any vertex in S and, for every maximal clique C of Q, ({v} u S) n C # 0. S is a cut-set of the element v of a partial order 9 if S is a cut-set of v in the comparability graph of 8. Given upper bounds for the clique sizes and cut-set sizes of g, we will determine the largest size of an independent set of vertices of Q. If 4 is the comparability graph of some partial order 9, we will also determine the best possible upper bounds for the size of a maximal antichain of 8.

📜 SIMILAR VOLUMES

Complete subgraphs of infinite multipart

Complete subgraphs of infinite multipartite graphs and antichains in partially ordered sets

✍ A. Hajnal; N. Sauer 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 393 KB

Finite invariant sets in infinite graphs

✍ Norbert Polat 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 795 KB

The closure of a set A of vertices of an infinite graph G is defined as the set of vertices of G which cannot be finitely separated from A. A subset A of Y(G) is dispersed if it is finitely separated from any ray of G. It is shown that the closure of any dispersed set A of an infinite connected grap

On Definitions of Cuts and Completion of

On Definitions of Cuts and Completion of Partially Ordered Sets

✍ Alexander Abian 📂 Article 📅 1968 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 1 views

Comparability graphs with constraint, pa

Comparability graphs with constraint, partial semi-orders and interval orders

✍ Claude Flament 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 580 KB

A symmetric, anfireflexive relation S is a comparability graph ff one can assign a transitive orientation to the edges: we obtain a partial order. We say that S is a comparability graph with constraint C, a subrelation of S, if S has a transitive orientation including C. A characterization is given

Large k-preserving sets in infinite grap

Large k-preserving sets in infinite graphs

✍ Andreas Huck; Frank Niedermeyer; Saharon Shelah 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 715 KB

## Abstract Let __K__ be a cardinal. If __K__ χ~0~, define K:= __K__. Otherwise, let __K__ := __K__ + 1. We prove a conjecture of Mader: Every infinite __K__‐connected graph __G__ = (__V, E__) contains a set __S__ ⊆ __V__ with |__S__| = |__V__| such that __G/S__ is __K__‐connected for all __S__⊆ __

On finite fixed sets in infinite graphs

✍ H.A. Jung 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 762 KB

## An automorphism of a graph X is called a translation of X if it fixes no finite non-empty set of vertices of X. It is shown that a group G of automorphisms of the connected graph X fixes a finite non-empty set of vertices or ends of X if and only if any two translations of X in G have a common