0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you looking for a coloring in the standard sense? I.e., the endpoints of each edge must have different colors? $\endgroup$
    – Steven
    Oct 6, 2021 at 11:29
  • $\begingroup$ @Steven Not in the traditional sense, two endpoints of edge may have the same color $\endgroup$
    – Andy
    Oct 6, 2021 at 11:33

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – Andy
    Oct 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$
    – Steven
    Oct 7, 2021 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.