Bounded-gap conjecture for strong-immersion-free clustered coloring

From papers

For a graph HH, let χ(H)\chi_*(H) denote the strong-immersion coloring parameter used in the paper, and let the clustered chromatic number of a graph class be the least number of colors for which some uniform finite bound exists on the size of every monochromatic component. A graph contains HH as a strong immersion when the immersion model satisfies the strongness condition that branch vertices do not occur internally on the routing paths. Strong-immersion clustered-coloring conjecture. There exists a positive integer CC such that for every graph HH, the clustered chromatic number of the class of graphs that do not contain HH as a strong immersion is at most χ(H)+C\chi_*(H)+C. The paper explains that the gap between the clustered chromatic numbers for immersion-free and strong-immersion-free graphs is unknown and conjectures that it is bounded by an absolute constant.

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

Chun-Hung Liu, “Immersion and clustered coloring”, arXiv:2007.00259 (2021).

Solutions 0

No solutions have been posted yet.