34
$\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

$\endgroup$
7
  • 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, 2015 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, 2015 at 14:22
  • 1
    $\begingroup$ Has anyone informed the website maintainers about the error? $\endgroup$
    – Mark S.
    Jul 11, 2015 at 0:02
  • $\begingroup$ @MarkS. I just did. $\endgroup$
    – Jakub Konieczny
    Jul 11, 2015 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, 2015 at 12:23

1 Answer 1

Reset to default
45
$\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

$\endgroup$
4
  • $\begingroup$ This would seem to work. Thanks! $\endgroup$
    – Jakub Konieczny
    Jul 10, 2015 at 14:24
  • $\begingroup$ You're welcome! $\endgroup$
    – n55
    Jul 10, 2015 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, 2015 at 8:59
  • $\begingroup$ Wow, I didn't see that... Thanks for letting me know! $\endgroup$
    – n55
    Jul 11, 2015 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.