Affordable Access

Publisher Website

On vertex k-partitions of certain infinite graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
23
Issue
2
Identifiers
DOI: 10.1016/0012-365x(78)90110-3

Abstract

Abstract Let G be an infinite graph; define deg∞ 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 on a triangular, square or hexagonal planar mosaic graph, it is shown that deg∞ G equals the degree of G. This verifies some conjectures of S. Ulam. Several open problems are given.

There are no comments yet on this publication. Be the first to share your thoughts.