Graph Coloring

Example Graph 1

We will denote vertices by 1,2,...,n. For each vertex, store the indexes of adjacent vertices. That is, g[[i]] is a list of vertices adjacent to vertex i.

neighbors={{2,4},{1,3,4},{2,4},{1,2,3}}

n=Length[neighbors]

We can build a list of all edges in the graph like this:

edgeList=Flatten[Table[a\[UndirectedEdge]b,{a,1,n},{b,neighbors[[a]]}]]

We can draw the graph like this. Note that each edge is drawn twice.

Graph[edgeList]

Here are two ways to draw the graph without duplicate edges:

Graph[{1,2,3,4},edgeList]//SimpleGraph

edgeList=DeleteDuplicates[Sort/@edgeList]

Graph[{1,2,3,4},edgeList]

Now let’s color the graph. First we will make a list of “color numbers” for each vertex.

vColorNums={1,2,3,2}

Now we can use the /. shorthand (the ReplaceAll function) to convert numbers to colors.

colorList=vColorNums/.{1->Red,2->Blue,3->Green}

We can make a list of the vertex numbers, each colored as specified above. This helps us draw the graph with colored vertices.

vColorList=Table[Style[i,colorList[[i]]],{i,n}]

This helps us draw the graph with colored vertices .

Graph[vColorList,edgeList,VertexLabels->Placed[Automatic,Center],VertexSize->0.2]

Example Graph 2

Here is a new list of vertex neighbors.

neighbors={{2,7,8},{1,3,8,9},{2,4,9},{3,5,9},{4,6,8,9},{5,7,8},{1,6,8},{1,2,5,6,7,9},{2,3,4,5,8}}

Let’s convert the list of neighbors into a list of edges.

n=Length[neighbors]
edgeList=Flatten[Table[a\[UndirectedEdge]b,{a,1,n},{b,neighbors[[a]]}]]
edgeList=DeleteDuplicates[Sort/@edgeList]

Now draw the graph:

Graph[edgeList,VertexLabels->Placed[Automatic,Center],VertexSize->0.3]

Now assign colors to each vertex:

vColorNums={1,2,3,4,2,1,2,3,1};
colorList=vColorNums/.{1->Red,2->Blue,3->Green,4->Orange}
vColorList=Table[Style[i,colorList[[i]]],{i,n}]

Draw the graph with vertex colors:

Graph[vColorList,edges,VertexLabels->Placed[Automatic,Center],VertexSize->0.3]

Erdős-Rényi Random Graphs

Given parameters n and p, an Erdős-Rényi random graph consists of n vertices. The edge between any two vertices is included in the graph with probability p.

Let’s write a module that constructs the incidence matrix for an Erdős-Rényi random graph with parameters n and p.

erdosRenyiGraph[n_,p_]:=Module[
{mx=Table[0,n,n]},
Do[
If[

],
{i,1,n},{j,i+1,n}
];
mx
]

Use the module to construct some incidence matrices:

incidenceMx=erdosRenyiGraph[8,0.6];
incidenceMx//MatrixForm

To make the neighbor lists for this graph, we can use the Position function to find the neighbors of any given vertex.

neighbors=Table[Flatten[Position[row,1]],{row,incidenceMx}]

We can then use Table to make a list of all edges in the graph:

n=Length[incidenceMx]
edgeList=Flatten[Table[a\[UndirectedEdge]b,{a,1,n},{b,neighbors[[a]]}]]

As before, we want to remove duplicate edges:

edgeList=DeleteDuplicates[Sort/@edgeList]

Now we can draw the graph:

Graph[Range[n],edgeList,VertexLabels->Placed[Automatic,Center],VertexSize->0.3]