Absolutely 3‐chromatic graphs
Anthony B. Evans · Journal of Graph Theory · 1986
Abstract A fold is a sequence of simple folds (elementary homomorphisms in which the identified vertices are both adjacent to a common vertex). It was shown in (C. R. Cook and A. B. Evans, Graph folding. Proceedings of the South Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, 1979, pp. 305–314) that all connected n‐chromatic graphs can be folded onto Kn. A connected n‐chromatic graph is called absolutely n‐chromatic if it can only be folded onto Km when m = n. Some classes of absolutely n‐chromatic graphs were given in Cook and Evans. In this paper, we classify the absolutely 3‐chromatic graphs.