# Who (and when) first defined interval graphs?

I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949.

So, I'm trying to track down the original paper introducing interval graphs for citation, but it's been rather elusive so far.

-

I was able to track the first occurences of interval graphs down to

G. Hajos, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957) page 65

This reference refers to a book of (talk) abstracts. In the abstract of Hajos interval graphs are defined, without actually calling them interval graphs. Moreover it says, that he gives conditions whether a graph is a interval graph and he discusses how to reconstruct the intervals defining the graph, when the graph fulfills these conditions.

-
How did you track down the paper and verify it's originality (regarding interval graphs)? – bitmask Nov 21 '12 at 15:15
I found many interval graph papers citing this source. See for example the paper of Fulkerson and Gross – A.Schulz Nov 21 '12 at 15:17
I actually managed to find it (page 34 ---65---), and it does describe what we call interval graphs, but it's a mere abstract. I don't know if you can read German, but it basically states the problem of determining if a given graph is an interval graph. It appears to be genuine, but I'd have loved an actual paper instead of an abstract advertising a talk. Do you think such a paper even exists? – bitmask Nov 21 '12 at 15:39
@bitmask: Thanks for the link, I included it in the post. Also, since German is my mother tongue, I have read the abstract and included a short summary. – A.Schulz Nov 21 '12 at 17:38
Thanks for your help! I asked our librarian to try and dig up the full paper. I'll see what comes from this. – bitmask Nov 21 '12 at 19:04

According to Golumbic [1], Hajös proposed the following problem in 1957 (translation by Golumbic):

Given a finite number of intervals on a straight line, a graph associated with this set of intervals can be constructed in the following manner: each interval corresponds to a vertex of the graph, and two vertices are connected by an edge if and only if the corresponding intervals overlap at least partially. The question is whether a given graph is isomorphic to one of the graphs just characterized (Hajös [1957, p. 65, translated by M.C.G.]).

Golumbic also discusses how interval graphs were related to a question in biology made by Benzer [2] in 1959.

[1] Golumbic, Martin Charles. Algorithmic graph theory and perfect graphs. Vol. 57. Elsevier, 2004.

[2] Benzer, Seymour. "On the topology of the genetic fine structure." Proceedings of the National Academy of Sciences of the United States of America 45.11 (1959): 1607.

-