33
$\begingroup$

The illustration on Wolfram's page claims to present a uniquely colorable, triangle-free graph. However, this seems to be blatantly false: the graph has a symmetry with respect to a reflection through the horizontal axis, and we can use this symmetry to construct a new colouring not isomorphic to the original one.

Am I missing something obvious here, or is the illustration simply wrong? If it's the latter, what is a simple example of a triangle-free, uniquely 3-colourable graph?

enter image description here

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ My graph theory is weak, and as such it is not obvious to me why the reflective symmetry should guarantee a coloring not isomorphic to the original one. Can you elaborate just a bit or provide a reference? $\endgroup$ – J. Loreaux Jul 10 '15 at 14:09
  • $\begingroup$ @J.Loreaux As defined by Wolfram (and I think this is the usual definition) two colourings are distinct if they give a different partition (see the linked page, first definition). $\endgroup$ – Jakub Konieczny Jul 10 '15 at 14:22
  • 1
    $\begingroup$ Has anyone informed the website maintainers about the error? $\endgroup$ – Mark S. Jul 11 '15 at 0:02
  • $\begingroup$ @MarkS. I just did. $\endgroup$ – Jakub Konieczny Jul 11 '15 at 8:09
  • 1
    $\begingroup$ @DavidRicherby: The issue is not left-right symmetry, but up-down symmetry. The right-left symmetry is indeed harmless. $\endgroup$ – Jakub Konieczny Jul 11 '15 at 12:23
44
$\begingroup$

Yes, Wolfram is wrong in this case. I just checked the archives of the Journal of Combinatorial Theory (where the erratum to the paper in question is published) and the two top vertices are supposed to be connected by an edge.

I cannot provide a link because it requires a login, and I was able to log in through my university's subscription to the journal.

Graph with added line

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This would seem to work. Thanks! $\endgroup$ – Jakub Konieczny Jul 10 '15 at 14:24
  • $\begingroup$ You're welcome! $\endgroup$ – n55 Jul 10 '15 at 14:25
  • 3
    $\begingroup$ I assume you mean the articles doi:10.1016/S0021-9800(70)80027-8 and doi:10.1016/S0021-9800(69)80086-4. They seem to be freely accessible. (They are marked as Open Archive.) $\endgroup$ – Martin Sleziak Jul 11 '15 at 8:59
  • $\begingroup$ Wow, I didn't see that... Thanks for letting me know! $\endgroup$ – n55 Jul 11 '15 at 15:59

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.