41–50 of 77 posts
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
2 -- 3 -- 2
| \ | / |
| \ | / |
3 -- 1 -- 3
| / | \ |
| / | \|
2 -- 3 -- 2I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
1.The poles was each their own country with a color on the map
2. Every country stretch all the way from south to north
Every country in 2. then only need two colors. Because the “same” color can never meet in any point.
The fourth color comes into play if you have a new country that bridge the south (or north) and both of the countries in step 2. at the same time.
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
Tangential: I don't know anything about graph theory but I'm intrigued by the student-instrument duet example. Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.
The adjacency matrix of a graph normally has entries only 0 or 1.
https://en.wikipedia.org/wiki/Adjacency_matrix
Generalize the adjacency matrices to include values between 0 and 1. Typically, you'd impose some normalization condition like rows and/or columns sum to 1.
Then compute the Kronecker product of matrices to obtain the graph tensor product.
I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1, B2, B3, B4 blue. It only becomes a problem when all nodes are interconnected (i.e. the graph is complete). So, the result does imply that graphs which are not colorable with 4 colors are not planar. In particular, the complete graph (where all nodes of the gra…
The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)
Earlier quoted context omitted.
The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1, B2, B3, B4 blue. It only becomes a problem when all nodes are interconnected (i.e. the graph is complete). So, the result does imply that graphs which are not colorable with 4 colors are not planar. In particular, the complete graph (where all nodes of the gra…
The complete graph with 4 nodes is planar, and obviously can be colored with only 4 colors -- that gives every node a unique color. The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)
Earlier quoted context omitted.
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".
To save laymen a google: A complete graph is one where all the nodes are connected. A planar graph is one that can be draw in the plane without two lines intersecting.