Bounded-gap conjecture for strong-immersion-free clustered coloring
Bounded-gap conjecture for strong-immersion-free clustered coloring
For a graph , let 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 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 such that for every graph , the clustered chromatic number of the class of graphs that do not contain as a strong immersion is at most . 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
Sign in to submit a solution.
No solutions have been posted yet.