14
\$\begingroup\$

Honestly, I can't believe this hasn't already been asked, but here it is

Background

Given a simple undirected planar (the graph can be drawn in the plane without intersections) graph, it is a proven theorem that the graph is 4-colorable, a term we will explore in a bit. However, it's far easier to 5-color a graph, which is what we will focus our challenge on today.

A valid k-coloring of a graph is an assignment of "colors" to the nodes of the graph with the following properties

  1. If two nodes are connected by an edge, the nodes are colored with different colors.
  2. Across the graph, there are a maximum of 5 colors.

Given this, I will present to you a pretty basic algorithm to 5-color any simple undirected planar graph. This algorithm requires the following definitions

Reachability: If node 1 is reachable from node 2, that means that there is a sequence of nodes, each connected to the next by an edge, such that the first node is node 2 and the last is node 1. Note that since undirected graphs are symmetric, if node 1 is reachable from node 2, node 2 is reachable from node 1.

Subgraph: A subgraph of a graph of a given set of nodes N is a graph where the nodes of the subgraph are all in N, and an edge from the original graph is in the subgraph if and only if both nodes being connected by the edge are in N.

Let Color(N) be a function to color planar graphs with N nodes with 5 colors. We define the function below

  1. Find the node with the least number of nodes connected to it. This node will have at most 5 nodes connected to it.
  2. Remove this node from the graph.
  3. Call Color(N-1) on this new graph to color it.
  4. Add the deleted node back to the graph.
  5. If possible, color the added node a color that none of its connected nodes have.
  6. If not possible, then all 5 neighboring nodes to the added node have 5 different colors, so we must try the following process.
  7. Number the nodes surrounding the added node n1...n5
  8. Consider the subgraph of all nodes in the original graph colored the same color as either n1 or n3.
  9. If in this subgraph, n3 is not reachable from n1, in the set of nodes reachable from n1 (including n1), replace all occurrences of n1's color with n3's and vice versa. Now color the added node n1's original color.
  10. If n3 was reachable from n1 in this new graph, do the process from step 9 on nodes n2 and n4, rather than n1 and n3.

Challenge

Given an input of an edgelist (representing a graph), color the graph, by assigning each node a value.

Input: A list of edges in the graph (i.e., [('a','b'),('b','c')...])

Note that the input edgelist will be such that if (a,b) is in the list, (b,a) is NOT in the list.

Output: An object containing pairs of values, where the first element of each pair is a node, and the second its color, i.e.,[('a',1),('b',2)...] or {'a':1,'b':2,...}

You can use anything to represent colors, from numbers, to characters, to anything else.

The input and output is quite flexible, as long as its quite clear what the inputs and outputs are.

Rules

  • This is a challenge
  • You do not have to use the algorithm I've described above. It is simply there for reference.
  • For any graph, there are often many valid methods of coloring them. As long as the coloring your algorithm produced is valid, that is acceptable.
  • Remember that the graph must be 5-colored.

Test Cases

Use the following code to test your coloring results validity. As there are many valid graph colorings per graph, this algorithm simply checks the validity of the coloring. See the docstring to see how to use the code.

Some random (and rather silly) test cases:

Test Case 2: Krackhardt Kite Graph [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]

A valid output: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Note: These test cases are too small to test the more nuanced behavior of the coloring algorithm, so constructing your own graphs is probably a good test of the validity of your work.

Note 2: I'll be adding another piece of code that'll graph your coloring solution soon.

Note 3: I didn't forsee the random coloring algorithms that have been presented, which is what's so cool about PPCG! However, if anyone could golf a more deterministic algorithm, that'd be very cool too.

