Lescure–Meynial and Abu-Khzam–Langston chromatic immersion conjecture

From papers

Let tt be a positive integer, and let GG be a graph. An immersion of KtK_t in GG consists of distinct branch vertices corresponding to the vertices of KtK_t, together with paths in GG representing the edges of KtK_t, such that distinct representing paths are edge-disjoint. The chromatic number of GG, denoted χ(G)\chi(G), is the least number of colors in a proper vertex-coloring of GG. Lescure–Meynial and Abu-Khzam–Langston conjecture. If GG has no immersion of KtK_t, then

χ(G)t1.\chi(G)\leq t-1.

The source attributes this conjecture independently to Lescure and Meynial and to Abu-Khzam and Langston. The supplied status evidence says that a minimum counterexample would have minimum degree t1t-1, so the conjecture is disproved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gregory Gauthier, Tien-Nam Le and Paul Wollan, “Forcing clique immersions through chromatic number”, arXiv:1703.08235 (2017).

Solutions 0

No solutions have been posted yet.