<p>(Copied from a comment:)</p>
<p>If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as <em>&quot;maximum k-cut&quot;</em> and also <em>&quot;maximum k-colorable subgraph&quot;</em>.</p>

CC BY-SA 4.0
2021-03-01T09:46:17.670Z
2021-03-01T09:46:17.670Z
Jukka Suomela
<p>I think under typical terminology this would be called &quot;Min k-Uncut&quot; (note, Min Uncut asks for a partition into two that minimizes the number of edges not cut, and Max k-Uncut asks for a k partition maximizing the number of uncut edges). Googling seems to find some references.</p>

CC BY-SA 4.0
2021-02-28T21:26:25.433Z
2021-02-28T21:26:25.433Z
Ryan Williams
<p>Given a graph <span class="math-container">$G=(V,E)$</span> and an integer <span class="math-container">$k$</span>, find a partition <span class="math-container">$P_1, P_2, \dots, P_k$</span> of <span class="math-container">$V$</span> into <span class="math-container">$k$</span> parts that minimize the total number of edges between two vertices in the same part, <em>i.e.</em> <span class="math-container">$\sum_i |(P_i\times P_i)\cap E|$</span>.</p>
<p>May someone please provide the name of this problem and/or references?</p>
<p>If <span class="math-container">$k$</span> is larger than or equal to the chromatic number of <span class="math-container">$G$</span>, then the number of edges under concern is <span class="math-container">$0$</span>. But if <span class="math-container">$k$</span> is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by <span class="math-container">$m=|E|$</span> (in the case <span class="math-container">$k=1$</span>).</p>

CC BY-SA 4.0
2021-03-01T08:53:40.717Z
Thank you @JukkaSuomela, this seems like the answer I was looking for; please post it as an answer so I may accept it.
Matthieu Latapy
CC BY-SA 4.0
2021-02-28T21:52:53.060Z
If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as *"maximum k-cut"* and also *"maximum k-colorable subgraph"*.
Jukka Suomela
<reference-request><graph-theory><graph-algorithms><graph-colouring><partition-problem>
Name of this graph partitioning problem? (related to coloring)
Matthieu Latapy
# Name of this graph partitioning problem? (related to coloring)

(Asked by: username_0 on 2021-02-28)

Given a graph $G=(V,E)$ and an integer $k$, find a partition $P\_1, P\_2, \dots, P\_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, *i.e.* $\sum\_i |(P\_i\times P\_i)\cap E|$.

May someone please provide the name of this problem and/or references?

If $k$ is larger than or equal to the chromatic number of $G$, then the number of edges under concern is $0$. But if $k$ is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by $m=|E|$ (in the case $k=1$).

**Tags:** reference-request, graph-theory, graph-algorithms, graph-colouring, partition-problem
> **Comments:**
> **username_1**: If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as *"maximum k-cut"* and also *"maximum k-colorable subgraph"*.  
> **username_0**: Thank you @JukkaSuomela, this seems like the answer I was looking for; please post it as an answer so I may accept it.  

---

## 2 answers

### Answer by username_1 on 2021-03-01. Score: 3 | Accepted answer

(Copied from a comment:)

If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as *"maximum k-cut"* and also *"maximum k-colorable subgraph"*.


---

### Answer by username_2 on 2021-02-28. Score: 1

I think under typical terminology this would be called "Min k-Uncut" (note, Min Uncut asks for a partition into two that minimizes the number of edges not cut, and Max k-Uncut asks for a k partition maximizing the number of uncut edges). Googling seems to find some references.


---

