On multichromatic numbers of widely colorable graphs

Gujgiczer, Anna and Simonyi, Gábor (2022) On multichromatic numbers of widely colorable graphs. JOURNAL OF GRAPH THEORY, 100 (2). pp. 346-361. ISSN 0364-9024

Preview

Text 2102_03120v1.pdf Download (183kB) | Preview

Abstract

A coloring is called (Formula presented.) -wide if no walk of length (Formula presented.) connects vertices of the same color. A graph is (Formula presented.) -widely colorable with (Formula presented.) colors if and only if it admits a homomorphism into a universal graph (Formula presented.). Tardif observed that the value of the (Formula presented.) multichromatic number (Formula presented.) of these graphs is at least (Formula presented.) and equality holds for (Formula presented.). He asked whether there is equality also for (Formula presented.). We show that (Formula presented.) for all (Formula presented.) thereby answering Tardif's question. We observe that for large (Formula presented.) (with respect to (Formula presented.) and (Formula presented.) fixed) we cannot have equality and that for (Formula presented.) fixed and (Formula presented.) going to infinity the fractional chromatic number of (Formula presented.) also tends to infinity. The latter is a simple consequence of another result of Tardif on the fractional chromatic number of generalized Mycielski graphs.

Actions (login required)

Edit Item