A counterexample to the Alon-Saks-Seymour conjecture and related problems
From MaRDI portal
(Redirected from Publication:452825)
Abstract: Consider a graph obtained by taking edge disjoint union of complete bipartite graphs. Alon, Saks and Seymour conjectured that such graph has chromatic number at most . This well known conjecture remained open for almost twenty years. In this paper, we construct a counterexample to this conjecture and discuss several related problems in combinatorial geometry and communication complexity.
Recommendations
Cites work
- scientific article; zbMATH DE number 4173028 (Why is no real title available?)
- scientific article; zbMATH DE number 736299 (Why is no real title available?)
- scientific article; zbMATH DE number 970791 (Why is no real title available?)
- A counterexample to the rank-coloring conjecture
- A new proof of a theorem of Graham and Pollak
- A polynomial space proof of the Graham-Pollak theorem
- Bipartite coverings and the chromatic number
- Bipartite edge partitions and the former Alon-Saks-Seymour conjecture
- Bounds of neighborly families of convex polytopes
- Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
- Communication Complexity
- Communication complexity and combinatorial lattice theory
- Expressing combinatorial optimization problems by linear programs
- On rank vs. communication complexity
- On the ``log rank-conjecture in communication complexity
- On the decomposition ofkn into complete bipartite graphs
- The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
- The linear-array conjecture in communication complexity is false
Cited in
(22)- New bounds on the maximum number of neighborly boxes in \(\mathbb{R}^d\)
- Ordered biclique partitions and communication complexity problems
- Communication complexity of pairs of graph families with applications
- Clique versus independent set
- Some improved bounds on communication complexity via new decomposition of cliques
- Exponential lower bounds for polytopes in combinatorial optimization
- Regarding two conjectures on clique and biclique partitions
- Eigenvalues of Cayley graphs
- Variations on a theme of Graham and Pollak
- scientific article; zbMATH DE number 2188427 (Why is no real title available?)
- Coloring temporal graphs
- More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
- Exact values and improved bounds on \(k\)-neighborly families of boxes
- Graph and hypergraph colouring via nibble methods: a survey
- A counterexample to a conjecture on the connectivity of \(0\)-\(1\) polytope graphs
- A proof of the Erdős-Faber-Lovász conjecture
- Problems and invariants connected with bicliques and multicliques of graphs
- Bipartite edge partitions and the former Alon-Saks-Seymour conjecture
- On the binary and Boolean rank of regular matrices
- Multicovering hypergraphs
- Problems close to my heart
- Decomposition techniques applied to the clique-stable set separation problem
This page was built for publication: A counterexample to the Alon-Saks-Seymour conjecture and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452825)
