King and Pelsmajer's bounded-exception domination conjecture for plane triangulations

From papers

Let GG be an nn-vertex plane triangulation, and let tt be a fixed nonnegative integer. A vertex has degree other than 66 when its degree in GG is not equal to 66. A dominating set is a set of vertices such that every vertex is either in the set or adjacent to a vertex in the set.

King and Pelsmajer's conjecture. For any constant tt, there exists ntn_t such that every nn-vertex plane triangulation with n>ntn>n_t and at most tt vertices of degree other than 66 has a dominating set of size at most n/4n/4.

This extends the previously studied maximum-degree-at-most-66 case to triangulations with only a bounded number of exceptional-degree vertices. The paper states this as a conjecture and subsequently proves a stronger bound under the same bounded-exception hypothesis.

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

Hong Liu and Michael J. Pelsmajer, “Dominating Sets in Triangulations on Surfaces”, arXiv:1006.1879 (2011).

Solutions 0

No solutions have been posted yet.