More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures (Q625392): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q175582 |
Import IPFS CIDs |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / reviewed by | |||
| Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: Publication / rank | |||
Normal rank | |||
| Property / IPFS content identifier | |||
| Property / IPFS content identifier: bafkreihwn7fezvv6zgwqa735f4p5y7xnrz4dxfhgjo2n5l5hiun2cejuia / rank | |||
Normal rank | |||
Latest revision as of 11:46, 22 February 2025
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
