Clique versus independent set
From MaRDI portal
Publication:402465
DOI10.1016/j.ejc.2014.02.003zbMath1297.05173arXiv1301.2474OpenAlexW1990565272MaRDI QIDQ402465
Steéphan Thomassé, Aurélie Lagoutte, Nicolas Bousquet
Publication date: 28 August 2014
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1301.2474
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (8)
Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Some improved bounds on communication complexity via new decomposition of cliques ⋮ Excluding hooks and their complements ⋮ On the binary and Boolean rank of regular matrices ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Extended formulations from communication protocols in output-efficient time ⋮ Communication Complexity of Pairs of Graph Families with Applications ⋮ Ordered biclique partitions and communication complexity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- \(\epsilon\)-nets and simplex range queries
- Bounds of neighborly families of convex polytopes
- Expressing combinatorial optimization problems by linear programs
- The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
- Stable sets and polynomials
- Variations on a theme of Graham and Pollak
- The Erdős-Hajnal conjecture for paths and antipaths
- The Complexity of the List Partition Problem for Graphs
- Adapted List Coloring of Graphs and Hypergraphs
- On the decomposition ofkn into complete bipartite graphs
- List Partitions
- Bi‐arc graphs and the complexity of list homomorphisms
- Communication Complexity
- Linear vs. semidefinite extended formulations
- Full Constraint Satisfaction Problems
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Clique versus independent set
