The relaxed locally identifying coloring conjecture for free-twin split graphs

From papers

Let GG be a free-twin split graph, meaning that GG is a split graph with no pair of free twins. Write χrlid(G)\chi_{rlid}(G) for its relaxed locally identifying chromatic number and ω(G)\omega(G) for its clique number. Free-twin split graph conjecture. If GG is a free-twin split graph, then

χrlid(G)ω(G)+1.\chi_{rlid}(G)\leq\omega(G)+1.

The conjecture proposes an improvement of the previously established upper bound χrlid(G)ω(G)+2\chi_{rlid}(G)\leq\omega(G)+2 for split graphs; the source gives no resolution.

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

Méziane Aïder, Sylvain Gravier and Souad Slimani, “Relaxed Locally Identifying coloring of Graphs”, arXiv:1406.3683 (2014).

Solutions 0

No solutions have been posted yet.