\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Sebastian M. Cioab\u{a} and Michael Tait}
%
%
\medskip
\noindent
%
%
{\bf More Counterexamples to the Alon-Saks-Seymour and Rank-Coloring Conjectures}
%
%
\vskip 5mm
\noindent
%
%
%
%
The chromatic number $\chi(G)$ of a graph $G$ is the minimum number of
colors in a proper coloring of the vertices of $G$. The biclique
partition number ${\rm bp}(G)$ is the minimum number of complete bipartite
subgraphs whose edges partition the edge-set of $G$.
The Rank-Coloring Conjecture (formulated by van Nuffelen in 1976)
states that $\chi(G)\leq {\rm rank}(A(G))$, where ${\rm rank}(A(G))$
is the rank of the adjacency matrix of $G$. This was disproved in 1989
by Alon and Seymour. In 1991, Alon, Saks, and Seymour conjectured that
$\chi(G)\leq {\rm bp}(G)+1$ for any graph $G$. This was recently
disproved by Huang and Sudakov. These conjectures are also related to
interesting problems in computational complexity.
In this paper, we construct new infinite families of counterexamples
to both the Alon-Saks-Seymour Conjecture and the Rank-Coloring
Conjecture. Our construction is a generalization of similar work by
Razborov, and Huang and Sudakov.
\end{document}