Following a definition of Goodman , we define a notion of compatibility between an (unoriented) graph and a simple (linear) order. The notion of indifference graph, introduced in  for finite graphs, is extended to graphs of arbitrary cardinalities; and the graphs compatible with some simple order are characterized as precisely the indifference graphs. The uniqueness of the compatible simple order is investigated, and it is shown that there is "essentially" only one such for each indifference graph. A definition of compatibility between oriented graphs and simple orders is also introduced and the oriented graphs compatible with some simple order are characterized as the semiorders of Luce  and Scott and Suppes . It is proved that there is essentially only one simple order compatible with each semiorder. Finally, the compatibility results are applied to solve the psychologically-motivated problem of representing a graph (oriented graph) by "just noticeable difference" intervals on the real line. In the work on infinite graphs, the Axiom of Choice is freely (and tacitly) assumed.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics