×
Golumbic, Martin Charles

Comparability graphs and a new matroid. (English) Zbl 0352.05023

J. Comb. Theory, Ser. B 22, 68-90 (1977).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0352.05023

Cited in 1 Review
Cited in 23 Documents

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05C99 Graph theory
06A06 Partial orders, general
Cite Review PDF
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Jordan-Polya numbers: products of factorial numbers A000142.

References:

[1] Aigner, M., Graphs and partial orderings, Monatsh. Math., 73, 385-396 (1969) · Zbl 0184.27502
[2] Aigner, M., Graphs and binary relations, (The Many Facets of Graph Theory. The Many Facets of Graph Theory, Lecture Notes in Mathematics, Vol. 110 (1969), Springer-Verlag: Springer-Verlag Berlin), 1-21 · Zbl 0186.27504
[3] Aigner, M.; Prins, G., Uniquely partially orderable graphs, J. London Math. Soc., 3, No. 2, 260-266 (1971) · Zbl 0214.51601
[4] Aigner, M.; Prins, G., Segment-preserving maps of partial orders, Trans. Amer. Math. Soc., 166, 351-360 (1972) · Zbl 0275.06002
[5] Berge, C., (Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam), Chap. 16 · Zbl 0483.05029
[6] Dushnik, B.; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · Zbl 0025.31002
[7] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[8] Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. Assoc. Comput. Mach., 19, 400-410 (1972) · Zbl 0251.05113
[9] Fishburn, P., An interval graph is not a comparability graph, J. Combinatorial Theory, 8, 442-443 (1970) · Zbl 0183.28602
[10] Fishburn, P., (Utility Theory for Decision Making (1970), Wiley: Wiley New York), Chap. 1 · Zbl 0213.46202
[11] Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., 18, 25-66 (1967) · Zbl 0153.26002
[12] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM J. Comp., 1, 180-187 (1972) · Zbl 0227.05116
[13] Ghouila-Houri, A., Caractérisation des graphes nonorientés dont on peut orienter les arêtes de manière à obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris, 254, 1370-1371 (1962) · Zbl 0105.35503
[14] Ghouila-Houri, A., Flot et tensions dans un graphe, Ann. Scient. École Norm. Sup., 81, 207-265 (1964) · Zbl 0178.57603
[15] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[16] Golumbic, M. C., An infinite class of superperfect noncomparability graphs, IBM Research, RC 5064 (October, 1974)
[17] Golumbic, M. C., Comparability graphs and a new matroid, (extended abstract), (Proc Alg. Aspects of Comb. (January, 1975), Univ. of Toronto) · Zbl 0365.05025
[18] Hedetniemi, S. T., Graphs of (0, 1)-matrices, (Recent Trends in Graph Theory. Recent Trends in Graph Theory, Lecture Notes in Mathematics, Vol. 186 (1971), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0217.31206
[19] Hedetniemi, S. T.; Slater, P. J., Line graphs of triangleless graphs and interated clique graphs, (Graph Theory and Applications. Graph Theory and Applications, Lecture Notes in Mathematics, Vol. 303 (1972), Springer-Verlag: Springer-Verlag Berlin), 139-147 · Zbl 0255.05121
[20] Lekkerkerker, C. G.; Boland, J. Ch, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501
[21] Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23, 160-175 (1971) · Zbl 0204.24604
[22] Roberts, F. S., Indifference graphs, (Harary, F., Proof Techniques in Graph Theory (1969), Academic Press: Academic Press New York), 139-146 · Zbl 0193.24205
[23] Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602
[24] Sharp, H., Enumeration of vacuously transitive relations, Discrete Math., 4, 185-196 (1973) · Zbl 0252.05003
[25] Shevrin, L. N.; Filippov, N. D., Partially ordered sets and their comparability graphs, Siberian Math. J., 11, 497-509 (1970) · Zbl 0214.23303
[26] Tucker, A., The strong perfect graph conjecture and an application to a municipal routing problem, (Graph Theory and Applications. Graph Theory and Applications, Lecture Notes in Mathematics, Vol. 303 (1972), Springer-Verlag: Springer-Verlag Berlin), 297-303 · Zbl 0247.05117
[27] Wilson, R. J., An introduction to matroid theory, Amer. Math. Monthyly, 80, 500-525 (1973) · Zbl 0275.05018
[28] Wolk, E. S., A note on the comparability graph of a tree, (Proc. Amer. Math. Soc., 16 (1965)), 17-20 · Zbl 0137.18105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.