The Last Fraction of a Fractional Conjecture

Authors :: Jean-Sébastien Sereni
Daniel Král
František Kardoš
Institut teoretické informatiky (ITI)
Charles University [Prague] (CU)
Institute of Mathematics
P.J. Safarik University
Department of Applied Mathematics (KAM) (KAM)
Univerzita Karlova v Praze
Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Source :: SIAM Journal on Discrete Mathematics, SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2010, 24 (2), pp.699--707. ⟨10.1137/090779097⟩
Publication Year :: 2010
Publisher :: Society for Industrial & Applied Mathematics (SIAM), 2010.
Abstract: Reed conjectured that for every $\varepsilon>0$ and every integer $\Delta$, there exists $g$ such that the fractional total chromatic number of every graph with maximum degree $\Delta$ and girth at least $g$ is at most $\Delta+1+\varepsilon$. The conjecture was proven to be true when $\Delta=3$ or $\Delta$ is even. We settle the conjecture by proving it for the remaining cases.<br />Comment: A typo has been corrected in the introduction (concerning the citation of the result by Ito, Kennedy and Reed)

Tools