Technical Report

 

Graph folding Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/technical_reports/4x51hs28p

Descriptions

Attribute NameValues
Alternative Title
Creator
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
Date Issued
Academic Affiliation
Series
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

Items