  Given an undirected graph $G$, we define a new object $H_G$, called the
mp-chart of $G$, in the max-plus algebra. We use it, together with the max-plus
permanent, to describe the complexity of graphs. We show how to compute the
mean and the variance of $H_G$ in terms of the adjacency matrix of $G$ and we
give a central limit theorem for $H_G$. Finally, we show that the mp-chart is
easily tractable also for the complement graph.
