More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures

MaRDI QIDQ625392zbMATH OpenFDO

Authors Sebastian Cioaba, Michael Tait

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/231767, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p26.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

biclique partition numberchromatic numberrank coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

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.

Recommendations

• scientific article; zbMATH DE number 34576
• A counterexample to the rank-coloring conjecture
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• scientific article; zbMATH DE number 2188427
• Counterexamples to a conjecture on injective colorings
• The Schur-Erdős problem for semi-algebraic colorings
• A counterexample to a 𝐵𝑃-analogue of the chromatic splitting conjecture
• Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
• A counterexample to montgomery's conjecture on dynamic colourings of regular graphs
• Counterexamples to a conjecture on matching Kneser graphs

Cited in

(8)

• Eigenvalues of Cayley graphs
• On the binary and Boolean rank of regular matrices
• A counterexample to the rank-coloring conjecture
• scientific article; zbMATH DE number 34576 (Why is no real title available?)
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Problems and invariants connected with bicliques and multicliques of graphs
• scientific article; zbMATH DE number 2188427 (Why is no real title available?)
• Spectral classes of regular, random, and empirical graphs

This page was built for publication: More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625392)