On infinite graphs with a specified number of colorings |
| |
Authors: | Stephen H Hechler |
| |
Institution: | Queens College of the City University of New York, Flushing, NY 11367, U.S.A. |
| |
Abstract: | In this paper we construct a planar graph of degree four which admits exactly Nu 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between Nu and 2Nu and that an appropriate generalization holds for at least certain nondenumerable graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|