Note on vertex-partitions of infinite graphs

János Pach; Joel H. Spencer

doi:10.1016/0012-365X(90)90060-U

Note on vertex-partitions of infinite graphs

János Pach, Joel H. Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	107-108
Number of pages	2
Journal	Discrete Mathematics
Volume	79
Issue number	1
DOIs	https://doi.org/10.1016/0012-365X(90)90060-U
State	Published - Jan 1 1990

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

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

Cite this

@article{ffb8b06b18c746e59689a0101e9da3ac,

title = "Note on vertex-partitions of infinite graphs",

abstract = "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.",

author = "J{\'a}nos Pach and Spencer, {Joel H.}",

year = "1990",

month = jan,

day = "1",

doi = "10.1016/0012-365X(90)90060-U",

language = "English (US)",

volume = "79",

pages = "107--108",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Note on vertex-partitions of infinite graphs

AU - Pach, János

AU - Spencer, Joel H.

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

SN - 0012-365X

VL - 79

SP - 107

EP - 108

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

Note on vertex-partitions of infinite graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this