Graphs and order : the role of graphs in the theory of ordered sets and its applications
Ivan Rival · D. Reidel Pub. Co. , Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers eBooks · 1985
I. Graph Representations.- Comparability graphs.- Algorithmic aspects of comparability graphs and interval graphs.- The diagram.- II. Scheduling, Searching and Sorting.- The information theoretic bound for problems on ordered sets and graphs.- Sorting and graphs.- A graph-theoretic approach to the jump-number problem.- Acyclic subdigraphs and linear orderings: polytopes, facets, and a cutting plane algorithm.- III. Extremal Orders.- Parameters of partial orders and graphs: packing, covering and representation.- Graphs and orders in Ramsey theory and in dimension theory.- Ordered ranked posets, representations of integers and inequalities from extremal poset problems.- IV. Social Sciences.- Issues in the theory of uniqueness in measurement.- V. Decomposition.- Path-partitions in directed graphs and posets.- VI. Recursion.- Recursion theoretic aspects of graphs and orders.- VII. Well-Quasi-Ordering.- Basic wqo- and bqo-theory.- Applications of well quasi-ordering and better quasi-ordering.- VIII. Problem Sessions.- Enumeration.- The diagram.- Ramsey theory.- Sorting, scheduling, computing, operations research, and social science.- Structure theories.- Infinite sets and infinite graphs.- Souvenir session.- Order-preserving and edge-preserving maps.- Miscellaneous.- IX. A Bibliography.- X. Index.