Graph folding

Technical Report

公开 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)
权利声明	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

缩略图	标题	上传日期	公开度	行动
	Cook_Evans_79_20_02.pdf	2022-12-19	公开	下载