### Minimum graph coloring/ Minimum chromatic number

Problem definition: https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/COMPEND/COMPED11/NODE13.HTM#SECTION00021500000000000000

Assignment based ILP-formulation (e.g. see here: https://arxiv.org/abs/1706.10191):
Let a graph $G=(V,E)$ with vertex set $V$ and edge set $E$ be given.
We model the decision via variables $x_{vi}\in\{0,1\}$, that take value $1$ if vertex $v\in V$ is assigned color $i$ and $0$ otherwise.

Further, let $H$ be an upper bound for the chromatic number, i.e. $H\le|V|$, but usually smaller as it could come from, e.g., the greedy coloring algorithm (https://en.wikipedia.org/wiki/Greedy_coloring). $w_{i}$ takes value $1$ if color $i=1,\ldots H$ is used in the assignment and $0$ otherwise.

\begin{align}
    &\min \sum_{1\le i \le H}w_{i} \text{ (minimize the total number of colors used) }\\
    &\text{s.t.} \\
    &\sum_{i=1}^{H} x_{vi} = 1\;\forall v\in V \text{ (make sure every vertex gets exactly one color) } \\
    &x_{ui}+x_{vi}\le w_{i}\;\forall(u,v)\in E, i=1,\ldots,H\text{ (make sure no two neighboring vertices get the same color) } \\
    &x_{vi},w_{i}\in\{0,1\}\;\forall v\in V, i=1,\ldots, H \text{ (assigning a color or not is a binary decision) }
\end{align}



```python
import gurobipy as gp
import networkx as nx
```


```python
from graphilp.partitioning.min_vertex_coloring import *
from graphilp.partitioning.heuristics import vertex_coloring_greedy
```


```python
from graphilp.imports import networkx as imp_nx
```

#### Create test graphs


```python
#create cycle graphs as test cases. we know odd cycles have chromatic number 3 and even cycles have chromatic number 2
G_odd_init = nx.cycle_graph(n=5)
G_even_init = nx.cycle_graph(n=4)
```


```python
#create ILPGraph objects
G_odd = imp_nx.read(G_odd_init)
G_even = imp_nx.read(G_even_init)
```


```python
#create test models
m_odd = create_model(G_odd)
m_even = create_model(G_even)
```


```python
#run optimization
m_odd.optimize()
```


```python
m_even.optimize()
```

#### Inspect solutions


```python
color_assignment_even, node_to_col_even = extract_solution(G_even, m_even)
```


```python
#visualize solution
nx.draw_circular(G_even.G, node_color=list(node_to_col_even.values()))
```


```python
color_assignment_odd, node_to_col_odd = extract_solution(G_odd, m_odd)
```


```python
nx.draw_circular(G_odd.G, node_color=list(node_to_col_odd.values()))
```


```python
col_to_node, node_to_col = vertex_coloring_greedy.get_heuristic(G_even)
```


```python
nx.draw_circular(G_even.G, node_color=list(node_to_col.values()))
```

8f23802d373c9c87d967e2be346add4d6a5f3db0
ipynb
Jupyter Notebook
graphilp/examples/MinVertexColouring.ipynb
VF-DE-CDS/GraphILP-API
841b80256f06b5dfc9f3bd4e514f1e24fb82b6ce
MIT
2021-05-03T10:58:55.000Z
2021-11-25T22:22:29.000Z
graphilp/examples/MinVertexColouring.ipynb
VF-DE-CDS/GraphILP-API
841b80256f06b5dfc9f3bd4e514f1e24fb82b6ce
MIT
graphilp/examples/MinVertexColouring.ipynb
VF-DE-CDS/GraphILP-API
841b80256f06b5dfc9f3bd4e514f1e24fb82b6ce
MIT
Qwen/Qwen-72B
1. YES
2. YES