More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures (Q625392): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q175582 |
||
| Property / reviewed by | |||
| Property / reviewed by: Ralph J. Faudree / rank | |||
Revision as of 05:05, 10 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures |
scientific article |
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
