TY - JOUR

T1 - Note on vertex-partitions of infinite graphs

AU - Pach, János

AU - Spencer, Joel H.

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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 deg∞(G)>2 and with the property that |{yε{lunate}V(G):d(x,y)≤n}|≤Cn for any xε{lunate}V(G), nε{lunate}N. This disproves conjectures of Cenzer and Howorka.

AB - 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 deg∞(G)>2 and with the property that |{yε{lunate}V(G):d(x,y)≤n}|≤Cn for any xε{lunate}V(G), nε{lunate}N. This disproves conjectures of Cenzer and Howorka.

UR - http://www.scopus.com/inward/record.url?scp=45149135960&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45149135960&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(90)90060-U

DO - 10.1016/0012-365X(90)90060-U

M3 - Article

AN - SCOPUS:45149135960

VL - 79

SP - 107

EP - 108

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1

ER -