Known to be at most 5, witnessed by the following path:
Erdős Fan Rong K. Chung / Stephen T. Hedetniemi / Maria Margaret Klawe Robert E. Tarjan Bob Paige Fritz Henglein Christian Stefansen
and also by
Erdős Ronald L. Graham Jeffrey D. Ullman Harry G. Mairson Fritz Henglein Christian Stefansen
This is a slightly modified version of the paths found on Henning Makholm’s homepage.
Read about The Erdős Number Project.