More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
type: Item
instance of: scholarly article
title: More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
zbMATH Open document ID: 1215.05059
author: Sebastian Cioaba
author: Michael Tait
published in: The Electronic Journal of Combinatorics
publication date: 2011-02-17T00:00:00Z
full work available at URL: https://eudml.org/doc/231767
full work available at URL: v18i1p26.html
review text: The Rank-Coloring Conjecture states that the chromatic number \(\chi(G) \leq rank(A(G))\), the rank of the adjacency matrix of the graph \(G\). The Alon, Saks, and Seymour Conjecture states that \(\chi(G) \leq bp(G) + 1\), where \(bp(G)\) is the complete bipartite partition number for the graph \(G\). Using a family of graphs \(G(n, k, r)\), which are patterned after \(n\)-dimensional cube \(Q_n\), they give counterexamples to each of the previously mentioned Conjectures.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A18
zbMATH DE Number: 5852476
zbMATH Keywords: chromatic number
zbMATH Keywords: rank coloring
zbMATH Keywords: biclique partition number
reviewed by: Ralph Faudree
MaRDI profile type: Publication
Recommended article: Q3989474
Recommended article: A counterexample to the rank-coloring conjecture
Recommended article: A counterexample to the Alon-Saks-Seymour conjecture and related problems
Recommended article: Q5461529
Recommended article: Counterexamples to a conjecture on injective colorings
Recommended article: The Schur-Erdős problem for semi-algebraic colorings
Recommended article: A counterexample to a 𝐵𝑃-analogue of the chromatic splitting conjecture
Recommended article: Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
Recommended article: A counterexample to montgomery's conjecture on dynamic colourings of regular graphs
Recommended article: Q5046003
description: scientific article; zbMATH DE number 5852476