More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures (Q625392): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Latest revision as of 00:46, 5 March 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
