Decidability of plane edge coloring with three colors

MaRDI QIDQ6236638zbMATH OpenFDO

Authors Hung-Hsun Chen, Wen-Guei Hu, De-Jan Lai, Song-Sun Lin

Publication date 24 October 2012

Abstract: This investigation studies the decidability problem of plane edge coloring with three symbols. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of $p$ colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set $B$ of Wang tiles, the decision problem is to find an algorithm to determine whether or not $Sigma(B)eqemptyset$, where $Sigma(B)$ is the set of all global patterns on $mathbb{Z}^2$ that can be constructed from the Wang tiles in $B$. When $pgeq5$, the problem is known to be undecidable. When $p=2$, the problem is decidable. This study proves that when $p=3$, the problem is also decidable. $mathcalP(B)$ is the set of all periodic patterns on $mathbb{Z}^2$ that can be generated by the tiles in $B$. If $mathcalP(B)eqemptyset$, then $B$ has a subset $B^{\prime }$ of minimal cycle generators such that $mathcalP(B^{\prime })eqemptyset$ and $$ for $$. This study demonstrates that the set $mathcalC(3)$ of all minimal cycle generators contains $787,605$ members that can be classified into $2,906$ equivalence classes. $mathcalN(3)$ is the set of all maximal non-cycle generators: if $BinmathcalN(3)$, then $mathcalP(B)=emptyset$ and $mathcalP(ildeB)eqemptyset$ for $ildeBsupsetneqqB$. The problem is shown to be decidable by proving that $BinmathcalN(3)$ implies $Sigma(B)=emptyset$. Consequently, $Sigma(B)eqemptyset$ if and only if $mathcalP(B)eqemptyset$.

This page was built for publication: Decidability of plane edge coloring with three colors

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