Improper conflict-free and unique-maximum coloring conjecture for planar and outerplanar graphs

Let P\mathcal{P} be the class of planar graphs and O\mathcal{O} the class of outerplanar graphs. Write χiCFo\chi_{\mathrm{iCFo}}, χiCFc\chi_{\mathrm{iCFc}}, χiUMo\chi_{\mathrm{iUMo}}, and χiUMc\chi_{\mathrm{iUMc}} for the corresponding improper conflict-free and improper unique-maximum chromatic numbers, with respect to open or closed neighborhoods as indicated by the subscripts.

Improper coloring conjecture. For the classes P\mathcal{P} and O\mathcal{O}, the following equalities hold:

χiCFo(P)=4,χiCFc(P)=3,χiUMo(P)=5,χiUMc(P)=4,\chi_{\mathrm{iCFo}}(\mathcal{P})=4,\quad \chi_{\mathrm{iCFc}}(\mathcal{P})=3,\quad \chi_{\mathrm{iUMo}}(\mathcal{P})=5,\quad \chi_{\mathrm{iUMc}}(\mathcal{P})=4, χiCFo(O)=3,χiUMo(O)=4,χiUMc(O)=3.\chi_{\mathrm{iCFo}}(\mathcal{O})=3,\quad \chi_{\mathrm{iUMo}}(\mathcal{O})=4,\quad \chi_{\mathrm{iUMc}}(\mathcal{O})=3.

The conjecture proposes that the currently known lower bounds are tight for all listed improper coloring parameters; the corresponding gaps between lower and upper bounds are unresolved.

Sources & referencesView supporting material

Primary source

Igor Fabrici, Borut Lužar, Simona Rindošová and Roman Soták, “Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods”, arXiv:2202.02570 (2022).

Additional references

2 papers in this index state this conjecture (2016–2022). The statement above is taken from the most recent of them; the others are arXiv:1603.02841.

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.