5
$\begingroup$

In an equitable coloring of a graph $G$, the number of vertices in each color class differ by at most $1$. For example, left below is not an equitable coloring, while the right graph is equitably colored.

Equitable_s12_n20.jpg

(I don't know if there is an equitable coloring for the left graph. Changing the topmost 3 to a 4 makes it more balanced but still not equitable.)

Q. Are there structural properties for planar trianguations that guarantee the existence of an equitable $4$-coloring?

By a triangulation I mean all faces, but possibly not the outer face, are triangles (as in the above examples). [As per @GordonRoyle's comment, these are known in the literature as "near triangulations."] It is relatively easy to identify classes of triangulations that cannot be equitably colored, e.g., wheel graphs:

         Wheel.jpg

But I am finding it more difficult to identify classes that can be equitably $4$-colored. There is literature on equitable coloring of planar graphs, but often triangulations are excluded.1 My sense is that it should be easier for triangulations.

1 Nakprasit, Keaitsuda, and Kittikorn Nakprasit. "Equitable colorings of planar graphs without short cycles." Theoretical Computer Science 465 (2012): 21-27. Earlier arXiv abstract.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I think near triangulation is the most commonly used term for a triangulation of a polygon. $\endgroup$
    – Gordon Royle
    Commented Jan 22, 2021 at 23:11
  • $\begingroup$ @GordonRoyle: Thanks; did not know that. I'm working with Delaunay triangulations (those examples derive from DTs). $\endgroup$
    – Joseph O'Rourke
    Commented Jan 22, 2021 at 23:16
  • 1
    $\begingroup$ Most likely it is NP-complete to decide whether an equitable 4-coloring exists or not. Here I've shown that the related problem of determining the domination number is NP-complete: arxiv.org/abs/1709.00596 $\endgroup$
    – domotorp
    Commented Jan 23, 2021 at 12:03
  • 2
    $\begingroup$ If you consider a triangulation obtained from a triangle by repeatedly adding a vertex in a (triangular) face and joining it to the 3 vertices of the face, then the resulting graph is planar and uniquely 4-colorable. Depending on the faces you chose you can skew the distribution of colors 1,2,3,4 arbitrarily, and once you have done that you can triangulate faces arbitrarily (by adding a small fraction of vertices, in such a way that the distribution stays arbitrarily far from being equitable). The class of triangulations you obtain this way is very large and does not have a real structure. $\endgroup$
    – Louis Esperet
    Commented Jan 25, 2021 at 9:54
  • $\begingroup$ @LouisEsperet: Very nice observations---Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Jan 25, 2021 at 12:17

0

Reset to default

You must log in to answer this question.