The edge-contraction lower-bound conjecture for dominated chromatic number

Let GG be a graph and let ee be an edge of GG. Write G/eG/e for the graph obtained by contracting ee, and let χdom(G)\chi_{dom}(G) denote the dominated chromatic number of GG. Edge-contraction conjecture.

χdom(G)1χdom(G/e).\chi_{dom}(G)-1\leq \chi_{dom}(G/e).

The authors report that this stronger lower bound is suggested by checking graphs of small order, while they have not been able to prove it. It improves the previously established bound χdom(G)2χdom(G/e)\chi_{dom}(G)-2\leq \chi_{dom}(G/e) by one.

Sources & referencesView supporting material

Primary source

Saeid Alikhani and Mohammad R. Piri, “Dominated chromatic number of some operations on a graph”, arXiv:1912.00016 (2019).

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.