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

DOI10.1007/s00493-012-2746-4zbMath1299.05123arXiv1002.4687OpenAlexW2080740807WikidataQ123333206 ScholiaQ123333206MaRDI QIDQ452825

Hao Huang, Benjamin Sudakov

Publication date: 17 September 2012

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

counterexamplebipartite graphschromatic numbercommunication complexityAlon-Saks-Seymour conjecturedisjoint union

Mathematics Subject Classification ID

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

Related Items

Regarding two conjectures on clique and biclique partitions, Eigenvalues of Cayley graphs, Some improved bounds on communication complexity via new decomposition of cliques, Unnamed Item, New bounds on the maximum number of neighborly boxes in \(\mathbb{R}^d\), Clique versus independent set, Graph and hypergraph colouring via nibble methods: a survey, A proof of the Erdős-Faber-Lovász conjecture, Problems close to my heart, On the binary and Boolean rank of regular matrices, Exact values and improved bounds on \(k\)-neighborly families of boxes, Decomposition techniques applied to the clique-stable set separation problem, Coloring temporal graphs, Multicovering hypergraphs, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Communication Complexity of Pairs of Graph Families with Applications, Ordered biclique partitions and communication complexity problems

Uses Software

• GRAFFITI

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of a theorem of Graham and Pollak
• The linear-array conjecture in communication complexity is false
• Bounds of neighborly families of convex polytopes
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• 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
• Communication complexity and combinatorial lattice theory
• On rank vs. communication complexity
• On the ``log rank-conjecture in communication complexity
• Bipartite coverings and the chromatic number
• A polynomial space proof of the Graham-Pollak theorem
• A counterexample to the rank-coloring conjecture
• On the decomposition ofkn into complete bipartite graphs
• Communication Complexity