Note on vertex-partitions of infinite graphs

János Pach, Joel H. Spencer

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)107-108
Number of pages2
JournalDiscrete Mathematics
Issue number1
StatePublished - Jan 1 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Note on vertex-partitions of infinite graphs'. Together they form a unique fingerprint.

Cite this