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

About 6 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.