A counterexample to the Alon-Saks-Seymour conjecture and related problems

DOI10.1007/S00493-012-2746-4zbMATH Open1299.05123arXiv1002.4687OpenAlexW2080740807WikidataQ123333206 ScholiaQ123333206MaRDI QIDQ452825FDOQ452825

Authors: Hao Huang, Benny Sudakov 

Publication date: 17 September 2012

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs. Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$. 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.

Full work available at URL: https://arxiv.org/abs/1002.4687

Recommendations

• More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
• Bipartite edge partitions and the former Alon-Saks-Seymour conjecture
• scientific article; zbMATH DE number 2188427
• A counterexample to the rank-coloring conjecture
• Variations on a theme of Graham and Pollak

zbMATH Keywords

chromatic numbercounterexamplebipartite graphscommunication complexityAlon-Saks-Seymour conjecturedisjoint union

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Expressing combinatorial optimization problems by linear programs
• Title not available (Why is that?)
• Communication Complexity
• Title not available (Why is that?)
• Bounds of neighborly families of convex polytopes
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• On the decomposition ofkn into complete bipartite graphs
• Title not available (Why is that?)
• Bipartite coverings and the chromatic number
• Communication complexity and combinatorial lattice theory
• On rank vs. communication complexity
• The linear-array conjecture in communication complexity is false
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• On the ``log rank-conjecture in communication complexity
• A polynomial space proof of the Graham-Pollak theorem
• A counterexample to the rank-coloring conjecture
• Bipartite edge partitions and the former Alon-Saks-Seymour conjecture
• A new proof of a theorem of Graham and Pollak

Cited In (22)

• Communication complexity of pairs of graph families with applications
• Ordered biclique partitions and communication complexity problems
• 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
• Title not available (Why is that?)
• 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
• New bounds on the maximum number of neighborly boxes in \(\mathbb{R}^d\)

Uses Software

• GRAFFITI

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)