Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902892 | Discrete Mathematics | 2018 | 6 Pages |
Abstract
Given an infinite leafless tree drawn on the plane, we ask whether or not one can add edges between the vertices of the tree obtaining a non-3-face-colorable graph. We formulate a condition conjectured to be necessary and sufficient for this to be possible. We prove that this condition is indeed necessary and sufficient for trees with maximal degree 3, and that it is sufficient for general trees. In particular, we prove that every infinite plane graph with a spanning binary tree is 3-face-colorable.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Eli Berger, Yanay Soker,