For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be colored in $3$ colors with the following condition: For any edge $(u, v)\in E$, if $u$ and $v$ have different colors, then there exists $w\in V$ such that $(u, w)\in E$, $(v, w)\in E$, and $w$ has the third color (different from both $u$ and $v$). Here it is ok that two vertices of the same color may be connected by an edge.
2
-
$\begingroup$ Are you looking for a coloring in the standard sense? I.e., the endpoints of each edge must have different colors? $\endgroup$– StevenOct 6, 2021 at 11:29
-
$\begingroup$ @Steven Not in the traditional sense, two endpoints of edge may have the same color $\endgroup$– AndyOct 6, 2021 at 11:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Here is one possible formula: $\texttt{true}$. Indeed, every graph admits a coloring that satisfies your requirements: simply color all vertices with the same color.
-
$\begingroup$ Thanks. But if we color all vertices with the same color, the condition "For any edge $(u, v)\in E$, if $u$ and $v$ have different colors, there exists..." never happens? $\endgroup$– AndyOct 7, 2021 at 8:20
-
1$\begingroup$ That condition because trivially true since there are no edges $(u,v)$ that satisfy the requirements. Essentially, you are using an universal quantifier over an empty set. $\endgroup$– StevenOct 7, 2021 at 9:22