How can this map be coloured using four colours?Four color theorem disproof?Did the Appel/Haken graph colouring (four colour map) proof really not contribute to understanding?Modeling a (rather silly) magnet problem using graphsWhy is TSP in NP?
Did thousands of women die every year due to illegal abortions before Roe v. Wade?
Does the "6 seconds per round" rule apply to speaking/roleplaying during combat situations?
Why don't B747s start takeoffs with full throttle?
On the Twin Paradox Again
How can drunken, homicidal elves successfully conduct a wild hunt?
Pronoun introduced before its antecedent
Should I "tell" my exposition or give it through dialogue?
Why doesn't my simple mesh wall "difference boolean cut" the door away?
Implement Homestuck's Catenative Doomsday Dice Cascader
How can I instantiate a lambda closure type in C++11/14?
Company did not petition for visa in a timely manner. Is asking me to work from overseas, but wants me to take a paycut
What do we gain with higher order logics?
What can plausibly explain many of my very long and low-tech bridges?
What is the advantage of carrying a tripod and ND-filters when you could use image stacking instead?
How is it possible that Gollum speaks Westron?
How to skip replacing first occurrence of a character in each line?
In this example, which path would a monster affected by the Dissonant Whispers spell take?
Importance sampling estimation of power function
What is the right way to float a home lab?
What is the purpose of building foundations?
My coworkers think I had a long honeymoon. Actually I was diagnosed with cancer. How do I talk about it?
What is in `tex.print` or `tex.sprint`?
Java guess the number
How do I write "Show, Don't Tell" as an Asperger?
How can this map be coloured using four colours?
Four color theorem disproof?Did the Appel/Haken graph colouring (four colour map) proof really not contribute to understanding?Modeling a (rather silly) magnet problem using graphsWhy is TSP in NP?
$begingroup$
I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps except this one, which after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality about it I've not fully understood (or I'm just bad at graph theory). I'd appreciate any help with solving this, and if possible an explanation of/link to a good algorithm to go about solving problems of this style.
Here's the map:
graph-theory coloring
edited 8 hours ago
Morgan Rodgers
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
$endgroup$
|
show 1 more comment
$begingroup$
I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps except this one, which after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality about it I've not fully understood (or I'm just bad at graph theory). I'd appreciate any help with solving this, and if possible an explanation of/link to a good algorithm to go about solving problems of this style.
Here's the map:
graph-theory coloring
edited 8 hours ago
Morgan Rodgers
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
$endgroup$
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
1
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
1
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago
|
show 1 more comment
$begingroup$
I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps except this one, which after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality about it I've not fully understood (or I'm just bad at graph theory). I'd appreciate any help with solving this, and if possible an explanation of/link to a good algorithm to go about solving problems of this style.
Here's the map:
graph-theory coloring
edited 8 hours ago
Morgan Rodgers
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
$endgroup$
I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps except this one, which after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality about it I've not fully understood (or I'm just bad at graph theory). I'd appreciate any help with solving this, and if possible an explanation of/link to a good algorithm to go about solving problems of this style.
Here's the map:
graph-theory coloring
graph-theory coloring
edited 8 hours ago
Morgan Rodgers
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
edited 8 hours ago
Morgan Rodgers
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
edited 8 hours ago
Morgan Rodgers
10.3k31541
edited 8 hours ago
Morgan Rodgers
10.3k31541
edited 8 hours ago
Morgan Rodgers
10.3k31541
10.3k31541
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
asked 8 hours ago
Geza KerecsenyiGeza Kerecsenyi
1386
1386
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
1
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
1
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago
|
show 1 more comment
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
1
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
1
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
1
1
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
1
1
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
$endgroup$
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
add a comment |
$begingroup$
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
answered 8 hours ago
RadostRadost
1,05915
$endgroup$
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3247841%2fhow-can-this-map-be-coloured-using-four-colours%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
$endgroup$
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
add a comment |
$begingroup$
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
$endgroup$
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
add a comment |
$begingroup$
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
$endgroup$
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
answered 7 hours ago
Mark BennetMark Bennet
83.9k990186
83.9k990186
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
add a comment |
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
$begingroup$
Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm.
$endgroup$
– Geza Kerecsenyi
7 hours ago
add a comment |
$begingroup$
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
answered 8 hours ago
RadostRadost
1,05915
$endgroup$
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
add a comment |
$begingroup$
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
answered 8 hours ago
RadostRadost
1,05915
$endgroup$
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
add a comment |
$begingroup$
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
answered 8 hours ago
RadostRadost
1,05915
$endgroup$
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
answered 8 hours ago
RadostRadost
1,05915
answered 8 hours ago
RadostRadost
1,05915
answered 8 hours ago
RadostRadost
1,05915
answered 8 hours ago
RadostRadost
1,05915
1,05915
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
add a comment |
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
2
2
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
$begingroup$
I also got a (different) coloring by hand within a minute. Why the downvote?
$endgroup$
– Fabio Somenzi
8 hours ago
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3247841%2fhow-can-this-map-be-coloured-using-four-colours%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
It is similar to this post.
$endgroup$
– Dietrich Burde
8 hours ago
$begingroup$
@DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing))
$endgroup$
– Geza Kerecsenyi
8 hours ago
1
$begingroup$
It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring.
$endgroup$
– Morgan Rodgers
8 hours ago
1
$begingroup$
Re. how to colour: Algorithms that always find a 4-colouring for any planar graph are very complicated. If a simple algorithm existed, it's unlikely that the 4-colour theorem would have taken so long to prove. However, you may get good results on many not-too-complicated graphs by using greedy colouring with a decent ordering heuristic, like smallest degree last or Brélaz's adaptive ordering (see "Degenerate" and "Adaptive" under "Choice of ordering").
$endgroup$
– Rahul
7 hours ago
$begingroup$
@Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated.
$endgroup$
– Fabio Somenzi
7 hours ago