Graph Coloring and Function Simulation

MaRDI QIDQ6220257zbMATH OpenFDO

Authors Amir Daneshgar, Alireza Rahimi, Siamak Taati

Publication date 18 August 2010

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $ngeqmaxm,3$, any partial function $varphi:S^{{}^p}o{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 ${\displaystyle }$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}},${\displaystyle }$ such that any assignment $sigm{a}_{{}_0}:XcupRo0,1,ldots,n-1$ with $sigm{a}_{{}_0}(Kvi)=i$ for all $0leqi<n$, is {it uniquely} and {it effectively} extendable to a proper $n$-coloring $sigma$ of $matr{G}_{{}_{varphi,n}}$ for which we have ${\displaystyle }$varphi(sigma(x_{_{0}}),sigma(x_{_{1}}),ldots,sigma(x_{_{p-1}}))=(sigma(y_{_{0}}),sigma(y_{_{1}}),ldots,sigma(y_{_{q-1}})),${\displaystyle }$ unless $(sigma(x_{{}_0}),sigma(x_{{}_1}),ldots,sigma(x_{{}_{p-1}}))$ is not in the domain of $varphi$ (in which case $sigm{a}_{{}_0}$ has no extension to a proper $n$-coloring of $matr{G}_{{}_{varphi,n}}$).

This page was built for publication: Graph Coloring and Function Simulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6220257)