Regular chromatic number and the lonely runner problem. (English) Zbl 1215.05052

Barajas, J.; Serra, O.

Márquez, Alberto (ed.) et al., Proceedings of the 4th European conference on combinatorics, graph theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 29, 479-483 (2007).

Summary: Suppose \(k+1\) runners having nonzero constant speeds run laps on a unit-length circular track. The lonely runner conjecture states that there is a time at which one runner is at distance at least \(1/(k+1)\) from all the others. The conjecture has been proved up to six runners (\(k\leq 5\)). A formulation of the problem is related to the regular chromatic number of distance graphs. We use a new tool developed in this context to solve the first open case of the conjecture with seven runners.
For the entire collection see [Zbl 1137.05002].

MSC:

05C15	Coloring of graphs and hypergraphs
52A40	Inequalities and extremum problems involving convexity in convex geometry
11B75	Other combinatorial number theory

References:

[1]	Barajas and O. Serra, Distance graphs with maximum chromatic number; Barajas and O. Serra, Distance graphs with maximum chromatic number · Zbl 1192.05035
[2]	J. Barajas and O. Serra, On the chromatic number of circulant graphs; J. Barajas and O. Serra, On the chromatic number of circulant graphs · Zbl 1213.05064
[3]	Betke, U.; Wills, J. M., Untere Schranken für zwei diophantische Approximations-Funktionen, Monatsch. Math., 76, 214-217 (1972) · Zbl 0239.10016
[4]	Bienia, W.; Goddyn, L.; Gvozdjak, P.; Sebő, A.; Tarsi, M., Flows, View Obstructions, and the Lonely Runner, J. of Combin. Th. Ser. B, 72, 1-9 (1998) · Zbl 0910.05064
[5]	Bohman, T.; Holzman, R.; Kleitman, D., Six lonely runners. Electron. J. Combin., 8, 2 (2001), Research Paper 3, 49 pp. (electronic) · Zbl 1011.11048
[6]	Cusick, T. W., View-obstruction problems, Aequationes Math., 9, 165-170 (1973) · Zbl 0265.52003
[7]	Cusick, T. W., View-obstruction problems in n-dimensional geometry, J. Combin. Theory Ser. A, 16, 1-11 (1974) · Zbl 0273.10025
[8]	Cusick, T. W., View-obstruction problems II, Proc. Amer. Math. Soc., 84, 25-28 (1982) · Zbl 0474.10023
[9]	Cusick, T. W.; Pomerance, C., View-obstruction problems, III, J. Number Theory, 19, 131-139 (1984) · Zbl 0563.10026
[10]	Renault, J., View-obstruction: a shorter proof for 6 lonely runners, Discrete Math., 287, 1-3, 93-101 (2004) · Zbl 1061.11036
[11]	Wills, J. M., Zwei Säzte über inhomogene diophantische Appreoximation von Irrationalzahlen, Monatsch. Math., 71, 263-269 (1967) · Zbl 0148.27505
[12]	Zhu, X., Circular chromatic number of distance graphs with distance sets of cardinality three, J. Graph Theory, 41, 3, 195-207 (2002) · Zbl 1012.05071