Abstract
This paper surveys results concerning packing/covering parameters and representation parameters of graphs and posets. We start from the poset param¬eters known as width and dimension. We consider generalizations, related ques¬tions, and analogous parameters for graphs and/or directed graphs.
Dilworth’s Theorem states that a poset with finite width (maximum antichain size) w can be covered with w chains; we review the known proofs. Greene and Kleitman generalized this to unions of k antichains, called k-famities, proving that the maximum size of a k-family equals the minimum in a dual chain-covering problem. Chain coverings yielding the optimal bound on k-family size are k-saturated partitions. We review proofs and discuss other aspects of the theory of saturated partitions. For example, chain coverings become cliques in the graph context or path coverings in the context of directed graphs, and duality questions still apply. Other topics include duality questions for product orders or product graphs, and the study of element sets that meet all maximal chains in a poset or maximal cliques in a graph.
Packing and covering focus on vertex subsets; “representation” expresses the entire relation as the union or intersection of a minimum number of “nice” relations. We review results on order dimension (the minimum number of chains whose intersection is the poset) and study various dimension parameters for graphs and digraphs. The Ferrers dimension of a digraph D is the minimum number of “Ferrers digraphs” whose intersection is D. Bouchet and Cogis proved that the Ferrers dimension of a reflexive, transitive, antisymmetric relation equals its order dimension as a poset. For undirected graphs, we discuss threshold dimension, product dimension, and boxicity. In each case we seek results analogous to those for order dimension of posets. The last of these leads to a general discussion of intersection representations of graphs, multiple inter¬section parameters, and edge-covering problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Aigner, Lexicographic matching in Boolean algebras. J. Comb. Theory B14 (1973), 187–194.
M. Aigner, Symmetrische Zerlegung von Kettenprodukten. Monats. Math79 (1975), 177–189.
M. Aigner, Combinatorial Theory. Springer-Verlag, New York (1979).
M. Aigner and G. Prins, Uniquely partially orderable graphs. J. London Math. Soc. (2) 3(1971), 260–266.
M.O. Albertson, A lower bound for the independence number of a planar graph. J. Comb. Th (B) 20(1976, 84–93.
M.O. Albertson, A new paradigm for duality questions, preprint.
M.O. Albertson and D.M. Berman, The chromatic difference sequence of a graph. J. Comb. Theory B 29 (1980), 1–12.
M.O. Albertson and D.M. Berman, Critical graphs for chromatic difference sequences. Disc. Math 31 (1980), 225–233.
M.O. Albertson, P.A. Catlin, and L. Gibbons, Homomorphisms of 3-chromatic graphs, II. preprint.
M.O. Albertson and K.L. Collins, Duality and perfection for r-clique graphs. J. Comb. Th (B), to appear.
M.O. Albertson and K.L. Collins, Homomorphisms of 3-chromatic graphs, Disc. Math, submitted.
M.O. Albertson and J.P. Hutchinson, The independence ratio and genus of a graph. Trans. Amer. Math. Soc 226 (1977), 161–173.
P. Alles, Estimation of the dimension of some types of graph by means of orthogonal Latin squares. Fachbereich Math Preprint 749, Technische Hochscule Darmstadt (1983).
P. Alles, The dimension of sums of graphs. Fachbereich Math Preprint 814, Technische Hochscule Darmstadt (1984).
P. Alles, On the dimension of sums, amalgams, and weak products of graphs, (preprint).
R. Alter and C.C. Wang, Uniquely intersectable graphs. Disc. Math 18 (1977), 217–226.
L.D. Andersen, D.D. Grant, and N. Linial, Extremalk-colourable subgraphs. Ars Combinatoria 16 (1983), 259–270.
J. Araoz, W.H. Cunningham, J. Edmonds, and J. Green-Krótki, Reductions to 1- matching polyhedra. Networks 13 (1983), 455–473.
J.C. Arditti and H.A. Jung, The dimension of finite and infinite comparability graphs. J. London Math. Soc. (2) 21(1980), 81–38
J. Ayel, Longest paths in bipartite digraphs. Disc. Math 40 (1982), 115–118.
K.A. Baker, Dimension, join-independence, and breadth in partially ordered sets, (1961), unpublished.
K.A. Baker, P.C. Fishburn, and F.S. Roberts, Partial orders of dimension two. Networks 2(1971), 11–28.
E. Balas and M.W. Padberg, Set partitioning: a survey. SIAM Review 18 (1976), 710–766.
L.W. Beineke, Characterizations of derived graphs. J. Comb. Th 9 (1970), 129–135.
L.W. Beineke and C.M. Zamfirescu, Connection digraphs and second-order line graphs. Disc. Math 39 (1982), 237–254.
M. Bell, The space of complete subgraphs of a graph. Comm. Math. Univ. Card 23 (1982), 525–536.
M. Bell and J. Ginsburg, Compact spaces and spaces of maximal complete subgraphs. Trans. Amer. Math. Soc, to appear.
C. Benzaken, P.L. Hammer, and D. de Werra, Threshold signed graphs. R.R. 237, IMAC, Univ. Grenoble (1981).
S. Benzer, On the topology of the genetic fine structure. Proc. Nat. Acad. Sci. USA 45 (1959), 1607–1620.
C. Berge, Farbung von Graphen, deren samtliche bzw. ungerade Kreise starr sind. Mas. Z. Martin-Luther-Univ., Halle-Wittenberg Math.-Natur, Reihe (1961), 114–115.
C. Berge, Some classes of perfect graphs, in Graph Theory and Theoretical Physics (F. Harary, ed.). Academic Press, New York (1967), 155–165.
C. Berge, Graphs and Hypergraphs. North-Holland, New York (1973).
C. Berge, Fractional Graph Theory, ISI Lecture Notes 1, Macmillan (1978).
C. Berge, Packing problems and hypergraph theory: a survey. Annals of Disc. Math 4 (1979), 3–37.
C. Berge, Diperfect graphs. Combinatorics and Graph Theory (Calcutta, 1980). Lect. Notes Math. 885, Springer-Verlag (1981), 1–8.
C. Berge, k-optimal partitions of a directed graph. Europ. J. Comb3 (1982), 97–101.
C. Berge, Path partitions in directed graphs. Annals of Disc. Math. 17(1983), 59–63.
C. Berge, Chain decompositions ofOrdered Sets and optimal partitions of directed graphs, this volume.
C. Berge and P. Duchet, Strongly perfect graphs, in Topics in Perfect Graphs (C. Berge and V. Chvatal, eds.) to appear.
J.C. Bermond et al. Cahiers Centre Etudes Rech. Oper 20(1978), 325–329.
F. Bemhart and P.C. Kainen, The book thickness of a graph. J. Comb. Th. (B). 27 (1979), 320–331.
R.E. Bixby, A composition for perfect graphs, inTopics in Perfect Graphs (C. Berge and V. Chvatal, eds.), to appear.
K.P. Bogart, Maximal dimensional partially ordered sets I. Hiraguchi’s Theorem. Disc. Math 5 (1973), 21–32.
K.P. Bogart, I. Rabinovitch, and W.T. Trotter, A bound on the dimension of interval orders, J. Comb. Th. (A) 21 (1976), 319–328.
K.P. Bogart and W.T. Trotter, Maximal dimensional partiallyOrdered SetsII: Characterization of2n-element posets with dimensionn. Disc. Math. 5 (1973), 33–45.
B. Bollobás, Extremal Graph Theory. Academic Press, New York (1980).
J.A. Bondy and C. Thomassen, A short proof of Meyniel’s theorem. Disc. Math 19 (1977), 195–197.
J.A. Bondy and S.C. Locke, Maximum bipartite subgraphs in triangle-free cubic graphs, to appear.
K.S. Booth and G.S. Leuker, Linear algorithms to recognize interval graphs and test for the consecutive ones property. Proc. 7th ACM Symp. Th. Comp. (1975), 255–265.
K.S. Booth and G.S. Leuker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Assoc. Comp. Syst. Sci 13 (1976), 335–379.
A. Boucher, It’s hard to color antirectangles. SIAM J. Alg. Disc. Meth. (1984).
A. Bouchet, Etude des ordonn’es finis — applications. These d’Etat, Grenoble (1971). See also, Codages et dimensions de relations binaires, in Ordres: Description et Roles (Proc. Lyon 1982, (M. Pouzet, ed.) Annals of Discrete Math. (1984), 387–396.
A. Bouchet, Etude des ordonn’es finis — applications. These d’Etat, Grenoble (1971). See also, Codages et dimensions de relations binaires, in Ordres: Description et Roles (Proc. Lyon 1982, (M. Pouzet, ed.) Annals of Discrete Math. (1984), 387–396.
A. Bouchet, Etude des ordonn’es finis — applications. These d’Etat, Grenoble (1971). See also, Codages et dimensions de relations binaires, in Ordres: Description et Roles (Proc. Lyon 1982, (M. Pouzet, ed.) Annals of Discrete Math. (1984), 387–396.
V. Bouchitte, M. Habib, and R. Jegou, On the greedy dimension of a partial order. Order (to appear).
G.H. Bradley, Transformation of integer programs to knapsack problems. Disc. Math 1 (1971), 29–45.
R.C. Brigham and R.D. Dutton, Graphs which, with their complements, have certain clique covering numbers. Disc. Math 34 (1981), 1–7.
R.C. Brigham and R.D. Dutton, On clique covers and independence numbers of graphs. Disc. Math 44 (1983), 139–144.
R.C. Brigham and R.D. Dutton, Upper bounds on the edge clique cover number of a graph, mimeograph, Univ. Central Florida (1983).
V.W. Bryant and K.G. Harris, Transitive Graphs. J. Lond. Math. Soc 11 (1975), 123–128.
M.A. Buckingham and M.C. Golumbic, Partitionable graphs, circle graphs, and the strong perfect graph conjecture. Disc. Math 44 (1983), 45–54.
P. Buneman, A characterization of rigid circuit graphs, Disc. Math. 9(1974), 205–212.
M. Burlet, Etude Algorithmique de Certaines Classes de Graphs Parfait. 3rd cycle doctorate thesis, Sci. Med. Univ. Grenoble.
M. Burlet and J.P. Uhry, Parity graphs, inBonn Workshop on Combinatorial Optimization, 1980 (B. Korte et al, eds.) Annals of Disc. Math. 16(1982), 1–26.
J.F. Buss and P.W. Shor, On the pagenumber of planar graphs, (preprint).
L. Cacetta and N.J. Pullman, Clique covering numbers of cubic graphs. Proc. Xth Austral. Conf. Comb. Math., Adelaide 1982. Springer-Verlag Lect. Notes Math. 1036(1983), 121–127.
L. Cacetta and N.J. Pullman, Clique covering numbers of regular graphs. Ars Combinatoria 15 (1983), 201–230.
K.B. Cameron and J. Edmonds, Algorithms for optimum antichains. Proc. 10th SE Conf. Comb., Graph Th., and Comp. (F. Hoffman et al, eds.), Utilitas Math., Winnipeg (1979), 229–240.
K.B. Cameron, Polyhedral and algorithmic ramifications of antichains, Ph.D. thesis, Univ. of Waterloo, Waterloo, Ont (1982).
E.R. Canfield, A Sperner property preserved by products. Lin. Multilin. Alg 9 (1980), 151–157.
P.A. Catlin, Graph homomorphism into the 5-cycle. J. Comb. Th. (B) submitted
P.A. Catlin, Homomorphism as a generalization of graph coloring, preprint.
S. Chaiken, D.J. Kleitman, M. Saks, and J. Shearer, Covering regions with rectangles. SIAM J. Alg. Disc. Meth. 2(1981),
S.A. Choudom, K.R. Parthasarathy, and G. Ravindra, Line-clique cover number of a graph. Proc. Indian Nat. Sci. Acad 41 (1975), 289–293.
C. Christen and S.M. Selkow, Some perfect coloring properties of graphs. J. Comb. Th. (B) 27 (1979), 49–59.
F.R.K. Chung, Problems and results on several graph labeling problems. Proc. 5th Intl. Conf. Graph Th., Kalamazoo 1984. (to appear).
V. Chvatal, Perfectly ordered graphs, McGill Univ. Rept. SOCS 81.28 (1981).
V. Chvatal and P.L. Hammer, Aggregation of inequalities in integer programming. Annals Disc. Math. 1(1977), 145–162. Contains the material of “Set packing and threshold graphs,” Univ. of Waterloo Rept. CORR 73-21 (1973).
V. Chvatal and C.T. Hoang, The P4 structure of perfect graphs, to appear.
O. Cogis, Determination d’un preordre total contenant un preordre et contenu dans une relation de Ferrers lorsque leur domaine commun est fini. C. R. Acad. Sci. Paris 283 (A) (1976), 1007–1009.
O. Cogis, Sur la dimension d’un graph oriente. C. R. Acad. Sci. Paris 288 (A) (1979), 639–641.
O. Cogis, Ferrers digraphs and threshold graphs. Disc. Math. 38(1982), 33–46. Includes most of “La dimension Ferrers des graphes orientes,” These de Doctorat d’Etat, Universite Pierre et Marie Curie, Paris (1980).
O. Cogis, Ferrers digraphs and threshold graphs. Disc. Math. 38(1982), 33–46. Includes most of “La dimension Ferrers des graphes orientes,” These de Doctorat d’Etat, Universite Pierre et Marie Curie, Paris (1980).
O. Cogis, On the Ferrers dimension of a digraph. Disc. Math 38 (1982), 47–52.
O. Cogis, A characterization of digraphs with Ferrers dimension 2. to appear.
J.E. Cohen, Interval graphs and food webs: a finding and a problem. RAND Corporation Document 17696-PR (1968).
J.E. Cohen, Food webs and the dimensionality of trophic niche space. Proc. Natl. Acad. Sci 74 (1977), 4533–4536.
J.E. Cohen, Food Webs and Niche Space. Princeton Univ Press, Princeton (1978).
J.E. Cohen, Recent progress and problems in food web theory. In Current Trends in Food Web Theory (D.L. DeAngelis et al, eds.) Oak Ridge Natl. Lab. Tech Rept. ORNL/TM-8643 (1983).
C.J. Colbourn, On testing isomorphism of permutation graphs. Networks 11 (1981), 13–21.
M.B. Cozzens, Higher and multi-dimensional analogues of interval graphs, Ph.D. Thesis, Rutgers (1981).
M.B. Cozzens, The NP-completeness of the boxicity of a graph, mimeograph, Northeastern Univ. (1982).
M.B. Cozzens and R. Leibowitz, Threshold dimension of graphs. SIAM J. Alg. Disc. Meth (to appear).
M.B. Cozzens and R. Leibowitz, Threshold dimension and psychological scaling, (preprint).
M.B. Cozzens and F.S. Roberts, Double semiorders and double indifference graphs. SIAM J. Alg. Disc. Meth 3 (1982), 566–583.
M.B. Cozzens and F.S. Roberts, Computing the boxicity of a graph by covering its complement by cointerval graphs. Disc. Appl. Math6 (1983), 217–228.
M.B. Cozzens and F.S. Roberts, Onk-suitable sets of arrangements and the boxicity of a graph. J. Comb. Inf. Syst. Sci (to appear).
M.B. Cozzens and F.S. Roberts, Multi-dimensional intersection graphs: cubicity, circular dimension, overlap dimension, (preprint).
M.B. Cozzens and D.-I. Wang, Closed neighborhood containment graphs. Proc. 15th SE Conf. Comb. Graph Th. Comp (to appear).
G.B. Dantzig and A. Hoffman, On a theorem of Dilworth. Linear Inequalities and related systems (H.W. Kuhn and A.W. Tucker, eds.) Annals of Math. Studies 38(1966), 207–214.
D.E. Daykin, Finite sets, order representations of integers, and inequalities. In this volume.
N. deBruijn, C. Tengbergen, D. Kruyswijk, On the set of divisors of a number. Nieuw Arch. Wiskunde 23 (1951), 191–193.
D. de Caen, D.A. Gregory, and N.J. Pullman, Clique coverings of paths and cycles. Annals Disc. Math. (1984).
W.A. Denig, A class of matroids derived from saturated chain partitions of par¬tially ordered sets. J. Comb. Th. (B) 30 (1981), 302–317.
R.P. Dilworth, A decomposition theorem for partially ordered sets. Annals of Math. 51 (1950). 161–165.
R.P. Dilworth, Some combinatorial problems on partially ordered sets, in Combinatorial Analysis (Proc. Symp. Appl. Math.), (Amer. Math. Soc., 1960), 85–90.
J.P. Doignon, A. Ducamp, and J.-C. Falmagne, On realizable biorders and the biorder dimension of a relation, to appear.
J.P. Doignon and J.-C. Falmagne, Matching relations and the dimensional structure of social choices, to appear.
A. Ducamp, Sur la dimension d’un ordre partiel. inTheory of Graphs, (Gordon and Breach, 1967 ).
A. Ducamp, A note on an alternative proof of the representation theorem for biorders. J. Math. Psych 18 (1978), 100–104.
A. Ducamp and J.-C. Falmagne, Composite measurement. J. Math. Psych. 6(1969), 359–390.
D. Duffus, I. Rival, and P. Winkler, Minimizing setups for cycle-free ordered sets. Proc. Amer. Math. Soc 85 (1982), 509–513.
B. Dushnik, Concerning a certain set of arrangements. Proc. Amer. Math. Soc 1 (1950), 788–796.
B. Dushnik and E.W. Miller, PartiallyOrdered Sets. Amer. J. Math 63 (1941), 600–610.
R.D. Dutton and R.C. Brigham, A characterization of competition graphs. Disc. Appl. Math 6 (1983), 315–317.
J. Edmonds, Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Stand 69B (1965), 67–72.
J. Edmonds and R. Giles, Box TDI polyhedra. (unpublished).
J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs, inStudies in Integer Programming(P.L. Hammer, E.L Johnson, and B.H. Korte, eds.), Annals Disc. Math. 1(1977), 185–204.
J. Edmonds and E.L. Johnson, Matching: A well-solved class of integer linear programs. inCombinatorial Structures and their Applications, (R.K. Guy et al, eds.). Gordon and Breach, New York (1970), 89–92.
J. Edmonds and D.R. Fulkerson, Bottleneck extrema. J. Comb. Th. 8(1970), 299–306.
C.S. Edwards, Some extremal properties of bipartite subgraphs. Canad. J. Math 25 (1973), 475–485.
C.S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in Recent Advances in Graph Theory (M. Feidler, ed.), Academia Praha, Prague (1975), 167–181.
K. Engel, Strong properties in partially ordered sets, I. Disc. Math 47 (1983), 229–234.
K. Engel, Strong properties in partiallyOrdered Sets, II. Disc. Math 48 (1984), 187–196.
P. Erdos, On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc 51 (1945), 898–902.
P. Erdos, Graph theory and probability, II. Canad. J. Math 13 (1961), 346–352.
P. Erdos, A. Goodman, and L. Posa, The representation of a graph by set intersections. Canad. J. Math 18 (1966), 106–112.
P. Erdos and D.J. Kleitman, Extremal problems among subsets of a set. Discrete Math. 8 (1974), 281–294.
P. Erdos, F. Harary, and W.T. Tutte, On the dimension of a graph. Mathematika 12 (1965), 118–122.
P. Erdos and L. Moser, On the representation of directed graphs as unions of orderings. Math. Inst. Hung. Acad. Sci 9 (1964), 125–132.
P. Erdos, E.T. Ordmann, and Y. Zalcstein, (unpublished).
P. Erdos and D.B. West, A note on interval number of graphs, (preprint).
S. Even, A. Pnueli, and A. Lempel, Permutation graphs and transitive graphs. J. Assoc. Comp. Mach 19(1972), 400–
S. Fajtlowicz, The independence ratio for cubic graphs. Proc. 8th SE Conf. Comb., Graph Th., and Comp. (1977), 273–277.
R.B. Feinberg, The circular dimension of a graph. Disc. Math 25 (1979), 27–31.
P.C. Fishburn, Intransitive indifference with unequal indifference intervals. J. Math. Psych7 (1970), 144–149.
P.C. Fishburn, Intransitive indifference in preference theory: a survey. Operations Research 18 (1970), 201–228.
P.C. Fishburn, Interval representations for interval orders and semiorders. J. Math. Psych 10 (1973), 91–105.
P.C. Fishburn, Maximum semiorders in interval orders. SIAM J. Alg. Disc. Meth. (1982)
P.C. Fishburn, Aspects of semiorders within interval orders. Disc. Math 40 (1982), 181–191.
P.C. Fishburn, Interval lengths for interval orders: A minimization problem. Disc. Math 47 (1983), 63–82.
P.C. Fishburn, On the sphericity and cubicity of graphs. J. Comb. Th. (B) 35 (1983), 309–318.
P.C. Fishburn, Interval graphs and interval orders. Disc. Math, (to appear).
P.C. Fishburn, Interval Orders and Interval Graphs. Wiley (1984/5).
P.C. Fishburn and R.L. Graham, Classes of interval graphs under expanding length restrictions, (to appear).
P.C. Fishburn and J. Spencer, Directed graphs as unions of partial orders. Pac. J. Math 39 (1971), 149–161.
S. Foldes and P.L. Hammer, Split graphs with Dilworth number 2. Canad. J. Math 29 (1977), 666–672.
S. Foldes and P.L. Hammer, Split graphs. Proc. 8th S.E. Conf. Comb., Graph Th., Comp. (F. Hoffman, et al, eds.) Congressus Numerantium 19(Utilitas Math., 1977), 311–315.
S. Foldes and P.L. Hammer, The Dilworth number of a graph. Ann. Disc. Math 2 (1978), 211–219.
S. Foldes and P.L. Hammer, On a class of matroid-producing graphs, inCombinatorics Colloq. Math. Soc. Janos Bolyai 18 (1978), 331–352.
L.R. Ford and D.R. Fulkerson, Maximal flow through a network. Canad. J. Math 8 (1956), 399–404.
L.R. Ford and D.R. Fulkerson, Flows in Networks, (Princeton Univ. Press, 1962 ).
S.V. Fomin, Finite partially ordered sets and Young tableaux. Soviet Math. Dokl 19 (1978), 1510–1514.
A. Frank, On chain and antichain families of a partially ordered set. J. Comb. Theory B 29 (1980), 176–184.
A. Frank, How to make a digraph strongly connected. Combinatorica 1 (1981), 145–153.
D.R. Fulkerson, Note on Dilworth’s embedding theorem for partially ordered sets. Proc. Amer. Math. Soc 7 (1956), 701–702.
D.R. Fulkerson, Networks, frames, blocking systems. InMathematics of the Decision Sciences (G.B. Dantzig and A.F. Vienott, eds.). Amer. Math. Soc. Lect. Appl. Math. 11(1968), 303–334.
D.R. Fulkerson, Blocking polyhedra. Graph Theory and Its Applications (B. Harris, ed.). Academic Press (1970), 93–112.
D.R. Fulkerson, Blocking and antiblocking pairs of polyhedra. Math. Programming 1 (1971), 168–194.
D.R. Fulkerson, Antiblocking polyhedra. J. Comb. Th. (B) 12(1972), 50–71.
D.R. Fulkerson, On the perfect graph theorem, inMath. Programming (T.C. Hu and S. Robinson, eds.) Academic Press, New York (1972), 68–76.
D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs. Pac. J. Math 15 (1965), 835–855.
H. Gabai, Bounds for the boxicity of a graph, mimeo, York College, CUNY (1974).
E. Gafni, M.C. Loui, P. Tiwari, D.B. West, and S. Zaks, Lower bounds on common knowledge in distributed algorithms, with applications, preprint.
T. Gallai, Graphen mit triangulierbaren ungeraden Viekecken, Magyar Tud. Akad. Kutato Int 7A (1962), 3–36.
T. Gallai, Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hung 18 (1967), 25–66.
T. Gallai, On directed paths and circuits, in Theory of Graphs, Tihany (P. Erdos and G.O.H. Katona, eds.) Academic Press, New York (1968), 115–118.
T. Gallai and A.N. Milgram, Verallgemeinerung eines Graphentheoretischen Satzes vi Reedei. Acta Sci. Math. Hung 21 (1960), 181–186.
E.R. Gansner, Acyclic digraphs, Young Tableaux and nilpotent matrices. SIAM J. Alg. Disc. Meth 2 (1981), 429–440.
M.L. Gardner, Forbidden configurations of large girth for intersection graphs of hypergraphs. Ars Combinatoria 14 (1982), 271–278.
M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, (Freeman, 1979).
M.R. Garey, D.S. Johnson, G.L. Miller, and C.H. Papadimitriou, The complexity of coloring circular arcs and chords.
F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comp 1 (1972), 180–187.
F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3 (1973), 261–273.
F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Th (B) 16 (1974), 47–56.
F. Gavril, Algorithms on circular-arc graphs. Networks 4 (1974), 357–369.
F. Gavril, Some NP-complete problems on graphs. Proc. 11th Conf. Info. Sci. Syst. Johns Hopkins Univ., Baltimore (1977), 91–95.
F. Gavril, A recognition algorithm for the intersection graphs of paths in trees. Disc. Math 23 (1978), 211–227.
A. Ghouila-Houri, Caracterisation des graphes nonorientes dont on peut orienter les aretes de mainiere a obtenir le graph d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962), 1370–1371.
R. Giles and R. Kannan, A characterization of threshold matroids. Disc. Math 30 (1980), 181–184.
P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs. Canad. J. Math 16 (1964), 539–548.
J. Ginsburg, Compactness and subsets ofOrdered Sets that meet every maximal chain, to appear.
J. Ginsburg, I. Rival, and B. Sands, Antichains and finite sets that meet all maximal chains, to appear.
M.C. Golumbic, Comparability graphs and a new matroid. J. Comb. Th. (B) 22 (1977), 68–90.
M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing 18 (1977), 199–203.
M.C. Golumbic, Threshold graphs and synchronizing parallel processes. Combinatorics, (A. Hajnal and V.T. Sos, eds.). Colloq. Math. Soc. Janos Bolyai 18(1978), 419–428.
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press (1980).
M.C. Golumbic and R.E. Jamison, The overlap graphs of paths in a tree. J. Comb. Th (B)(to appear).
M.C. Golumbic and R.E. Jamison, Algorithmic aspects of overlapping paths in a tree. Disc. Math (to appear).
M.C. Golumbic and C.L. Monma, A generalization of interval graphs with tolerances. Proc 18th S.E. Conf. Comb., GT, and Comp Utilitas Math. (1982).
M.C. Golumbic, C.L. Monma, and W.T. Trotter, Tolerance graphs, (to appear).
M.C. Golumbic, D. Rotem, and J. Urrutia, Comparability graphs and intersection graphs. Disc. Math (to appear).
R.L. Graham and F.R.K. Chung, On multicolor Ramsey numbers for complete bipartite graphs. J. Comb. Th. (B) 18 (1975), 164–169.
R.L. Graham and L.H. Harper, Some results on matching in bipartite graphs. SIAM J. Appl. Math 17 (1969), 1017–1022.
C. Greene, An extension of Schensted’s theorem. Advances in Math 14 (1974), 254–265.
C. Greene, Sperner families and partitions of a partially ordered set. Combinatorics (Hall and J.H. Van Lint), Math. Center Tracts 56(1974), 91–106.
C. Greene, Some partitions associated with a partially ordered set. J. Comb. Th. (A) 20 (1976), 69–79.
C. Greene and D.J. Kleitman, The structure of Spernerk-families. J. Comb. Th. (A) 20 (1976), 41–68.
C. Greene and D.J. Kleitman, Strong versions of Sperner’s Theorem. J. Comb. Th. (A) 20 (1976), 80–88.
C. Greene and D.J. Kleitman, Proof techniques in the theory of finite sets. InStudies in Combinatorics, (G.-C. Rota, ed.), MAA Studies in Math. 17(1978) 22–79.
D.A. Gregory and N.J. Pullman, On a clique covering problem of Orlin. Disc. Math 41 (1982), 97–99.
J.R. Griggs, Sufficient conditions for a symmetric chain order. SIAM J. Appl. Math 32 (1977), 807–809.
J.R. Griggs, Another three-part Sperner theorem. Studies Appl. Math. 57 (1977), 181–184.
J.R. Griggs, Extremal values of the interval number of a graph, II. Discrete Math. 28 (1979), 37–47.
J.R. Griggs, On chains and Spernerk-families in ranked posets. J. Comb. Theory A 28 (1980), 156–168.
J.R. Griggs, The Littlewood-Offord problem: tightest packing and anm-part Sperner theorem. Europ. J Comb 1 (1980), 225–234.
J.R. Griggs, Poset measure and saturated partitions. Studies in Appl. Math 66 (1982), 91–93.
J.R. Griggs, Lower bounds on the independence number in terms of the degrees. J. Comb. Th. (B) 34 (1983), 22–39.
J.R. Griggs, The Sperner property, in Ordres: Description et Roles (Proc. Lyon 1982, (M. Pouzet, ed.) Annals of Discrete Math. (1984), 371–387.
J.R. Griggs and D.J. Kleitman, A three-part Sperner theorem. Disc. Math 17 (1977), 281–289.
J.R. Griggs, A.M. Odlyzko, and J.B. Shearer, k-color Sperner theorems, (to appear).
J.R. Griggs, J. Stahl, and W.T. Trotter, A Sperner theorem on unrelated chains of subsets. J. Comb. Th. (A) 36 (1984), 124–127.
J.R. Griggs, D. Sturtevant, and M. Saks, On chains and Spernerk-families in ranked posets, II. J. of Comb. Theory A 29 (1980), 391–394.
J.R. Griggs and D.B. West, Extremal values of the interval number of a graph, I. SIAM J. Alg. Disc. Meth 1 (1980), 1–7.
P.A. Grillet, Maximal chains and antichains. Funda. Math. 15 (1969), 157–167.
M. Grotschel, L. Lovasz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981), 169–197.
L. Guttman, A basis for scaling quantitative data. Amer. Sociol. Rev 9 (1944), 139–150.
A. Gyarfas, On the chromatic number of multiple interval graphs and overlap graphs, (preprint).
A. Gyarfas and J. Lehel, A Helly-type problem in trees, in Combinatorial Theory and Its Applications, II (P. Erdos et al, eds.) (North-Holland, 1970), 571–584.
A. Gyarfas and J. Lehel, Covering and coloring problems for relatives of intervals, (to appear).
R. Gysin, Dimension transitiv orientierbarer Graphen. Acta Math. Acad. Sci. Hungar 29 (1977), 313–316.
M. Habib, Comparability invariants, in Ordres: Description et Roles (Proc. Lyon 1982), Annals of Discrete Math (1984), 371–387.
M. Habib and M.C. Maurer, On the X-join decomposition for undirected graphs. Disc. Appl. Math 3 (1979), 198–207.
G. Hajos, Uber eine Art von Graphen. Int. Math. Nachr. 47 (1957), 65.
[H4] R. Halin, Some remarks on interval graphs. Combinatorica3 (1982), 297–304.
P.L. Hammer, T. Ibaraki, and U.N. Peled, Threshold numbers and threshold completions. inStudies on Graphs and Discrete Programming (P. Hansen, ed.), Annals Disc. Math 11(1981), 125–145.
P.L. Hammer, T. Ibaraki, and B. Simeone, Threshold sequences. SIAM J. Alg. Disc. Meth 2(1981), 39–49. Contains “Degree sequence of threshold graphs”, Univ. of Waterloo Rept. CORR 78–10 (1978).
P.L. Hammer and B. Simeone, The splittance of a graph. Combinatorica 1 (1981), 275–284.
P.L. Hammer and N.V.R. Mahadev, Bithreshold graphs, Research Report CORR 83-35, Univ. of Waterloo (1983).
P.L. Hammer, N.V.R. Mahadev, and U.N. Peled, Some properties of 2-threshold graphs, (to appear).
P. Hanlon, Counting interval graphs. Trans. Amer. Math. Soc 272 (1982), 383–426.
F. Harary and J. Kabell, An intuitive approach to interval numbers of graphs. Math. Mag. 53(1980), 39–44.
L.H. Harper, The morphology of partially ordered sets. J. Comb. Th (A) 17(1974), 44–58.
E. Harzheim, Ein endlichkeitssatz uber die Dimension teiweise geordneter Mengen. Math. Nachr. 46(1970), 183–188.
E. Harzheim, On Dilworth’s decomposition theorem. Ars Combinatoria
E. Harzheim, Combinatorial theorems on contractive mappings in power sets. Disc. Math 40 (1982), 193–202.
E. Harzheim, A constructive proof for a theorem on contractive mappings in power sets. Disc. Math 45 (1983), 99–106.
T.F. Havel, The combinatorial distance geometry approach to the calculation of molecular conformation. Ph.D. Thesis, Univ. Calif.—Berkeley (1982).
P.B. Henderson and Y. Zalcstein, A graph-theoretic characterization of the PV chunk class of synchronizing primitives. SIAM J. Comp 6 (1977), 88–108.
P. Hell, Subdirect products of bipartite graphs, inInfinite and Finite Sets, Colloq. Math. Soc. Janos Bolyai 10 (1973), 857–866.
T. Hiraguchi, On the dimension of partially ordered sets. Sci. Rep. Kanazawa Univ. 1(1951), 77–94.
T. Hiraguchi, On the dimension of orders. Sci. Rep. Kanazawa Univ. 4(1955), 1–20.
C.T. Hoang, A class of perfectly orderable graphs, (preprint).
A.J. Hoffman, The uses of linear programming in ordered sets, inOrdered Sets (I. Rival, ed.) D. Reidel, Dordrecht (1982), 619–654.
A.J. Hoffman and J.B. Kruskal, Integral boundary points of convex polyhedra. in Linear Inequalities and Related Systems (H.W. Kuhn and A.W. Tucker, eds.), Annals of Math. Studies 38, Princetom Univ. Press, Princeton (1956), 223–246.
A.J. Hoffman and D.E. Schwartz, On lattice polyhedra. Combinatorics, Colloq. Math. Soc. Janos Bolyai 18 (1976), 593–598.
A.J. Hoffman and D.E. Schwartz, On partitions of a partially ordered set. J. Comb. Theory B 23 (1977), 3–13.
G. Hopkins and W. Staton, Extremal bipartite subgraphs of cubic triangle-free graphs. J. Graph Theory 6 (1982), 115–121.
G. Hopkins and W. Staton, Maximal bipartite subgraphs. Ars Combinatoria 13 (1982), 223–226.
G. Hopkins and W. Staton, Girth and independence ratioCanad. Math. Bull, (to appear).
L. Hopkins and W.T. Trotter, A bound on the interval number of a complete multipartite graph. Theory and Applications of Graphs (Chartrand et al, eds.) (Wiley, 1981), 391–407.
L. Hopkins, W.T. Trotter, and D.B. West, The interval number of the complete multipartite graph. Disc. Appl. Math, to appear.
W.N. Hsieh and D.J. Kleitman, Normalized matching in direct products of partial orders. Studies in Appl. Math 52 (1973), 285–289.
T. Ibaraki and U.N. Peled, Sufficient conditions for graphs to have threshold number 2. inStudies on Graphs and Discrete Programming (P. Hansen, ed.), Annals Disc. Math 11(1981), 241–268.
T. Kameda, On maximally distant spanning trees of a graph. Computing 17(1976), 115–119.
G.O.H. Katona, On a conjecture of Erdos and a stronger form of Sperner’s theorem. Stud. Sci. Math. Hung 1(1966), 59–63.
G.O.H. Katona, A generalization of some generalizations of Sperner’s theorem. J. Comb. Theory B 12(1972), 72–81.
G.O.H. Katona, A three-part Sperner theorem. Stud. Sci. Math. Hung 8(1973), 379–390.
G.O.H. Katona, Extremal problems for hypergraphs. Combinatorics (M. Hall and J.H. Van Lint), Math. Center Tracts 56(1974), 13–42.
D. Kelly, 3-Irreducible partially ordered sets. Can. J. Math 29(1977), 367–383.
D. Kelly, On the dimension of partially ordered sets. Disc. Math 35(1981), 135–156.
D. Kelly, Comparability graphs, this volume.
D. Kelly, in Open problems. Order 1(1984), No. 2.
D. Kelly and D.A. Daykin, Strict LYM orders, (preprint).
D. Kelly and I. Rival, Planar lattices. Canad. J. Math 27(1975), 636–665.
D. Kelly and I. Rival, Certain partially ordered sets of dimension 3. J. Comb. Th. (A) 18(1975), 239–242.
D. Kelly, J. Schonheim, and R. Woodrow, Relating vertex colorability of graphs and hypergraphs. Univ. Calgary Math. Res. Paper #481.
D. Kelly and W.T. Trotter, Dimension theory for ordered sets, inOrdered Sets (I. Rival, ed.), North-Holland (1982), 171–212.
R. Kimble, Extremal problems in dimension theory for partially ordered sets. Ph.D. thesis, M.I.T. (1973).
D.J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums. Math. Zeitschr 90(1965), 251–259.
D.J. Kleitman, On an extremal property of antichains in partial orders: the LYM property and some of its implications and applications. Combinatorics (Hall and J.H. Van Lint), Math. Centre Tracts 56(1974), 77–90.
D.J. Kleitman, Extremal hypergraph problems, in Surveys in Combinatorics (B. Bollobas, ed.), 7th Brit. Comb. Conf., London Math. Soc. Lec. Notes 38, Cambridge Univ. Press (1979), 44–65.
D.J. Kleitman and M. Saks, Stronger forms of the LYM inequality.
D.J. Kleitman, D. Sturtevant, M. Saks, and J. Shearer
H. Komm, On the dimension of partially ordered sets. Amer. J. Math 70(1948), 507–520.
L.T. Kou, L.J. Stockmeyer, and C.K. Wong, Covering edges by cliques with regard to keyword conflicts and intersection graphs. Comm. Assoc. Comp. Mach 21(1978), 135–139.
P. Krivka, The dimension of odd cycles and cartesian cubes, inAlgebraic Methods in Graph Theory (Szeged, 1978) (L. Lovasz and V.T. Sos, eds.), Coll. Math. Soc. J. Bolyai 25(1981), 435–443.
P. Krivka, Dimension of the sum of two copies of a graph. Czech. Math. J 31(1981), 514–520.
C. Kruskal and D.B. West, The minimum size of a compatible matching in a bipartite graph, (submitted to 5th Intl Conf. in Graph Theory).
L. Kucera, J. Nesetril, and A. Pultr, Complexity of dimension three and some related edge-covering characteristics of graphs. Theor. Comp. Sci 11(1980), 93–106.
J.R. Kung, ed. ??Recent Advances in the Theory of Young Tableaux.
E.L. Lawler, Combinatorial Optimization and Matroids. Holt, Rinehart, and Winston, New York (1976).
E.L. Lawler and O. Vornberger, The partial order dimension problem is NP-complete. (unpublished).
B. LeClerc, Arbres et dimension des ordres. Disc. Math 14(1976), 69–76.
J. Lehel and Z. Tuza, Triangle-free partial graphs and edge covering theorems. Disc. Math 39(1982), 59–65.
R. Leibowitz, Interval counts and threshold graphs, Ph.D. Thesis, Rutgers Univ. (1978).
R. Leibowitz, S.F. Assmann, and G.W. Peck, Interval counts of interval graphs. SIAM J. Alg. Disc. Meth 3(1982), 485–494.
C.B. Lekkerkerker and J. Ch. Boland, Representation of a finite graph by a set of intervals on the real line. Fund. Math 51(1962), 45–64.
G.S. Leuker and K.S. Booth, A linear time algorithm for deciding interval graph isomorhism. J. Assoc. Comp. Mach 26(1979), 183–195.
M. Lewin, On intersection multigraphs of hypergraphs. J. Comb. Th. (B) 34(1983), 229–232.
B. Lindstrom, A partition of L(3,n) into saturated symmetric chains. Europ. J. Comb 1(1980), 61–63.
N. Linial, Covering digraphs by paths. Disc. Math 23(1978) 257–272.
N. Linial, Extending the Greene-Kleitman theorem to directed graphs. J. Comb. Th. A 30(1981), 331–334.
W. Lipski, The consecutive retrieval property, interval graphs, and related topics — a survey, inProc. Conf. on Consecutive Retrieval Property (T. Kambayashi, ed.) Inst, of Comp. Sci., Polish Acad. Sci., Rept. 438 (1981), 110–141.
S.C. Locke, Maximumk-colorable subgraphs. J. Graph Theory 6(1982), 123–132.
L. Lovasz, On covering of graphs, in Theory of Graphs, Tihany 1966 (P. Erdos and G. Katona, eds.) Academic Press (1969), 231–236.
L. Lovasz, Normal hypergraphs and the perfect graph conjecture. Disc. Math 2(1972), 253–267.
L. Lovasz, A characterization of perfect graphs. J. Comb. Th.(B) 13(1972), 95–98.
L. Lovasz, 2-matchings and 2-covers of hypergraphs. Acta Math. Acad. Sci. Hung 26(1975), 433–444.
L. Lovasz, On two minimax theorems in graph theory, J. Comb. Th (B) 21(1976), 96–103.
L. Lovasz, Certain duality principles in integer programming. Annals Disc. Math 1(1977), 363–374.
L. Lovasz, On the shannon capacity of a graph. IEEE Trans. Info. Th 25(1979), 1–7.
L. Lovasz, Perfect Graphs, inSelected Topics in Graph Theory (Academic Press, 1983), 55–87.
L. Lovasz, J. Nesetril, and A. Pultr, On a product dimension of graphs. J. Comb. Th. (B) 29(1980), 47–67.
D. Lubell, A short proof of Sperner’s lemma. J. Comb. Theory (1966), 299.
D. Lubell, Local matching in the function space of a partial order. J. Comb. Th. (A) 19(1975), 154–159.
C.L. Lucchesi and D.H. Younger, A minimax relation for directed graphs. J. London Math. Soc. (2) 17 (1978), 369–374.
M. Las Vergnas, C. R. Acad. Sci. Paris (A) 272 (1971).
M. Las Vergnas, Sur les circuits dans les sommes completees de graphes orientes. Coll. Theorie des Graphes, Inst. Hautes Etudes Belgique (1973), 231–244.
J. Lehel, A 5-color algorithm for triangle-free overlap graphs, (preprint).
H.T. Loh and H.H. Teh, On the dimension of product graphs. Nanta Math 1(1966/67), 68–71.
C. Maas, Some results about the interval number of a graph. Disc. Appl. Math 6(1983), 99–102.
C. Maas, Determining the interval number of a triangle-free graph. Computing 31(1983), 347–354.
C. Maas, A lower bound for the interval number of a graph. J. Computational Appl. Math 10(1984), 65–69.
H. Maehara, On time graphs. Disc. Math 32(1980), 281–289.
H. Maehara, Space graphs and spericity. Disc. Appl. Math 7(1984), 55–64.
N.V.R. Mahadev and D. de Werra, On a class of perfectly orderable graphs. Univ. Waterloo CORR 83/27 (1983).
G. Malle, On maximum bipartite subgraphs. J. Graph Theory 6(1982), 105–113.
P. Marchioro, A. Morgana, R. Petreschi, and B. Simeone, Degree sequences of matrogenic graphs, (preprint).
T.M. Matthews and W.T. Trotter, The interval number of the complete multipartite graph. 2nd Annual SE SIAM Meeting, 1978.
S.B. Maurer and I. Rabinovitch, Large minimal realizers of a partial order. Proc. Amer. Math. Soc 66(1978), 211–216.
S.B. Maurer, I. Rabinovitch, and W.T. Trotter, Partially ordered sets with equal rank and dimension. Proc. 10th SE Conf. on Comb. Graph Theory, and Comp Comgressus Numerantium 29(1980), 627–637.
S.B. Maurer, I. Rabinovitch, and W.T. Trotter, Large minimal realizers of a partial order II, Disc. Math 31(1980), 297–314.
S.B. Maurer, I. Rabinovitch, and W.T. Trotter, A generalization of Turan’s theorem to directed graphs. Disc. Math 32(1980), 167–189.
F.R. McMorris and G.T. Myers, Some uniqueness results for upper bound graphs. Disc. Math 44(1983), 321–323.
F.R. McMorris and T. Zaslavsky, Bound graphs of a partially ordered set. J. Comb. Inf. Syst. Sci 7(1982), 134–138.
L.D. Meshalkin, A generalization of Sperner’s Theorem on the number of subsets of a finite set. Teor. Verojatnosti Primener 8(1963), 219–220 (in Russian)—Theory Probab. Appl (English trans.) 8(1963), 203–204.
L.D. Meshalkin, A generalization of Sperner’s Theorem on the number of subsets of a finite set. Teor. Verojatnosti Primener 8(1963), 219–220 (in Russian)—Theory Probab. Appl (English trans.) 8(1963), 203–204.
H. Meyniel, On the perfect graph conjecture. Disc. Math 16(1976), 339–342.
L. Mirsky, A dual of Dilworth’s decomposition theorem. Amer. Math. Monthly 78(1971), 876–877.
R.H. Mohring, Algorithmic aspects of comparability graphs, this volume.
B. Monjardet, Axiomatiques et proprietes des quasi-ordres. Math. Sci. Hum 63(1978), 51–82.
B. Monjardet and E. Jacquet-Lagreze, Modelisation des preferences et quasi-ordres. Math. Sci. Hum 62(1978), 5–10.
J.I. Moore, Interval hypergraphs and D-interval hypergraphs. Disc. Math 17(1977), 173–179.
A. Mycielski, Sur le coloriage des graphes. Colloq. Math 3(1955), 161–162.
G.T. Myers, Upper bound graphs of partially ordered sets. Ph.D. Thesis, Bowling Green State Univ. (1982).
C.St.J. Nash-Williams, Decomposition of finite graphs into forests. J. London Math. Soc 39(1964), 12–17.
C. Nara, Split graphs with Dilworth number three. Natur. Sci. Rep. Ochanomizu Univ 33(1982), 37–44.
G.L. Nemhauser, L.E. Trotter, and R.M. Nauss, Set partitioning and chain decomposition. Management Sci 20(1974), 1413–1473.
J. Nesetril and A. Pultr, A Dushnik-Miller type dimension of graphs and its complexity. inFundamentals of Computation Theory, Lecture Notes in Comp. Sci. 50, Springer-Verlag (1977), 482–493.
J. Nesetril and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects. Disc. Math 22(1978), 287–300.
J. Nesetril and A. Pultr, Product and other representations of graphs and related characteristics, inAlgebraic Methods in Graph Theory (Szeged, 1978) (L. Lovasz and V.T. Sos, eds.), Coll. Math. Soc. J. Bolyai 25(1981), 571–598.
J. Nesetril and V. Rodl, A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of graphs. Disc. Math 23(1978), 49–55.
U. Neumann, Einige Beobachtunen zur Dimension von Graphen, Diplomarbeit, Technische Hochschule Darmstadt (1982).
V. Novak, The dimension of lexicographic sums of partially ordered sets. (1961).
H. Oellrich and K. Steffens, On Dilworth’s decomposition theorem. Disc. Math 15(1976), 301–304.
R.J. Opsut and F.S. Roberts, On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems, in The Theory and Applications of Graphs (G. Chartrand et al, eds.), Proc. 4th Intl. Cojif: Graph Th., Wiley, New York (1981), 477–492.
O. Ore. Theory of Graphs (Amer. Math. Soc., 1962), Section 10.4.
J. Orlin, Contentment in graph theory: covering graphs with cliques. Proc. Konink. Nederl. Acad. Weten. (A) 80(1977), 406–424.
M.W. Padberg, Perfect zero-one matrices. Math. Prog 6(1974), 180–196.
M.W. Padberg, Almost integral polyhedra related to certain combinatorial optimization problems. Lin. Alg. Appl 15(1976), 69–88.
M.W. Padberg, On the complexity of set packing polyhedra. Annals Disc. Math 1(1977), 421–434.
M. Paoli, W.T. Trotter, and J.W. Walker, Graphs and orders in Ramsey theory and in dimension theory. In this volume.
C.H. Papadimitriou and M. Sipser, Communication complexity. Proc. 14th ACM Symp. Th. Comp (1982), 330–337.
C. Payan, A class of threshold and domishold graphs: equistable and equidominating graphs. Disc. Math 29(1980), 47–52.
C. Payan, Perfectness and Dilworth number. Disc. Math 44(1983), 229–230.
U.N. Peled, Matroidal graphs. Disc. Math 20(1977), 263–286.
U.N. Peled, Threshold graph enumeration and series-product identities. Proc. 11th SE Conf. Comb. Graph Th. Comp. Congressus Num. 29(1980), 735–738
U.N. Peled and B. Simeone, Box-threshold graphs. J. Graph Th 8(1984), 331–345.
M.A. Perles, A proof of Dilworth’s decomposition theorem for partially ordered sets. Israel J. of Math 1(1963), 105–107.
M.A. Perles, On Dilworth’s theorem in the infinite case. Israel J. Math 1(1963), 108–109.
A. Pnueli, S. Even, and A. Lempel, Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math 23(1971)160–175.
S. Poljak, A note on stable sets and colorings of graphs. Comm. Math. Univ. Carolinae 15(1974), 307–309.
S. Poljak and A. Pultr, On the dimension of trees. Disc. Math 34(1981), 165–171.
S. Poljak and A. Pultr, Representing graphs by means of strong and weak products. Comment. Math. Univ. Carol 22(1981), 449–465.
S. Poljak, A. Pultr, and V. Rodl, On the dimension of the Kneser graphs, inAlgebraic Methods in Graph Theory (L. Lovasz and V.T. Sos, eds.), Coll. Math. Soc. J. Bolyai 25(1981), 631–646.
S. Poljak, A. Pultr, and V. Rodl, On a product dimension of bipartite graphs. J. Graph Th 7(1983), 475–486.
S. Poljak and V. Rodl, Orthogonal partitions and covering of graphs, Czech. Math. J 30(1980), 475–485.
S. Poljak, V. Rodl, and D. Turzik, Complexity of representation of graphs by set systems. Disc. Appl. Math 3(1981), 301–312.
S. Poljak and D. Turzik, A note on dimension of P n3 . Czech. Math. J 31(1981)
M. Preissman, A class of strongly perfect graphs. Ecole Polytech. Fed., Lausanne, ORWP 83/3 (1983).
O. Pretzel, On the dimension of partially ordered sets. J. Comb. Th. (A) 25(1977), 50–61.
O. Pretzel, Another proof of Dilworth’s decomposition theorem. Disc. Math 25(1979), 91–92.
O. Pretzel, A construction for posets. Disc. Math 32(1980), 59–68.
R.A. Proctor, M.E. Saks, and D.G. Sturtevant, Product partial orders with the Sperner property. Disc. Math 30(1980), 173–180.
N.J. Pullman, Clique coverings of graphs—a survey. Proc. Xth Austral. Conf. Comb. Math., Adelaide 1982, Springer-Verlag Lect. Notes Math. 1036 (1983), 72–85.
N.J. Pullman, Clique coverings of graphs IV: Algorithms. SIAM J. Comp (to appear).
N.J. Pullman and D. de Caen, Clique coverings of graphs III: Clique coverings of regular graphs. Congr. Numer 29(1980), 795–808.
N.J. Pullman and D. de Caen, Clique coverings of graphs I: Clique partitions of regular graphs. Utilitas Math 19(1981), 177–205.
N.J. Pullman and A. Donald, Clique coverings of graphs II: Complements of cliques. Utilitas Math 19(1981), 207–213.
A. Pultr, Tensor products in the category of graphs. Commun. Math. Univ. Carol 11(1970), 619–639.
A. Pultr, On productive classes of graphs determined by prohibiting given subgraphs. inCombinatorics (A. Hajnal and V.T. Sos, eds.) Colloq. Math. Soc. Janos Bolyai 18 (North-Holland, 1978), 805–820.
A. Pultr and J. Vinarek, Productive classes and subdirect irreducibility, in particular for graphs. Disc. Math 20(1977), 159–176.
I. Rabinovitch, The dimension theory of semiorders and interval orders, Ph.D. thesis, Dartmouth College (1973).
I. Rabinovitch, The Scott-Suppes theorem on semi-orders. J. Math. Psych 15(1977), 209–212.
I. Rabinovitch, The dimension of semi-orders. J. Comb. Th. (A) 25(1978), 50–61.
I. Rabinovitch, Upper bound on dimension of interval orders. J. Comb. Th. (A) 25(1978), 68–71.
I. Rabinovitch and I. Rival, Rank of a distributive lattice. Disc. Math 25(1979), 275–279.
G. Ravindra, Meyniel graphs are strongly perfect. J. Comb. Th. (B) 33(1982), 187–190.
A. Ray-Chaudhuri, unpublished.
R.C. Read, D. Rotem, and J. Urrutia, Orientations of circle graphs. J. Graph Th 6(1982), 325–241.
P.L. Renz, Intersection representations of graphs by arcs, Pac. J. Math 34(1970), 501–510.
B. Resnick, P. Tiwari, and D.B. West, Decomposition of product graphs into complete bipartite subgraphs, (preprint).
W. Riess, Zwei Optimierungsprobleme auf Ordnungen. Arbeitsbereichte des institute fur mathematische Maschinen und Datenwerarbeitung (Informatik) II 5(1978), 50–57.
J. Riguet, Les relations de Ferrers. C.F. Acad. Sci. Paris 232(1951), 1729.
I. Rival, The diagram. In this volume.
I. Rival and N. Zaguia, Antichains and cutsets, to appear.
F.S. Roberts, Indifference graphs, inProof Techniques in GT (F. Harary, ed.). Academic Press (1969), 139–146.
F.S. Roberts, On the boxicity and cubicity of a graph. Recent Progress in Combinatorics (W.T. Tutte, ed.) (Acadamic Press, 1969).
F.S. Roberts, Graph Theory and its Applications to the Problems of Society, CBMS-NSF Conf. (Soc. Ind. Appl. Math, 1978)
F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, inTheory and Application of Graphs, Kalamazoo 1976 (Y. Alavi and D. Lick, eds.) Springer-Verlag Lect. Notes Math. 642 (1978), 477–490.
F.S. Roberts, Measurement theory. Encyc. Math. Appl 7(1979) (Addison-Wesley)
F.S. Roberts, Indifference and seriation. inAdvances in Graph Theory (F. Harary, ed.), New York Acad. Sci. 328(1979), 171–180.
F.S. Roberts, Applications of edges coverings by cliques. Disc. Appl. Math (to appear).
F.S. Roberts, Issues in the theory of uniqueness in measurement, inGraphs and Order. (I. Rival, ed.) D. Reidel (1985).
F.S. Roberts and J.E. Steif, A characterization of competition graphs of arbitrary digraphs. Disc. Appl. Math 6(1983), 323–326.
D. Rotem and J. Urrutia, Circular permutation graphs. Networks 12(1982), 429–437.
M. Roubens and P. Vincke, Linear orders and semiorders close to an interval order. Disc. Appl. Math 6(1983), 311–314.
B. Roy, Nombre chromatique et plus longs chemins. Rev. Fr. Automat. Inform 1(1967), 127–132.
G. Sabidussi, Subdirect representations of graphs, in Infinite and Finite Graphs, Colloq. Math. Soc. Janos Bolyai 10(1973), 1199–1226.
M. Saks, A short proof of the existence ofk-saturated partitions of partially ordered sets. Advances in Math 33(1979), 207–211.
M. Saks, Duality properties of finite set systems. Ph.D. Thesis, M.I.T. (1980). See also “Some integer sequences associated with combinatorial structures,” to appear.
M. Saks, Dilworth numbers, incidence maps, and product partial orders. SIAM J. Alg. Disc. Meth 1(1980), 211–216.
A. Sali, Stronger form of an M-part Sperner theorem. Europ. J. Comb 4(1983), 179–183.
N. Sauer and R.E. Woodrow, Finite cutsets and finite antichains. Order 1, 35.
E.R. Scheinerman, Intersection graphs and multiple intersection parameters of graphs, Ph.D Thesis, Princeton Univ. (1984).
E.R. Scheinerman, Characterizing intersection classes. Disc. Math (to appear).
E.R. Scheinerman, Irrepresentability by multiple intersection, or why the interval number is unbounded. (to appear).
E.R. Scheinerman and D.B. West, The interval number of a planar graph: Three intervals suffice. J. Comb. Th. (B) 35(1983), 224–239.
J. Schonheim, A generalization of results of P. Erdos, G. Katona and D.J. Kleitman concerning Sperner’s theorem. J. Comb. Theory 11(1971), 111–117.
A. Schrijver, A counterexample to a conjecture of Edmonds and Giles. Disc. Math 32(1980), 213–214.
A. Schrijver, On total dual integrality. Linear Alg. Appl 38(1981), 27–32.
A. Schrijver, Short proofs on the matching polyhedron. J. Comb. Th. (B) 34(1983), 104–108.
D. Scott, Measurement models and linear inequalities. J. Math. Psych 1(1964), 233–247.
D. Scott and P. Suppes, Foundational aspects of theories of measurement. J. Symbolic Logic 23(1958), 113–128.
J.B. Shearer, A note on circular dimension. Disc. Math 30(1980), 103.
L.N. Shevrin and N.D. Filippov, Partially ordered sets and their comparability graphs, Siber. Math. J 11(1970), 497–507 (648–667 in Russian).
L.N. Shevrin and N.D. Filippov, Partially ordered sets and their comparability graphs, Siber. Math. J 11(1970), 497–507 (648–667 in Russian).
D. Skrien, A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs. J. Graph Th 6(1982).
D. Skrien, Chronological orderings of interval graphs. Disc. Appl. Math. 7(1984).
P.J. Slater, A note on pseudointersection graph. J. Res. Nat. Bur. Stan 80B(1976), 441–445.
J. Spencer, Minimal scrambling sets of simple orders, Acta. Math. Acad. Sci. Hungar 22(1971), 349–353.
E. Sperner, Ein Satz uber Untermengen einer endlichen Menge. Math. Z 27(1928), 544–548.
E. Spilrajn, Sur l’extension de l’ordre partiel. Fund. Math 16(1930), 386–389.
J. Spinrad, Two-dimensional partial orders, Ph.D. Thesis, Princeton Univ. (1982). See also “Transitive orientation in0(n 2) time,”Proc. 15th ACM Symp. Th. Comp (1983), 457–466.
J. Stahl, On the 2-dimension of the crown S nk . (preprint).
J. Stahl and R. Wille, Preconcepts of contexts, in Proc. Universal Algebra (Sienna, 1984). (to appear).
R. Stanley, unpublished?
J.E. Steif, Frame dimension, generalized competition graphs, and forbidden sublist characterizations. Henry Rutger Thesis, Rutgers Univ. (1982).
L. Suranyi, the covering of graphs by cliques, Stud. Sci. Math. Hung 3(1968), 345–349.
M.M. Syslo, On characterizations of cycle graphs, inProblemes Combinatoires et Theorie des Graphes, Colloq. CNRS Orsay 1976, Paris (1978), 395–398.
M.M. Syslo, On characterizations of kcycle graphs and on other families of intersection graphs. Report N40, Inst, of Comp. Sci., Univ. of Wroclaw (1978).
M.M. Syslo, Triangulated tree-edge-interval graphs, (preprint).
M.M. Syslo, A graph-theoretic approach to the jump number problem. In this volume.
V.S. Tanaev, Optimal decomposition of a partially ordered set into chains. Doklady Akad. Nauk. BSSR 23(1979), 389–391. MR 80m:06003.
R.E. Tarjan, Decomposition by clique separators. Disc. Math (to appear).
D. Taylor, R.D. Dutton, and R.C. Brigham, Bounds on Nordhaus-Gaddum type bounds for clique cover numbers. Congressus Numer 40(1983), 199–234.
H.H. Teh, Dimensions and auto-extensions of graphs. Nanta Math 3(1969), 23–32.
J. Tind, On antiblocking sets and polyhedra. Annals Disc. Math 1(1977), 507–515.
J. Tind, Blocking and antiblocking polyhedra. AnnalsDisc. Math 4(1979), 159–174.
B. Toft, On the maximal number of edges of criticalk-chromatic graphs. Stud. Sci. Math. Hungar 5(1970), 461–470.
B. Toft, On critical subgraphs of color-critical graphs. Disc. Math 7(1974), 377–392.
C. Totter, unpublished (Darmstadt).
C.A. Tovey and D.B. West, A network approach to duality theorems in products of partial orders. Order (to appear).
L.E. Trotter and D.B West, Two easy duality theorems on products of partial orders. (preprint).
W.T. Trotter, Dimension of the crown S kn . Disc. Math8 (1974), 85–103.
W.T. Trotter, Irreducible posets with large height exist. J. Comb. Th. (A) 17(1974), 337–344.
W.T. Trotter, Inequalities in dimension theory for posets. Proc. Amer. Math. Soc 47(1975), 311–316.
W.T. Trotter, A note on Dilworth’s embedding theorem. Proc. Amer. Math. Soc 52(1975), 33–39.
W.T. Trotter, Embedding finite posets in cubes. Disc. Math 12(1975), 165–172.
W.T. Trotter, A generalization of Hiraguchi’s inequality for posets. J. Comb. Th. (A) 20(1976), 114–123.
[T18] W.T. Trotter, A forbidden subposet characterization of an order-dimension inequality. Math. Syst. Th. 10 (1976), 91–96.
W.T. Trotter, Combinatorial problems in dimension theory for partially ordered sets. Proc. Comb. and Graph Theory, Univ. of Paris, Orsay (1976).
W.T. Trotter, The dimension of planar posets. J. Comb. Th. (B) (1977), 54–67.
W.T. Trotter, A characterization of Roberts’ inequality for boxicity. Disc. Math 28(1979), 303–313.
W.T. Trotter, Stacks and splits of partially ordered sets. Disc. Math 35(1981), 229–256.
W.T. Trotter, Jr., Graphs and partially ordered sets, inSelected Topics in Graph Theory, Vol. II (L. Beineke and R. Wilson, eds.). Academic Press, New York (1983), 237–268.
W.T. Trotter, The dimension of the cartesian product of posets. in Ordres: Description et Roles (M. Pouzet, ed.)Annals Disc. Math (1984).
W.T. Trotter, A note on the greedy dimension of ordered sets. Order (to appear).
W.T. Trotter, personal communication.
W.T. Trotter and K.P. Bogart, Maximal dimensional partially ordered sets III: A characterization of Hiraguchi’s inequality for interval dimension. Disc. Math 15(1976), 389–400.
W.T. Trotter and K.P. Bogart, On the complexity of posets. Disc. Math 16(1976), 71–82.
W.T. Trotter and F. Harary, On double and multiple interval graphs. J. Graph Th 2(1978), 137–142.
W.T. Trotter and T.R. Monroe, A combinatorial problem involving graphs and matrices. Disc. Math 39(1982), 87–101.
W.T. Trotter and J.I. Moore, Characterization problems for graphs, partially ordered set, lattices, and families of sets. Disc. Math 16(1976), 361–381.
W.T. Trotter and J.I. Moore, Some theorems on graphs and posets. Disc. Math 15(1976), 79–84.
W.T. Trotter and J.I. Moore, The dimension of planar posets. J. Comb. Th. (B) 22(1977), 54–67.
W.T. Trotter, J.I. Moore, and D.P. Sumner, Dimension of a comparability graph. Proc. Amer. Math. Soc 60(1976), 35–38.
W.T. Trotter and J.A. Ross, Every t-irreducible partial order is a suborder of a t+1-irreducible partial order. Annals Disc. Math. 17(1983), 613–621.
W.T. Trotter and J.A. Ross, For t≥ 3, every t -dimensional partial order is a suborder of a t + 1-irreducible partial order. Proc. Conf. Combinatorics and Graph Theory, Eger, Hungary, 1981 (to appear).
A.C. Tucker, Characterizing circular arc graphs. Bull. Am. Math. Soc 76(1970), 1257–1260.
A.C. Tucker, Matrix characterizations of circular arc graphs. Pac. J. Math 39(1971), 535–545.
A.C. Tucker, Structure theorems for some circular-arc graphs. Disc. Math 7(1974), 167–195.
A.C. Tucker, Coloring a family of circular arcs. SIAM J. Appl. Math 29(1975), 493–502.
A.C. Tucker, Circular arc graphs: new uses and a new algorithm. Theory and Application of Graphs, 581–589.
A.C. Tucker, An efficient test for circular-arc graphs. SIAM J. Computing 9(1980), 1–24.
P. Turan, An extremal problem in graph theory. Mat. Fiz. Lapok 48(1941), 436–452.
H. Tverberg, On Dilworth’s decomposition theorem for partially ordered sets. J. Comb. Th 3(1967), 305–306.
P. Tiwari, Lower bounds on communication complexity in distributed computer networks. Proc. 25th Symp. Found. Comp. Sci (1984).
K. Vesztergombi, Some remarks on the chromatic number of the strong product of graphs. Acta Cybernetica 4(1978), 207–212.
K. Vesztergombi, Chromatic number of strong product of graphs, inAlgebraic Methods in Graph Theory (L. Lovasz and V.T. Sos, eds.), North-Holland, New York (1981), 819–826.
G. Viennot, Chain and antichain families, grids, and Young tableaux, in Ordres: Description et Roles (Proc. Lyon 1982) (M. Pouzet, ed.)Annals of Discrete Math (1984), 409–463.
J.R. Walter, Representation of Rigid Cycle Graphs. Ph.D. Thesis, Wayne State Univ. (1972).
D.L. Wang, A note on uniquely intersectable graphs. Studies in Appl. Math 55(1976), 361–363.
G. Wegner, Eigenscharten der Nervan Homologische-einfacher Familien im Rn. Ph.D. thesis, Gottingen (1967).
D.B. West, A symmetric chain decomposition ofL(4, n). Eur. J. Comb 1(1980), 379–383.
D.B. West, Extremal problems in partially ordered sets, inOrdered Sets (I. Rival, ed.) D. Reidel, Dordrecht (1982), 473–521.
D.B. West, “Poly-unsaturated partitions”: The Greene-Kleitman Theorem is best possible. J. Comb. Th. (A) (submitted).
D.B. West, L.H. Harper, and D.A. Daykin, Some remarks on normalized matching. J. Comb. Th. (A) 35(1983), 301–308.
D.B. West and D.J. Kleitman, Skew chain orders and sets of rectangles. Disc. Math 27(1979), 99–102.
D.B. West and D.B. Shmoys, Recognizing graphs with fixed interval number is NP-complete. Disc. Appl. Math 8(1984), 295–305.
D.B. West and C.A. Tovey, Semiantichains and unichain coverings in the direct products of partial orders. SIAM J. Alg. Disc. Meth 2(1981), 295–305.
D. B. West, W. T. Trotter, Jr., G. W. Peck, and P. Shor, Regressions and monotone chains: a Ramsey-type extremal problem for partial orders. Combinatorica 4(1984), 117–119.
A.T. White and L.W. Beineke, Topological graph theory, inSelected Topics in Graph Theory (L.W. Beineke and R.W. Wilson, eds.) Academic Press (1978), 15–49.
R. Wille, Lexicographic decomposition of ordered sets (graphs), Fachbereich Mathematik, Tech. Hochschule Darmstadt, Report No. 705.
H.S. Witsenhausen, On intersections of interval graphs. Disc. Math 31(1980), 211–216.
D.R. Woodall, Menger and Konig systems, inTheory and Applications of Graphs, Kalamazoo 1976 (Y. Alavi and D.R. Lick, eds.) Springer-Verlag Lect. Notes 642 (1978), 620–635.
K. Yamamoto, Logarithmic order of free distributive lattices. J. Math. Soc. Japan 6(1954), 343–353.
M. Yannakakis, The complexity of the partial order dimension problem. SIAM J. Alg. Disc. Meth 3(1982), 351–358.
A.C. Yao, some complexity questions related to distributive computing. Proc. 11th ACM Symp. Th. Comp. (1979), 209–213
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 D. Reidel Publishing Company
About this chapter
Cite this chapter
West, D.B. (1985). Parameters of Partial Orders and Graphs: Packing, Covering, and Representation. In: Rival, I. (eds) Graphs and Order. NATO ASI Series, vol 147. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-5315-4_8
Download citation
DOI: https://doi.org/10.1007/978-94-009-5315-4_8
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-010-8848-0
Online ISBN: 978-94-009-5315-4
eBook Packages: Springer Book Archive