1
$\begingroup$

A graph can be expressed as an structure $G = <A,R>$ satisfying the axioms $ \forall xy R(x,y) \rightarrow R(y,x)$ and $ \forall x \lnot R(x,x)$.

How to extend the structure and/or axioms to express a 5 colourable graph?

|cite|improve this question
$\endgroup$
2
$\begingroup$

General ideas:

  • Require that each vertex ($\forall x \ldots$) satisfies at least one color predicate (Use $\lor$ among five color predicates).
  • Also require that no vertex ($\lnot\exists x \ldots$) has two distinct colors (you can enumerate all the ten distinct pairs: $\lnot({\sf red}(x)\land{\sf blue}(x))\land \lnot(\ldots)\land \cdots$).
  • For each color (repeat this axiom five times, once for each color), require that if $x$ has that color and $R(x,y)$ then $y$ has not that color (e.g. $\forall x y.\ {\sf red}(x)\land R(x,y) \implies \lnot{\sf red}(y)$).
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Point two: How would a general requirement look like? $\endgroup$ – brandstifter May 13 '18 at 13:43
  • $\begingroup$ @brandstifter See the edit. $\endgroup$ – chi May 13 '18 at 13:50
  • 1
    $\begingroup$ You actually don't need the second requirement. $\endgroup$ – Yuval Filmus May 13 '18 at 15:54
  • $\begingroup$ @YuvalFilmus That's true -- for formalizing color-ability we do not need to state that each vertex has exactly one color, but only that it has at least one color. For some other properties it could be useful to require it. $\endgroup$ – chi May 13 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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