×

Perfect graphs, kernels, and cores of cooperative games. (English) Zbl 1103.05034

Summary: A kernel of a directed graph \(D\) is defined as an independent set which is reachable from each outside vertex by an arc. A graph \(G\) is called kernel-solvable if an orientation \(D\) of \(G\) has a kernel whenever each clique of \(G\) has a kernel in \(D\). The notion of kernel-solvability has important applications in combinatorics, list coloring, and game theory. It turns out that kernel-solvability is equivalent to perfectness, as it was conjectured by Berge and Duchet in 1983. These and other kernel-related results are the subject of the present survey. Many of these results are independent of the strong perfect graph conjecture, yet, the recent proof of this conjecture and the efficient recognition of perfect graphs have several important implications, in particular in game theory, which are also included here.

MSC:

05C17 Perfect graphs
91A12 Cooperative games
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharoni, R.; Fleiner, T., On the lemma of Scarf, J. Combin. Theory (Ser. B), 87, 1, 72-80 (2003) · Zbl 1058.05031
[2] Aharoni, R.; Holzman, R., Fractional kernels in digraphs, J. Combin. Theory (Ser. B), 73, 1, 1-6 (1998) · Zbl 0904.05036
[3] Alon, N.; Tarsi, M., Colourings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[4] Apartsin, A.; Ferapontova, E.; Gurvich, V., A circular graph—counterexample to the Duchet kernel conjecture, Discrete Math., 178, 229-231 (1998) · Zbl 0886.05073
[5] Aumann, R. J.; Peleg, B., Von Neumann-Morgenstern solutions to cooperative games without side payments, Bull. Amer. Math. Soc., 66, 173-179 (1960) · Zbl 0096.14706
[6] Bang-Jensen, J.; Huang, J.; Prisner, E., In-tournament digraphs, J. Combin. Theory (Ser. B), 59, 267-287 (1993) · Zbl 0794.05033
[7] Berge, C., Farbung von Graphen, deren samtliche bzw deren ungerade Kreise starr sind, Wiss. Z. Martin Luther Univ. Halle Wittenbog, Math. Nat. Reihe, 10, 114-115 (1961)
[8] Berge, C., Sur une conjecture relative au probleme des codes optimaux (1961), Comm. 13-eme Assemble Generale de l’URSI: Comm. 13-eme Assemble Generale de l’URSI Tokyo
[9] Berge, C., Graphes et Hypergraphes. Dunod, Paris, 1970, Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam, (English translation)
[10] Berge, C., Perfect Graphs, (Fulkerson, D., Studies in Graph Theory, Part I, M.A.A. Studies in Mathematics, vol. 11 (1975), Math. Assoc. Amer.: Math. Assoc. Amer. Washington), 1-22
[11] Berge, C., Vers une theorie generale des jeux positionnels, (Henn, R.; Moeschlin, O., Mathematical Economics and Game Theory, Essays in honor of Oskar Morgenstern, Lecture Notes in Economics, vol. 141 (1977), Springer: Springer Berlin), 13-24 · Zbl 0349.90137
[12] C. Berge, Nouvelles extensions du noyau d’un graphe et ses applications et theorie des jeux, Publ. Econometriques 6, 1977.; C. Berge, Nouvelles extensions du noyau d’un graphe et ses applications et theorie des jeux, Publ. Econometriques 6, 1977. · Zbl 0257.05113
[13] Berge, C., Minimax theorems for normal hypergraphs and balanced hypergraphs—a survey, Ann. Discrete Math., 21, 3-19 (1984) · Zbl 0554.05052
[14] Berge, C., Graphes North-Holland Mathematical Library, vol. 6 (1985), North-Holland: North-Holland Amsterdam, (Chapter 14)
[15] Berge, C., Hypergraphs. Combinatorics of Finite Sets, North-Holland Mathematical Library (1989), North-Holland: North-Holland Amsterdam, New York, Oxford, Tokyo
[16] C. Berge, P. Duchet, Probleme, Seminaire MSH, Paris, January 1983.; C. Berge, P. Duchet, Probleme, Seminaire MSH, Paris, January 1983.
[17] Berge, C.; Duchet, P., Solvability of perfect graphs, Proceedings of the Burnside-Raspai meeting, Barbados, 1986 (1987), Mc Gill University: Mc Gill University Montreal
[18] C. Berge, P. Duchet, Recent problems and results about kernels in directed graphs, Applications of Discrete Mathematics (Clemson, SC, 1986), SIAM, Philadelphia, PA, 1988, pp. 200-204.; C. Berge, P. Duchet, Recent problems and results about kernels in directed graphs, Applications of Discrete Mathematics (Clemson, SC, 1986), SIAM, Philadelphia, PA, 1988, pp. 200-204. · Zbl 0669.05036
[19] Berge, C.; Duchet, P., Perfect graphs and kernels, Bull. Inst. Math. Acad. Sinica, 16, 263-274 (1988) · Zbl 0669.05037
[20] Berge, C.; Duchet, P., Recent problems and results about kernels in directed graphs, Discrete Math., 86, 27-31 (1990) · Zbl 0721.05027
[21] Berge, C.; Ramachandra Rao, A., A combinatorial problem in logic, Discrete Math., 17, 23-26 (1977) · Zbl 0352.05047
[22] M. Blidia, Contribution a l’etude des noyaux dans les graphes, Thesis, Paris, 1984.; M. Blidia, Contribution a l’etude des noyaux dans les graphes, Thesis, Paris, 1984.
[23] Blidia, M., A parity digraph has a kernel, Combinatorica, 6, 23-27 (1986) · Zbl 0599.05028
[24] Blidia, M.; Duchet, P.; Jacob, H.; Maffray, F.; Meyniel, H., Some operations preserving the existence of kernels, Discrete Math., 205, 211-216 (1999) · Zbl 0936.05047
[25] Blidia, M.; Duchet, P.; Maffray, F., On kernels in perfect graphs, Combinatorica, 13, 2, 231-233 (1993) · Zbl 0780.05020
[26] Blidia, M.; Duchet, P.; Maffray, F., On the orientation of Meyniel graphs, J. Graph Theory, 18, 7, 705-711 (1994) · Zbl 0809.05049
[27] Blidia, M.; Engel, K., Perfectly orderable graphs and almost all perfect graphs are kernel-\(M\)-solvable, Graph Combin., 8, 2, 103-108 (1992) · Zbl 0761.05090
[28] Bondareva, O. N., The core of \(n\)-person game, Vestnik Leningrad Univ., 17, 13, 141-142 (1962), (in Russian) · Zbl 0122.15404
[29] Bondareva, O. N., Some applications of linear programming methods to the theory of cooperative games, Problemy Kibernetiki (Problems of Cybernetics), 10, 119-139 (1963), (in Russian) · Zbl 1013.91501
[30] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., On kernel-perfect orientations of line graphs. Graph theory (Elgersburg, 1996), Discrete Math., 191, 1-3, 45-49 (1998) · Zbl 0955.05049
[31] Boros, E.; Gurvich, V., Perfect graphs are kernel-solvable, Discrete Math., 159, 35-55 (1996) · Zbl 0861.05053
[32] Boros, E.; Gurvich, V., A corrected version of the Duchet kernel conjecture, Discrete Math., 179, 231-233 (1998) · Zbl 0886.05089
[33] Boros, E.; Gurvich, V., Stable effectivity functions and perfect graphs, Math. Soc. Sci., 39, 175-194 (2000) · Zbl 0951.91011
[34] Boros, E.; Gurvich, V.; Vasin, A., Stable families of coalitions and normal hypergraphs, Math. Soc. Sci., 34, 107-123 (1997) · Zbl 0915.90277
[35] Bouton, C. L., Nim, a game with a complete mathematical theory, Ann. Math., 3, 2, 35-39 (1902) · JFM 32.0225.02
[36] Champetier, C., Kernels in some orientations of comparability graphs, J. Combin. Theory (Ser. B), 47, 1, 111-113 (1989) · Zbl 0681.05037
[37] Chilakamarri, K. B.; Hamburger, P., On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Math., 118, 1-3, 253-257 (1993) · Zbl 0782.05035
[38] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Math. Programming (Ser. B) 97 (2003) 405-422.; M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Math. Programming (Ser. B) 97 (2003) 405-422. · Zbl 1028.05035
[39] M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic, Recognizing Berge graphs, Combinatorica 25 (2) (2005) 143-186.; M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic, Recognizing Berge graphs, Combinatorica 25 (2) (2005) 143-186. · Zbl 1089.05027
[40] V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal, 1973.; V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal, 1973.
[41] Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory (Ser. B), 18, 138-154 (1975) · Zbl 0277.05139
[42] Chvátal, V.; Graham, R. L.; Perold, A. F.; Whitesides, S. H., Combinatorial designs related to the strong perfect graph conjecture, Discrete Math., 26, 83-92 (1979) · Zbl 0403.05017
[43] Chvátal, V.; Lovász, L., Every directed graph has a semi-kernel, (Berge, C.; Ray-Chaudhuri, D., Hypergraph Seminar, Lecture Notes in Mathematics (1974), Springer: Springer Berlin) · Zbl 0297.05116
[44] G. Cornuéjols, X. Liu, K. Vušković, A polynomial algorithm for recognizing perfect graphs, Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2003) 20-27.; G. Cornuéjols, X. Liu, K. Vušković, A polynomial algorithm for recognizing perfect graphs, Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2003) 20-27.
[45] Danilov, V. I.; Sotskov, A. I., The independent blocking in social choice mechanisms, Economica i mat. metody (Econom. Math. Methods), 23, 5, 888-898 (1987), (in Russian) · Zbl 0659.90006
[46] Danilov, V. I.; Sotskov, A. I., Mechanizmy gruppovogo vybora (in Russian) (1991), Nauka: Nauka Moscow, (English translation, Social Choice Mechanisms, ser. Studies in Economic Design, Springer, Berlin, 2002)
[47] Duchet, P., Graphes noyau-parfaits, Combinatorics 79 (Proceedings of the Colloquium, University of Montréal, Montreal, Que., 1979), Part II, Ann. Discrete Math., 9, 93-101 (1980)
[48] Duchet, P., Parity graphs are kernel-\(M\)-solvable, J. Combin. Theory (Ser. B), 43, 2, 121-126 (1987) · Zbl 0675.05063
[49] Duchet, P., A sufficient condition for a digraph to be kernel-perfect, J. Graph Theory, 11, 1, 81-85 (1987) · Zbl 0607.05036
[50] Duchet, P.; Meyniel, H., A note on kernel-critical graphs, Discrete Math., 33, 103-105 (1981) · Zbl 0456.05032
[51] Duchet, P.; Meyniel, H., Une jeneralization du theoreme de Richardson sur l’existence de noyaux dans les graphes orientes, Discrete Math., 43, 1, 21-27 (1983) · Zbl 0502.05027
[52] Duchet, P.; Meyniel, H., Kernels in directed graphs: a poison game, Discrete Math., 115, 1-3, 273-276 (1993) · Zbl 0773.05052
[53] Duchet, P.; Olariu, S., Graphes parfaitement ordonnables généralisés, Discrete Math., 90, 1, 99-101 (1991) · Zbl 0743.05043
[54] Erdös, P., Some old and new problems in various branches of combinatorics, Congr. Numer., 23, 19-37 (1979)
[55] T. Fleiner, Stable and crossing structures, Ph.D. Thesis, Alfred Renyi Mathematical Institute of the Hungarian Academy of Sciences, 2000.; T. Fleiner, Stable and crossing structures, Ph.D. Thesis, Alfred Renyi Mathematical Institute of the Hungarian Academy of Sciences, 2000. · Zbl 0966.91007
[56] Fraenkel, A. S., Planar kernel and Grundy with \(d \leqslant 3, d_{\operatorname{out}} \leqslant 2, d_{\operatorname{in}} \leqslant 2\) are NP-complete, Discrete Appl. Math., 3, 257-262 (1981)
[57] Fulkerson, D. R., Anti-blocking polyhedra, J. Combin. Theory (Ser. B), 12, 50-71 (1972) · Zbl 0227.05015
[58] Gale, D.; Shapley, L. S., College admissions and stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) · Zbl 0109.24403
[59] Galeana-Sánchez, H., A counterexample to a conjecture by Meyniel on kernel-perfect graphs, Discrete Math., 41, 105-107 (1982) · Zbl 0484.05035
[60] Galeana-Sánchez, H., A theorem about a conjecture of H. Meyniel on kernel-perfect graphs, Discrete Math., 59, 1-2, 35-41 (1986) · Zbl 0602.05032
[61] Galeana-Sánchez, H., A new method to extend kernel-perfect graphs to kernel-perfect critical graphs, Discrete Math., 69, 2, 207-209 (1988) · Zbl 0675.05033
[62] Galeana-Sánchez, H., Normal fraternally orientable graphs satisfy the strong perfect graph conjecture, Discrete Math., 122, 1-3, 167-177 (1993) · Zbl 0791.05046
[63] Galeana-Sánchez, H., A characterization of normal fraternally orientable perfect graphs, Discrete Math., 169, 1-3, 221-225 (1997) · Zbl 0884.05079
[64] Galeana-Sánchez, H.; García-Ruvalcaba, J., Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory, 20, 2, 243-254 (2000) · Zbl 0990.05059
[65] Galeana-Sánchez, H.; García-Ruvalcaba, J., On graphs all of whose \(\{C_3, T_3 \}\)-free arc colorations are kernel-perfect, Discuss. Math. Graph Theory, 21, 1, 77-93 (2001) · Zbl 0990.05060
[66] Galeana-Sánchez, H.; Neumann-Lara, V., On kernels and semikernels of digraphs, Discrete Math., 48, 1, 67-76 (1984) · Zbl 0529.05024
[67] Galeana-Sánchez, H.; Neumann-Lara, V., On kernel-perfect critical digraphs, Discrete Math., 59, 3, 257-265 (1986) · Zbl 0593.05034
[68] Galeana-Sánchez, H.; Neumann-Lara, V., Orientations of graphs in kernel theory, Discrete Math., 87, 3, 271-280 (1991) · Zbl 0732.05044
[69] Galeana-Sánchez, H.; Neumann-Lara, V., Extending kernel perfect digraphs to kernel perfect critical digraphs, Discrete Math., 94, 3, 181-187 (1991) · Zbl 0748.05060
[70] Galeana-Sánchez, H.; Neumann-Lara, V., New extensions of kernel perfect digraphs to kernel imperfect critical digraphs, Graphs Combin., 10, 4, 329-336 (1994) · Zbl 0811.05027
[71] Galeana-Sánchez, H.; Neumann-Lara, V., KP-digraphs and CKI-digraphs satisfying the \(k\)-Meyniel’s condition, Discuss. Math. Graph Theory, 16, 1, 5-16 (1996) · Zbl 0865.05046
[72] Galeana-Sánchez, H.; Neumann-Lara, V., On the dichromatic number in kernel theory, Math. Slovaca, 48, 3, 213-219 (1998) · Zbl 0937.05048
[73] Galvin, F., The list chromatic index of a bipartite graph, J. Combin. Theory (Ser. B), 63, 153-158 (1995) · Zbl 0826.05026
[74] Gavril, F.; Toledano, V.; de Werra, D., Chordless paths, odd holes, and kernels in graphs without \(m\)-obstructions, J. Algorithms, 17, 2, 207-221 (1994) · Zbl 0807.05035
[75] Gavril, F.; Urrutia, J., An algorithm for fraternal orientation of graphs, Inform. Process. Lett., 41, 271-274 (1992) · Zbl 0764.68135
[76] Gurvich, V., Some properties of effectivity functions (in Russian), Doklady Akad. Nauk SSSR,, 307, 6, 1311-1317 (1989), (English transl. in Soviet Math. Dokl. 40(1) (1990) 244-250)
[77] Gurvich, V., Algebraic properties of effectivity functions (in Russian), Dokl. Akad. Nauk., 323, 1, 19-24 (1992), (English transl. in Soviet Math. Dokl. 45(2) (1992) 245-251)
[78] V. Gurvich, Effectivity functions and informational extensions of game forms and game correspondences (in Russian), Uspehi Mat. Nauk 47(6) (1992) (288) 209-210 (English translation in Russian Mathematical Surveys 47(6) (1992) 208-209).; V. Gurvich, Effectivity functions and informational extensions of game forms and game correspondences (in Russian), Uspehi Mat. Nauk 47(6) (1992) (288) 209-210 (English translation in Russian Mathematical Surveys 47(6) (1992) 208-209).
[79] V. Gurvich, Dual cores and effectivity functions; criteria of nonemptyness for dual cores (in Russian), Dokl. Acad. Nauk. 352 (1-2) (1997) (English translation in Doklady Mathematics 55(1) (1997) 12-16 and 33-37).; V. Gurvich, Dual cores and effectivity functions; criteria of nonemptyness for dual cores (in Russian), Dokl. Acad. Nauk. 352 (1-2) (1997) (English translation in Doklady Mathematics 55(1) (1997) 12-16 and 33-37).
[80] V.A. Gurvich, A.A. Vasin, Reconcilable sets of coalitions, in: Questions of Applied Math. Siberian Energetic Institute, Irkutsk, 1977, pp. 20-30 (in Russian).; V.A. Gurvich, A.A. Vasin, Reconcilable sets of coalitions, in: Questions of Applied Math. Siberian Energetic Institute, Irkutsk, 1977, pp. 20-30 (in Russian). · Zbl 0465.90094
[81] V.A. Gurvich, A.A. Vasin, Reconcilable sets of coalitions for normal form games, in: Numerical Methods in Optimization Theory (Applied Math.), Siberian Energetic Institute, Irkutsk, 1978, pp. 27-38 (in Russian).; V.A. Gurvich, A.A. Vasin, Reconcilable sets of coalitions for normal form games, in: Numerical Methods in Optimization Theory (Applied Math.), Siberian Energetic Institute, Irkutsk, 1978, pp. 27-38 (in Russian). · Zbl 0463.90098
[82] Harary, F.; Norman, R. Z.; Cartwright, D., Structural Models (1965), Wiley: Wiley NY · Zbl 0139.41503
[83] Huang, Y., Kernels in a special class of digraphs, J. Xinjiang Univ. Natur. Sci., 16, 4, 23-26 (1999) · Zbl 1056.05506
[84] Huang, Y.; Guo, X., On a class of kernel-perfect and kernel-perfect-critical graphs, J. Xinjiang Univ. Natur. Sci., 16, 3, 1-9 (1999) · Zbl 1056.05507
[85] H. Jacob, Etude theorique du noyau d’un graphe, Thesis, Paris 6, 1979.; H. Jacob, Etude theorique du noyau d’un graphe, Thesis, Paris 6, 1979.
[86] Jacob, H.; Meyniel, H., About quasi-kernels in a digraph, Discrete Math., 154, 279-280 (1996) · Zbl 0854.05055
[87] Kaneko, M.; Wooders, M. H., Cores of partitioning games, Math. Soc. Sci., 3, 313-327 (1982) · Zbl 0493.90089
[88] Keiding, H., Necessary and sufficient conditions for stability of effectivity functions, Internat. J. Game Theory, 14, 93-101 (1985) · Zbl 0567.90101
[89] J. Kuipers, Combinatorial methods in cooperative game theory, Thesis, Maastricht University, 1994.; J. Kuipers, Combinatorial methods in cooperative game theory, Thesis, Maastricht University, 1994.
[90] Le Breton, M.; Owen, G.; Weber, S., Strongly balanced cooperative games, Internat. J. Game Theory, 21, 419-427 (1992) · Zbl 0763.90103
[91] Lovász, L., Normal hypergraphs and the weak perfect graph conjecture, Discrete Math., 2, 3, 253-267 (1972) · Zbl 0239.05111
[92] Lovász, L., A characterization of perfect graphs, J. Combin. Theory (Ser. B), 13, 2, 95-98 (1972) · Zbl 0241.05107
[93] F. Maffray, Sur l’existence des noyaux dans les graphes parfaits, Thesis, Paris VI, 1984.; F. Maffray, Sur l’existence des noyaux dans les graphes parfaits, Thesis, Paris VI, 1984.
[94] Maffray, F., On kernels in \(i\)-triangulated graphs, Discrete Math., 61, 2-3, 247-251 (1986) · Zbl 0617.05029
[95] Maffray, F., Kernels in perfect line-graphs, J. Combin. Theory (Ser. B), 55, 1, 1-8 (1992) · Zbl 0694.05054
[96] Meyniel, H., The graphs whose odd cycles have at least two chords, (Berge, C.; Chvátal, V., Topics on Perfect Graphs, Mathematical Studies, vol. 88 (1984)), 115-120 · Zbl 0567.05034
[97] Moulin, H., The strategy of social choice, Advanced Textbooks in Economics, vol. 18 (1983), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam, New York, Oxford · Zbl 0543.90002
[98] Moulin, H.; Peleg, B., Cores of effectivity functions and implementation theory, J. Math. Econom., 10, 115-145 (1982) · Zbl 0481.90004
[99] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton University Press: Princeton University Press Princeton, NJ, 1947, 1953 · Zbl 0063.05930
[100] Nowakowski, R. J., Games of no chance, Combinatorial games at MSRI, 1994, Mathematical Sciences Research Institute Publications, vol. 29 (1996), Cambridge University Press: Cambridge University Press Cambridge
[101] Olaru, E., Betrage zur Theorie der perfecten Graphen, Elektron. Inform. Kybernetik (EIK), 8, 147-172 (1972) · Zbl 0242.05126
[102] E. Olaru, H. Sachs, Contributions to a characterization of the structure of perfect graphs, in: C. Berge, V. Chvátal (Eds.), Topics on Perfect Graphs, Ann. Discrete Math. 21 (1984) 121-144.; E. Olaru, H. Sachs, Contributions to a characterization of the structure of perfect graphs, in: C. Berge, V. Chvátal (Eds.), Topics on Perfect Graphs, Ann. Discrete Math. 21 (1984) 121-144. · Zbl 0559.05054
[103] Padberg, M. W., Perfect zero-one matrices, Math. Programming, 6, 180-196 (1974) · Zbl 0284.90061
[104] Peleg, B., An inductive method for constructing minimal balanced collections of finite sets, Naval Res. Logistics Quart., 12, 155-162 (1965) · Zbl 0137.38604
[105] B. Peleg, Game Theoretic Analysis of Voting in Committees. Econometric Society Publication, vol. 7, Cambridge University Press, Cambridge, London, New York, New Rochelle, Melburn, Sydney, 1984.; B. Peleg, Game Theoretic Analysis of Voting in Committees. Econometric Society Publication, vol. 7, Cambridge University Press, Cambridge, London, New York, New Rochelle, Melburn, Sydney, 1984. · Zbl 0563.90002
[106] Peleg, B., Core stability and duality of effectivity functions, (Hammer, G.; Pallaschke, D., Selected topics in operations research and mathematical economics (1984), Springer: Springer Berlin), 272-287
[107] Preissmann, M.; Sebő, A., Some aspects of minimal imperfect graphs, (Ramirez Alfonsin, J. L.; Reed, B., Perfect Graphs (2001), Wiley: Wiley New York), 185-214 · Zbl 0990.05055
[108] Richardson, M., Solutions of irreflexible relations, Ann. Math., 58, 573-590 (1953) · Zbl 0053.02902
[109] Scarf, H., The core of \(n\) person game, Econometrica, 35, 1, 50-59 (1967) · Zbl 0183.24003
[110] Shapley, L. S., On balanced sets and cores, RAND corporation, RM-4601-PR, 1965, Naval Res. Logist. Quart., 14, 453-460 (1967)
[111] Skrien, D. J., A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular arc graphs, and nested interval graphs, J. Graph Theory, 6, 309-316 (1982) · Zbl 0495.05027
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.