Graph Coloring and Function Simulation - Mathematics > CombinatoricsReport as inadecuate

Graph Coloring and Function Simulation - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: We prove that every partial function with finite domain and range can beeffectively simulated through sequential colorings of graphs. Namely, we showthat given a finite set $S=\{0,1,\ldots,m-1\}$ and a number $n \geq\max\{m,3\}$, any partial function $\varphi:S^{^p} \to S^{^q}$ i.e. it may notbe defined on some elements of its domain $S^{^p}$ can be effectively i.e. inpolynomial time transformed to a simple graph $\matr{G} { {\varphi,n}}$ alongwith three sets of specified vertices $$X =\{x { {0}},x { {1}},\ldots,x { {p-1}}\}, \ \ Y =\{y { {0}},y { {1}},\ldots,y { {q-1}}\}, \ \ R =\{\Kv{0},\Kv{1},\ldots,\Kv{n-1}\},$$ such that any assignment $\sigma { {0}}: X\cup R \to \{0,1,\ldots,n-1\} $ with $\sigma { {0}}\Kv{i}=i$ for all $0 \leqi < n$, is {\it uniquely} and {\it effectively} extendable to a proper$n$-coloring $\sigma$ of $\matr{G} { {\varphi,n}}$ for which we have$$\varphi\sigmax { {0}},\sigmax { {1}},\ldots,\sigmax { {p-1}}=\sigmay { {0}},\sigmay { {1}},\ldots,\sigmay { {q-1}},$$unless $\sigmax { {0}},\sigmax { {1}},\ldots,\sigmax { {p-1}}$ is notin the domain of $\varphi$ in which case $\sigma { {0}}$ has no extension to aproper $n$-coloring of $\matr{G} { {\varphi,n}}$.

Author: Amir Daneshgar, Ali Reza Rahimi, Siamak Taati


Related documents