More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures (Q625392)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5852476
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures |
scientific article; zbMATH DE number 5852476 |
Statements
More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures (English)
0 references
17 February 2011
0 references
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.
0 references
chromatic number
0 references
rank coloring
0 references
biclique partition number
0 references
0.91889906
0 references
0.90922296
0 references
0.88006747
0 references
0.85662305
0 references
0.85416055
0 references
0 references
0.8513266
0 references
