21–30 of 77 posts
Long time ago I failed to solve this conjecture. Nice to see it have been solved. I shared some email with S. Hetdetniemi about some special cases. Good old times.
What results and special cases did you work on?
> Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering).
I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem.
Does anyone know of a resource that provides a more intuitive explanation for this for non-graph-theorists?
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…
COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…
It's also got a lot of videos on other cool math stuff.
Beautiful article, though not sure why two examples are introduced (students x instruments, and jobs x hobbies). The abstract for Shitov's paper is also a gem of brevity, here reproduced in its entirety: "The chromatic number of G×H can be smaller than the minimum of the chromatic numbers of finite simple graphs G and H." (And, of course, the first reference in the paper is co-authored by Erdős.)
The second example was used to show how colouring the tensor product may actually be useful.
I thought the second example was a little more complex (primarily because it requires the connection of incompatible nodes, as opposed to the more straightforward pairing of compatible nodes), so having a different, more straight forward example to just explain tensor products was helpful.
Also, having 2 different unrelated examples for the same thing can definitely help with understanding the underlying property/theorem.
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…
Intuitive explanation about the proof? That might be tricky because it took a computer to prove it.
There’s also a good popular overview of the history of the problem in the book “Four Colors Suffice” by Robin Wilson.
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…
It required a notoriously hard-to-simplify proof, which required computer assisted brute force analysis. But an intuition is that a complete graph with four nodes is planar, and five is not. A (3,3) bipartite graph is also the smallest non-planar bipartite graph. That's probably good for answering "why would you suspect 4".
> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…