Graph Coloring and Function Simulation

Details Graph Coloring and Function Simulation Graph Coloring and Function Simulation

2010-08-18

arxiv.org/abs/1008.3015v1

Mathematics

Combinatorics

Scientific paper

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,\ldots,m-1\}$ and a number $n \geq \max\{m,3\}$, any partial function $\varphi:S^{^p} \to S^{^q}$ (i.e. it may not be defined on some elements of its domain $S^{^p}$) can be effectively (i.e. in polynomial time) transformed to a simple graph $\matr{G}_{_{\varphi,n}}$ along with 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 \leq i < n$, is {\it uniquely} and {\it effectively} extendable to a proper $n$-coloring $\sigma$ of $\matr{G}_{_{\varphi,n}}$ for which we have $$\varphi(\sigma(x_{_{0}}),\sigma(x_{_{1}}),\ldots,\sigma(x_{_{p-1}}))=(\sigma(y_{_{0}}),\sigma(y_{_{1}}),\ldots,\sigma(y_{_{q-1}})),$$ unless $(\sigma(x_{_{0}}),\sigma(x_{_{1}}),\ldots,\sigma(x_{_{p-1}}))$ is not in the domain of $\varphi$ (in which case $\sigma_{_{0}}$ has no extension to a proper $n$-coloring of $\matr{G}_{_{\varphi,n}}$).

Affiliated with

Also associated with

No associations

Rating

Graph Coloring and Function Simulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Coloring and Function Simulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Coloring and Function Simulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-504098