Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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.

share|improve this question

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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