The Maximum k-Colorable Subgraph Problem and Related Problems

References

• Addario-Berry L, Kennedy W, King AD, Li Z, Reed B (2010) Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph. Discrete Appl. Math. 158(7):765–770.Crossref, Google Scholar
• Alizadeh F (1995) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1):13–51.Crossref, Google Scholar
• Bentert M, van Bevern R, Niedermeier R (2019) Inductive k-independent graphs and c-colorable subgraphs in scheduling: A review. J. Scheduling 22:3–20.Crossref, Google Scholar
• Bresar B, Valencia-Pabon M (2019) Independence number of products of Kneser graphs. Discrete Math. 342(4):1017–1027.Crossref, Google Scholar
• Brouwer A, Shearer J, Sloane N, Smith W (1990) A new table of constant weight codes. IEEE Trans. Inform. Theory 36(6):1334–1380.Crossref, Google Scholar
• Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479–495.Crossref, Google Scholar
• Campêlo M, Corrêa RC (2010) A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems. Electronic Notes Discrete Math. 36:503–510.Crossref, Google Scholar
• de Klerk E, Sotirov R (2008) Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Programming 122(2):225–246.Crossref, Google Scholar
• de Klerk E, Pasechnik D, Warners J (2004) On approximate graph colouring and MAX-k-CUT algorithms based on the θ-function. J. Combin. Optim. 8(3):267–294.Crossref, Google Scholar
• Delorme C, Poljak S (1993) Laplacian eigenvalues and the maximum cut problem. Math. Programming 62(1):557–574.Crossref, Google Scholar
• Delsarte P (1973) An algebraic approach to the association schemes of coding theory. Philips Research Reports Supplements No. 10, Phillips Research Laboratories, Eindhoven, Netherlands.Google Scholar
• Ding Y, Ge D, Wolkowicz H (2011) On equivalence of semidefinite relaxations for quadratic matrix programming. Math. Oper. Res. 36(1):88–104.Link, Google Scholar
• Erdős P, Ko C, Rado R (1961) Intersection theorem for system of finite sets. Quart. J. Math. 12(1):313–318.Crossref, Google Scholar
• Etzion T, Bitan S (1996) On the chromatic number, colorings, and codes of the Johnson graph. Discrete Appl. Math. 70(2):163–175.Crossref, Google Scholar
• Fan K (1949) On a theorem of Weyl concerning eigenvalues of linear transformations I. Proc. Natl. Acad. Sci. USA 35(11):652–655.Crossref, Google Scholar
• Fouilhoux P, Mahjoub AR (2006) Polyhedral results for the bipartite induced subgraph problem. Discrete Appl. Math. 154(15):2128–2149.Crossref, Google Scholar
• Fouilhoux P, Mahjoub AR (2012) Solving VLSI design and DNA sequencing problems using bipartization of graphs. Comput. Optim. Appl. 51(2):749–781.Crossref, Google Scholar
• Frieze A, Jerrum M (1995) Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Balas E, Clausen J, eds., Integer Programming and Combinatorial Optimization (Springer, Berlin), 1–13.Crossref, Google Scholar
• Füredi Z (1983) An extremal problem concerning Kneser’s conjecture. Studia Sci. Math. Hungarica 18:335–341.Google Scholar
• Gatermann K, Parrilo P (2004) Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1–3):95–128.Crossref, Google Scholar
• Godsil C, Royle G (2001) Algebraic Graph Theory (Springer, Berlin).Crossref, Google Scholar
• Goemans MX, Williamson DP (1994) .879 approximation algorithms for MAX CUT and MAX 2SAT. Proc. 26th Annual ACM Sympos. Theory Comput. (ACM, New York), 422–431.Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Crossref, Google Scholar
• Gvozdenović N, Laurent M (2008) The operator ψ for the chromatic number of a graph. SIAM J. Optim. 19(2):572–591.Crossref, Google Scholar
• Halldórsson MM, Halpern JY, Li LE, Mirrokni VS (2004) On spectrum sharing games. Proc. 23rd Annual ACM Sympos. Principles Distributed Comput. (ACM, New York), 107–114.Google Scholar
• Hertz A, Montagné R, Gagnon F (2016) Constructive algorithms for the partial directed weighted improper coloring problem. J. Graph Algorithms Appl. 20(2):159–188.Crossref, Google Scholar
• Hertz A, Montagné R, Gagnon F (2018) Online algorithms for the maximum k-colorable subgraph problem. Comput. Oper. Res. 91:209–224.Crossref, Google Scholar
• Hüffner F (2005) Algorithm engineering for optimal graph bipartization. Nikoletseas SE, ed. Experimental and Efficient Algorithms (Springer, Berlin), 240–252.Crossref, Google Scholar
• Januschowski T, Pfetsch ME (2011a) Branch-cut-and-propagate for the maximum k-colorable subgraph problem with symmetry. Achterberg T, Beck JC, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin), 99–116.Crossref, Google Scholar
• Januschowski T, Pfetsch ME (2011b) The maximum k-colorable subgraph problem and orbitopes. Discrete Optim. 8(3):478–494.Crossref, Google Scholar
• Karisch SE, Rendl F (1998) Semidefinite programming and graph equipartition. Pardalos PM, Wolkowicz H, eds. Topics in Semidefinite and Interior-Point Methods (American Mathematical Society, Providence, RI), 77–95.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations (Springer, Boston), 85–103.Crossref, Google Scholar
• Koster A, Scheffel M (2007) A routing and network dimensioning strategy to reduce wavelength continuity conflicts in all-optical networks. Proc. INOC 2007, Internat. Network Optim. Conf., Spa, Belgium, April 22–25.Google Scholar
• Lee K, Funabiki N, Takefuji Y (1992) A parallel improvement algorithm for the bipartite subgraph problem. IEEE Trans. Neural Networks 3(1):139–145.Crossref, Google Scholar
• Lewis J, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci. 20(2):219–230.Crossref, Google Scholar
• Lippert R, Schwartz R, Lancia G, Istrail S (2002) Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Brief Bioinform. 3(1):23–31.Crossref, Google Scholar
• Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1):1–7.Crossref, Google Scholar
• Lund C, Yannakakis M (1993) The approximation of maximum subgraph problems. Lingas A, Karlsson R, Carlsson S, eds. Automata, Languages and Programming (Springer, Berlin), 40–51.Crossref, Google Scholar
• Marek-Sadowska M (1984) An unconstrained topological via minimization problem for two-layer routing. IEEE Trans. Comput. Aided Des. Integrated Circuits Systems 3(3):184–190.Crossref, Google Scholar
• Mohar B, Poljak S (1993) Eigenvalues in combinatorial optimization. Brualdi RA, Friedland S, Klee V, eds. Combinatorial and Graph-Theoretical Problems in Linear Algebra (Springer, New York), 107–151.Crossref, Google Scholar
• Narasimhan G (1989) The maximum k-colorable subgraph problem. Unpublished doctoral dissertation, University of Wisconsin–Madison.Google Scholar
• Narasimhan G, Manber R (1990) A generalization of Lovász’s ϑ function. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 19–27.Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1):139–172.Crossref, Google Scholar
• Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3):425–440.Crossref, Google Scholar
• Rendl F (2016) Semidefinite relaxations for partitioning, assignment and ordering problems. Ann. Oper. Res. 240:119–140.Crossref, Google Scholar
• Rendl F, Sotirov R (2018) The min-cut and vertex separator problem. Comput. Optim. Appl. 69(1):159–187.Crossref, Google Scholar
• Rendl F, Sotirov R, Truden C (2019) Lower bounds for the bandwidth problem. Preprint, submitted April 14, https://arxiv.org/abs/1904.06715.Google Scholar
• Sabidussi G (1957) Graphs with given group and given graph-theoretical properties. Canadian J. Math. 9:515–525.Crossref, Google Scholar
• Schrijver A (1979) A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inform. Theory 25(4):425–429.Crossref, Google Scholar
• Sherali HD, Adams WP (1994) A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52(1):83–106.Crossref, Google Scholar
• Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos M, Lasserre J, eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications (Springer, New York), 795–820.Crossref, Google Scholar
• Sotirov R (2014) An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J. Comput. 26(1):16–30.Link, Google Scholar
• Subramanian AP, Gupta H, Das SR, Buddhikot MM (2007) Fast spectrum allocation in coordinated dynamic spectrum access based cellular networks. Proc. 2nd IEEE Internat. Sympos. New Frontiers Dynam. Spectrum Access Networks (IEEE, Piscataway, NJ), 320–330.Google Scholar
• van Dam E, Sotirov R (2016) New bounds for the max-k-cut and chromatic number of a graph. Linear Algebra Appl. 488:216–234.Crossref, Google Scholar
• van Dam ER, Sotirov R (2015) Semidefinite programming and eigenvalue bounds for the graph partition problem. Math. Programming 151(2):379–404.Crossref, Google Scholar
• Wolkowicz H, Zhao Q (1999) Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97:461–479.Crossref, Google Scholar
• Yannakakis M, Gavril F (1987) The maximum k-colorable subgraph problem for chordal graphs. Inform. Processing Lett. 24(2):133–137.Crossref, Google Scholar