7
$\begingroup$

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.

Improve this question
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ How did you track down the paper and verify it's originality (regarding interval graphs)? $\endgroup$ – bitmask Nov 21 '12 at 15:15
  • $\begingroup$ I found many interval graph papers citing this source. See for example the paper of Fulkerson and Gross $\endgroup$ – A.Schulz Nov 21 '12 at 15:17
  • $\begingroup$ 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? $\endgroup$ – bitmask Nov 21 '12 at 15:39
  • $\begingroup$ @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. $\endgroup$ – A.Schulz Nov 21 '12 at 17:38
  • $\begingroup$ Thanks for your help! I asked our librarian to try and dig up the full paper. I'll see what comes from this. $\endgroup$ – bitmask Nov 21 '12 at 19:04
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.