<p>Upon the suggestion of Louis Esperet, I contacted Philippe Gambette  and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib and Christophe Paul (DOI:10.1016/j.cosrev.2010.01.001).</p>

<p>Some nice properties of this graph include:</p>

<ul>
<li>it is a permutation graph</li>
<li>its prime node (the bull) is a prime graph containing a vertex that avoids every induced P4. When such a node exists, it is unique.</li>
</ul>

CC BY-SA 4.0
2019-10-03T11:27:19.313Z
2019-10-03T11:27:19.313Z
Yixin Cao
<p>When introducing graph <a href="https://en.wikipedia.org/wiki/Modular_decomposition" rel="noreferrer">modular decomposition</a>, most authors use the 11-vertex graph, which I copy from wikipedia.</p>

<p>The question is who is (are) the original designer of it. (I'm not asking who drew this graph for wikipedia, but the original source of it.)</p>

<p><a href="https://i.sstatic.net/4rjJg.png" rel="noreferrer"><img src="https://i.sstatic.net/4rjJg.png" alt="enter image description here"></a></p>

<p>The wikipedia page was created in December 2006. The earliest source I can find is the <a href="https://tel.archives-ouvertes.fr/tel-00112390" rel="noreferrer">Habilitation thesis of Christophe Paul</a> dated on May 17, 2006. (I didn't search intensively.)</p>

CC BY-SA 4.0
2019-10-02T09:34:04.743Z
Philippe Gambette (who created the wikipedia page) was a PhD student of Christophe Paul. The best is that you contact either one of them, http://igm.univ-mlv.fr/~gambette/ or http://www.lirmm.fr/~paul/
Louis Esperet
<reference-request><graph-theory>
The source of the modular decomposition graph
Yixin Cao
# The source of the modular decomposition graph

(Asked by: username_0 on 2019-10-02)

When introducing graph [modular decomposition](https://en.wikipedia.org/wiki/Modular_decomposition), most authors use the 11-vertex graph, which I copy from wikipedia.

The question is who is (are) the original designer of it. (I'm not asking who drew this graph for wikipedia, but the original source of it.)

[![enter image description here](https://i.sstatic.net/4rjJg.png)](https://i.sstatic.net/4rjJg.png)

The wikipedia page was created in December 2006. The earliest source I can find is the [Habilitation thesis of Christophe Paul](https://tel.archives-ouvertes.fr/tel-00112390) dated on May 17, 2006. (I didn't search intensively.)

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: Philippe Gambette (who created the wikipedia page) was a PhD student of Christophe Paul. The best is that you contact either one of them, http://igm.univ-mlv.fr/~gambette/ or http://www.lirmm.fr/~paul/  

---

## 1 answers

### Answer by username_0 on 2019-10-03. Score: 7 | Accepted answer

Upon the suggestion of Louis Esperet, I contacted Philippe Gambette and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib and Christophe Paul (DOI:10.1016/j.cosrev.2010.01.001).

Some nice properties of this graph include:

* it is a permutation graph
* its prime node (the bull) is a prime graph containing a vertex that avoids every induced P4. When such a node exists, it is unique.


---

