Graph folding

Technical Report

Öffentlich Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/technical_reports/4x51hs28p

Descriptions

Attribute Name	Values
Creator	Cook, Curtis R. Evans, Anthony B.
Abstract	A graph fold is the special case of a graph homomorphism where the two identified vertices are both adjacent to a common vertex. Like homomorphisms, folds are related to the chromatic number and we obtain an Interpolation Theorem for folds. If X(G) = n, then G is absolutely n-chromatic if every fold preserves the chromatic number. Every nontrivial bipartite graph is absolutely 2-chromatic. Given m ≥ 4, we give a construction of a three chromatic graph that folds onto Kₘ and conjecture that this is the smallest such graph.
Resource Type	Technical Report
Date Issued	1979
Academic Affiliation	Computer Science
Series	Technical report (Oregon State University. Department of Computer Science)
Urheberrechts-Erklärung	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

Miniaturansicht	Titel	Hochladedatum	Sichtbarkeit	Aktionen
	Cook_Evans_79_20_02.pdf	2022-12-19	Öffentlich	Herunterladen