First usage of "intersection graph" in a publication?

38 Views Asked by At

I am wondering about the first published use of the concept of an intersection graph.

At first I thought this 1966 paper by Erdos is the first publication defining and using intersection graphs explicitly, but then I dug a bit deeper.

A translation of Erdos' reference (2) is provided here, though it doesn't mention graphs.

Erdos' reference (3) is this 1954 paper by Turan, who on page 2 mentions a theorem of Marczewski relating to intersection graphs.

I tracked down that reference, which is this 1947 paper, but I got a bit stuck here since I don't read French.

Does anyone know definitively the first explicit appearance of intersection graphs in a published work?

1

There are 1 best solutions below

0
On BEST ANSWER

Turan refers to a theorem in the paper [1], not the one you mentioned. This theorem is interpreted as "all graphs are intersection graphs", though Szpilrajn-Marczewski does not use the word graphs, but speaks only of a relation. Here is the statement of the theorem:

Pour qu'une relation $\varrho$ soit symétric et non-réflexive, il faut et il suffit qu'il existe une classe $K$ d'ensembles non vides telle que la relation de disjonction ($E_1 \cdot E_2 = 0$), considérée dans $K$, soit semblable à $\varrho$

and its translation:

A relation $\varrho$ is symmetric and non-reflexive if and only if there exists a class $K$ of non-empty sets such that the disjonction relation ($E_1 \cdot E_2 = 0$), considered in $K$, is equivalent to $\varrho$.

This theorem is also mentionned on Wikipedia: intersection graph, so you can probably consider this as the first appearance of this concept, or Turan paper, since he explicitely talks about graphs.

[1] Szpilrajn-Marczewski, Edward, Sur deux propriétés des classes d’ensembles, Fundam. Math. 33, 303-307 (1945). ZBL0060.12508.Sur deux propriétés des classes d'ensembles"