✦ LIBER ✦

Note on vertex-partitions of infinite graphs

✍ Scribed by János Pach; Joel H. Spencer

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 118 KB
Volume: 79
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90060-u

No coin nor oath required. For personal study only.

✦ Synopsis

Given an infinite graph G, let deg,(G) be defined as the smallest d for which V(G) can be partitioned into finite subsets of (uniformly) bounded size such that each part is adjacent to at most d others. A countable graph G is constructed with de&(G) > 2 and with the property that [{y~V(G):d(x, y)sn}lcCn for any xeV(G), n E N. This disproves conjectures of Cenzer and Howorka.

📜 SIMILAR VOLUMES

On vertex k-partitions of certain infini

On vertex k-partitions of certain infinite graphs

✍ Douglas Cenzer; Edward Howorka 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 826 KB

Let G be an infinite graph; define de& G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m Other sets of the partition. If G is either a regular tree 01 a triangtiisr, sqzart or hexagonal plana

Vertex partitions of chordal graphs

✍ David R. Wood 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into ‘bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro

Note on vertex degrees of planar graphs

✍ Miroslaw Truszczyáski 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 2 views

A note on vertex pancyclic oriented grap

A note on vertex pancyclic oriented graphs

✍ Bang-Jensen, J�rgen; Guo, Yubao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

Note on the reconstruction of vertex col

Note on the reconstruction of vertex colored graphs

✍ R. Taylor 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB 👁 2 views

A note on infinite transitive graphs

✍ Norbert Seifter 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 250 KB

In [4] Jung and Watkins proved that for a connected infinite graph X either r®(X) = oo holds or X is a strip, if Aut(X) contains a transitive abelian subgroup G. Here we prove the same result under weaker assumptions.