Submodular Functions and Perfect Graphs

References

• [1] Abrishami T, Chudnovsky M, Dibek C, Hajebi S, Rzqżewski P, Spirkl S, Vušković K (2024) Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree. J. Combin. Theory Ser. B 164:371–403.Crossref, Google Scholar
• [2] Beck A (2014) Introduction to Nonlinear Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [3] Chudnovsky M, Robertson N, Seymour P, Thomas R (2006) The strong perfect graph theorem. Ann. Math. 164(1):51–229.Crossref, Google Scholar
• [4] Chudnovsky M, Trotignon N, Trunck T, Vušković K (2015) Coloring perfect graphs with no balanced skew-partitions. J. Combin. Theory Ser. B 115:26–65.Crossref, Google Scholar
• [5] Chudnovsky M, Liu C, Schaudt O, Spirkl S, Trotignon N, Vušković K (2019) Triangle free graphs that do not contain an induced subdivision of K4 are 3-colorable. J. Graph Theory 92(2):67–95.Crossref, Google Scholar
• [6] Conforti M, Cornuéjols G, Vušković K (2004) Square-free perfect graphs. J. Combin. Theory Ser. B 90(2):257–307.Crossref, Google Scholar
• [7] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:169–197.Crossref, Google Scholar
• [8] Harvey DJ, Wood DR (2017) Parameters tied to treewidth. J. Graph Theory 84(4):364–385.Crossref, Google Scholar
• [9] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [10] Lovász L (1983) Submodular functions and convexity. Bachem A, Grötschel M, Korte B, eds. Mathematical Programming – The State of the Art (Bonn, 1982) (Springer-Verlag, Berlin), 234–257.Crossref, Google Scholar
• [11] Marczewski E (1930) Sur l’extension de l’ordre partiel. Fund. Math. 16(1):386–389.Google Scholar
• [12] McCormick ST (2005) Submodular function minimization. Aardal K, Nemhauser GL, Weismantel R, eds. Discrete Optimization. Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, Amsterdam), 321–391.Crossref, Google Scholar
• [13] Olariu S (1988) Paw-free graphs. Inform. Processing Lett. 28(1):53–54.Crossref, Google Scholar
• [14] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118:237–251.Crossref, Google Scholar
• [15] Robertson N, Seymour PD (1991) Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52(2):153–190.Crossref, Google Scholar
• [16] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar