×

zbMATH — the first resource for mathematics

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

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
05C99 Graph theory
06A06 Partial orders, general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M, Graphs and partial orderings, Monatsh. math., 73, 385-396, (1969) · Zbl 0184.27502
[2] Aigner, M, Graphs and binary relations, (), 1-21
[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, (), Chap. 16
[6] Dushnik, B; Miller, E.W, Partially ordered sets, Amer. J. math., 63, 600-610, (1941) · Zbl 0025.31002
[7] Eilenberg, S, ()
[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, (), Chap. 1
[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), () · Zbl 0365.05025
[18] Hedetniemi, S.T, Graphs of (0, 1)-matrices, () · Zbl 0217.31206
[19] Hedetniemi, S.T; Slater, P.J, Line graphs of triangleless graphs and interated clique graphs, (), 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, (), 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, (), 297-303
[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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.