Maximum bipartite subgraphs of Kneser graphs

DOI10.1007/BF01788540zbMath0674.05064MaRDI QIDQ1121290

Svatopluk Poljak, Zsolt Tuza

Publication date: 1987

Published in: Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

exact solutionKneser graphmaximum number of edgesbipartite subgraphpolytope of a graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (05C99)

Related Items

Unnamed Item, Extensions of Fractional Precolorings Show Discontinuous Behavior, Large cycles in generalized Johnson graphs, Towards the Chen-Raspaud conjecture, A note on induced cycles in Kneser graphs, \(L(1,1)\)-labelling of the direct product of a complete graph and a cycle, The minimum number of disjoint pairs in set systems and related problems, Max-cut in circulant graphs, First-order complexity of subgraph isomorphism via Kneser graphs, Long induced paths and cycles in Kneser graphs, Häggkvist-Hell graphs: A class of Kneser-colorable graphs, Fractional covering by cuts

Cites Work

• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• Non-trivial intersecting families
• Triangle-free partial graphs and edge covering theorems
• A short proof of Kneser's conjecture
• Facets of the Bipartite Subgraph Polytope
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• The Complexity of Near-Optimal Graph Coloring
• Graphs with maximal number of adjacent pairs of edges