19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On the ultimate direct Hall-ratio

Presented by Ms. Agnes TOTH
Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs


The Hall-ratio $\rho(G)$ of a graph $G$ is the ratio of the number of vertices and the independence number maximized over all subgraphs of $G$. The ultimate direct Hall-ratio of a graph $G$ is defined as $\lim _{k\to \infty} \rho (G^{\times k})$, where $G^{\times k}$ denotes the $k$th direct power of $G$ (that is, $G^{\times k}$ is defined on the $k$-length sequences over the vertex set of $G$, and two such sequences are connected iff their elements form an edge in $G$ at every coordinate). We prove the conjecture of Simonyi stating that the ultimate direct Hall-ratio equals to the fractional chromatic number for all graphs. The proof uses a recent result of Zhu that he proved on the way when proving the fractional version of Hedetniemi's conjecture.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

  • Ms. Agnes TOTH Budapest University of Technology and Economics, Hungary