@techreport{TR-IC-13-18,
number = {IC-13-18},
author = {At\'{i}lio Gomes Luiz and R. Bruce Richter},
title = {{Colorings and crossings}},
month = {August},
year = {2013},
institution = {Institute of Computing, University of Campinas},
note = {In English, 32 pages.
\par\selectlanguage{english}\textbf{Abstract}
In 2007, Albertson conjectured that if a graph $G$ has
chromatic number $k$, then the crossing number of $G$ is at
least the crossing number of the complete graph with $k$
vertices. To date, two papers were written on this subject
trying to solve the conjecture for an arbitrary $k$-chromatic
graph $G$, and after much effort the conjecture was proved true
for $k \leq 16$. In this report, we present an overview of
topics related to Albertson's Conjecture, such as: the crossing
number problem, lower bounds on crossing number, lower bounds
on the number of edges of color-critical graphs, and coloring
of graphs with small crossing number and small clique number.
While investigating Albertson's conjecture, J. Bar\'{a}t and G.
T\'{o}th proposed the following conjecture involving
color-critical graphs: for every positive integer $c$, there
exists a bound $k(c)$ such that for any $k$, where $k \geq
k(c)$, any k-critical graph on $k+c$ vertices has a subdivision
of $K_k$. In Section $9$, we present counterexamples to this
conjecture for every $c \geq 6$ and we prove that the
conjecture is valid for $c = 5$.
}
}