Graph Coloring and Function Simulation

Original · EN

We prove that every partial function with finite domain and range can be effectively simulated through sequential colorings of graphs. Namely, we show that given a finite set S={0,1,,m-1} and a number n ≥ {m,3}, any partial function φ:Sᵖ → Sq (i.e. it may not be defined on some elements of its domain Sᵖ) can be effectively (i.e. in polynomial time) transformed to a simple graph Gᵩ,ₙ along with three sets of specified vertices X = {x₀,x₁,,xₚ₋₁}, Y = {y₀,y₁,,yq₋₁}, R = {0,1,,n-1}, such that any assignment σ₀: X ∪ R → {0,1,,n-1} with σ₀(i)=i for all 0 ≤ i < n, is uniquely and effectively extendable to a proper n-coloring σ of Gᵩ,ₙ for which we have φ(σ(x₀),σ(x₁),,σ(xₚ₋₁))=(σ(y₀),σ(y₁),,σ(yq₋₁)), unless (σ(x₀),σ(x₁),,σ(xₚ₋₁)) is not in the domain of φ (in which case σ₀ has no extension to a proper n-coloring of Gᵩ,ₙ).