A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set C of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to C is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm212-3-2,
author = {Nick Haverkamp},
title = {Countable splitting graphs},
journal = {Fundamenta Mathematicae},
volume = {215},
year = {2011},
pages = {217-233},
zbl = {1258.03064},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm212-3-2}
}
Nick Haverkamp. Countable splitting graphs. Fundamenta Mathematicae, Tome 215 (2011) pp. 217-233. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm212-3-2/