\$\endgroup\$
  • 3
    \$\begingroup\$ Aren't the Petersen and the Chvatal graph nonplanar? \$\endgroup\$ – Kroppeb Aug 15 '18 at 17:08
  • 1
    \$\begingroup\$ @NicHartley There are well known transpose based operations on adjacency matrices that effectively color graphs. I'll attach a paper when I find one. \$\endgroup\$ – Don Thousand Aug 15 '18 at 20:28
  • 1
    \$\begingroup\$ I think you would have been better off restricting solutions to polynomial time or requiring a large test case to run successfully in order to force solutions to use graph algorithms like what you seem to have in mind. \$\endgroup\$ – xnor Aug 15 '18 at 23:01
  • 2
    \$\begingroup\$ @xnor I seem to have learned my lesson. That's alright! Thinking out of the box should be rewarded, not penalized. \$\endgroup\$ – Don Thousand Aug 15 '18 at 23:29
  • 1
    \$\begingroup\$ Yes, I know, but a 4-colouring question would have to be designed in such a way that people can't just take their answers to this question, change 5 to 4, and resubmit them. \$\endgroup\$ – Peter Taylor Aug 16 '18 at 13:28
6
\$\begingroup\$

Python 2, 96 bytes

i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Try it online!

The input is \$g\$, a list of pairs of integers. We count up \$i\$ from zero, and map natural numbers to graph 4-labelings \$c\$, aborting (and writing \$c\$ to STDERR) as soon as \$c\$ is a valid coloring.

The input is planar, so finding a 4-coloring is always possible.

(Thus: this finds the lexicographically earliest coloring in a sense, and does so very inefficiently.)

The mapping: node \$ k \$ is given color \$ \Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4 \$, i.e. the \$k\$’th least significant digit of \$i\$ in base 4.

\$\endgroup\$
  • \$\begingroup\$ Nice effort, but I do believe you are missing one component. What about the case where a node is surrounded by 5 different colors? \$\endgroup\$ – Don Thousand Aug 15 '18 at 17:50
  • \$\begingroup\$ I'll try to build a test case to break this \$\endgroup\$ – Don Thousand Aug 15 '18 at 17:51
  • \$\begingroup\$ Suppose that a given node in your graph is surrounded by 5 other nodes, which you've already colored the 5 colors you are allowed. \$\endgroup\$ – Don Thousand Aug 15 '18 at 17:56
  • 1
    \$\begingroup\$ My code randomly generates graph colorings and checks them until it generates a correct graph coloring, which it then prints upon exiting. In the case you describe it'd start over and hopefully not color those 5 nodes all 5 available colors. \$\endgroup\$ – Lynn Aug 15 '18 at 17:59
  • 2
    \$\begingroup\$ Now it checks all the colorings in lexicographic order :) so it's deterministic and O(5^n), but a lot slower for most inputs. \$\endgroup\$ – Lynn Aug 15 '18 at 18:09
3
\$\begingroup\$

JavaScript (ES7), 80 76 74 bytes

Saved 2 bytes thanks to @Neil

Same approach as Lynn. Solves in 4 colors, numbered from 0 to 3.

a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ If you're allowed a 4-colouring, then why not x>>n+n&3? \$\endgroup\$ – Neil Aug 15 '18 at 19:39
  • \$\begingroup\$ @Neil Ah yes, thanks. I got distracted by the explanation about 5-colouring and forgot the input was guaranteed to be solvable in 4. \$\endgroup\$ – Arnauld Aug 15 '18 at 20:39
3
\$\begingroup\$

Brachylog, 38 bytes

cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Try it online!

Explanation

Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints
\$\endgroup\$
1
\$\begingroup\$

Python 2, 211 bytes

def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Try it online!

Deterministic! Would probably fail on more complicated test cases, but I'm too burnt out to find a graph that it fails for. More test cases and.or criticism welcome!

\$\endgroup\$
1
\$\begingroup\$

Clean, 139 bytes

import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Try it online!

Generates all colorings and returns the first valid one.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 23 bytes

®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Try it online!

Brute force. Assumes the nodes are labeled by integers.

\$\endgroup\$

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.