zbMATH — the first resource for mathematics

Maximum bipartite subgraphs of Kneser graphs. (English) Zbl 0674.05064
Summary: We investigate the maximum number of edges in a bipartite subgraph of the Kneser graph K(n,r). The exact solution is given for either r arbitrary and \(n\leq (4.3+o(1))r,\) or \(r=2\) and n arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.

05C99 Graph theory
05A05 Permutations, words, matrices
Full Text: DOI
[1] Ahlswede, R., Katona, G.O.H.: Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hung.32, 97–120 (1978) · Zbl 0386.05036 · doi:10.1007/BF01902206
[2] Barahona, F., Grötschel, M., Mahjoub, F.: Facets of the bipartite subgraph polytope. Math. Oper. Res.10, 340–358 (1985) · Zbl 0578.05056 · doi:10.1287/moor.10.2.340
[3] Barahona, F.: On the complexity of Max-Cut. In: Rapport de Recherche No. 186 IMAG, Universite Scientifique et Medicale de Grenoble 1980
[4] Bárány, I.: A short proof of Kneser’s conjecture. J. Comb. Theory (A)25, 325–326 (1976) · Zbl 0404.05028 · doi:10.1016/0097-3165(78)90023-7
[5] Frankl P., Füredi, Z.: Nontrivial intersecting families. J. Comb. Theory (A)41, 150–153 (1986) · Zbl 0583.05002 · doi:10.1016/0097-3165(86)90121-4
[6] Garey, M.R., Johnson, D.S.: The complexity of near optimal graph colouring. J. Assoc. Comput. Math.23, 43–49 (1976) · Zbl 0322.05111
[7] Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-completeness. San Francisco: Freeman 1979 · Zbl 0411.68039
[8] Kneser, M.: Aufgabe 300. Jahresber. Dtsch. Math. -Ver.58, (1955)
[9] Lehel, J., Tuza, Zs.: Triangle-free partial graphs and edge covering theorems. Discrete Math.39, 59–65 (1982) · Zbl 0499.05026 · doi:10.1016/0012-365X(82)90040-1
[10] Lovász, L.: Kneser’s conjecture, chromatic number and homotopy. J. Comb. Theory (A)25, 319–324 (1978) · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5
[11] Poljak, S., Turzik, D.: On the structure of bipartite subgraphs ofr-chordal graphs (to appear) · Zbl 0471.68041
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.