Grunbaum colorings extended to non-facial 3- ¨ cycles

sarah-marie belcastro^∗a , Ruth Haas^b

^aMathematical Staircase, Inc., Holyoke MA, and Smith College, Northampton MA, U.S.A. ^bUniversity of Hawai'i at Manoa, Honolulu, HI, and Smith College, Northampton MA, U.S.A.

smbelcas@toroidalsnark.net, rhaas@math.hawaii.edu

∗ corresponding author

We consider the question of when a triangulation with a Grunbaum coloring can be edge-colored ¨ with three colors such that the non-facial 3-cycles also receive all three colors; we will call this a strong Grunbaum coloring ¨ . It turns out that for the sphere, every triangulation has a strong Grunbaum coloring, and that the presence of a ¨ K⁵ subgraph prohibits a strong Grunbaum coloring, ¨ but that K⁵ is not the only such barrier. We investigate the ramifications of these facts. We also show that for every other topological surface there exist triangulations with a strong Grunbaum ¨ coloring and triangulations that have Grunbaum colorings but that cannot have a strong Gr ¨ unbaum ¨ coloring. Finally, we reframe strong Grunbaum colorings as certain hypergraph edge colorings, ¨ and raise the question of how many colors are needed to achieve an edge coloring such that both facial and non-facial 3-cycles receive three colors.

Keywords: embedding, edge coloring, Grunbaum coloring, triangulation ¨

Mathematics Subject Classification: 05C10, 05C15

DOI: 10.5614/ejgta.2022.10.1.13

1. Introduction

We consider triangulations, which are embedded graphs in which every face has three edges. A triangulation has a Grunbaum coloring ¨ if there exists an edge 3-coloring in which each face is

Received: 1 November 2021, Revised: 27 February 2022, Accepted: 14 March 2022.

assigned all three colors. It is known that all planar triangulations and many classes of toroidal [1], projective-planar [4], and Klein-bottle [3] triangulations have Grunbaum colorings. One reason ¨ that Grunbaum colorings are of interest is because of their connection to the Four Color Theorem: ¨ Every planar graph has a Grunbaum coloring because the Four Color Theorem assures us of a ¨ face 4-coloring, and Tait's theorem implies that every face 4-colorable embedding has an edge 3-coloring (which is in turn dual to a Grunbaum coloring). ¨

There are many ways to generalize Grunbaum colorings. For example, in [5] the authors con- ¨ sider graph embeddings that have all faces of size d and attempt to assign each face d edge colors; in [6] the authors consider simplicial complexes and attempt to assign every simplicial facet all colors. More widely studied is the situation of 3-coloring triangles of (ordinary, not embedded) graphs. The papers [7, 8] find conditions under which an edge-colored graph must have a rainbow triangle; [2] counts the maximum number of rainbow triangles in 3-edge-colored Kn.

Our focus is a different generalization of Grunbaum colorings: We say that a triangulation has ¨ a strong Grunbaum coloring ¨ when it can be edge 3-colored such that both facial and non-facial 3 cycles receive all three colors. Note that a triangulation is topologically dual to an embedded cubic graph. While a Grunbaum coloring of a triangulation corresponds under duality to a proper edge ¨ 3-coloring of the dual cubic graph, a strong Grunbaum coloring corresponds to a stronger edge ¨ coloring of the dual cubic graph—in addition to being a proper edge 3-coloring, selected triples of must receive three distinct colors.

For which Grunbaum-colorable triangulations do there exist strong Gr ¨ unbaum colorings? We ¨ show in Section 2.1 that for the sphere, every triangulation has a strong Grunbaum coloring, and in ¨ Sections 2.2 and 2.3 that for every other topological surface there exist triangulations with a strong Grunbaum coloring ¨ and triangulations that have Grunbaum colorings but that cannot have a strong ¨ Grunbaum coloring. We explain in Section 2.4 why structural results are currently elusive. Finally, ¨ in Section 3 we raise, but do not resolve, the question of how many colors are needed to assign colors to edges of a triangulation of a surface such that every 3-cycle (both facial and non-facial) receives three distinct colors.

2. Results

2.1. Contractible triangles

As previously mentioned, every planar triangulation has at least one Grunbaum coloring. It ¨ turns out that not only does every planar triangulation have a strong Grunbaum coloring, but in ¨ fact every (regular) Grunbaum coloring on the plane will be a strong Gr ¨ unbaum coloring. The ¨ proof is straightforward, and as Mark Ellingham has observed, this proof is essentially the dual to that of the parity lemma.

Theorem 2.1. Every Grunbaum coloring of a planar triangulation is a strong Gr ¨ unbaum coloring. ¨

Proof. Consider a non-facial triangle in a Grunbaum coloring of a planar triangulation. This trian- ¨ gle and its interior may be cut out of the triangulation of the sphere and placed on another sphere, where the non-facial triangle has become the exterior face.

We now have a triangulation with f faces. Because a triangulation is dual to a cubic graph, it has an even number of faces; thus, f − 1 is odd. For any color, the total number of edge-face

incidences must be even, and therefore it must be that each color appears an odd number of times on the exterior face. The only way this can happen is if each color appears exactly once.

The ideas in the proof of Theorem 2.1 extend in multiple ways to triangulations on general surfaces.

Corollary 2.2. For a Grunbaum coloring of any triangulation on any orientable surface ¨ S^g or nonorientable surface Ng, any contractible triangle must be Grunbaum colored. ¨

Corollary 2.3. In a triangulation of edge-width at least 4 (so there are no noncontractible 3-cycles) on any surface S^g or Ng, every Grunbaum coloring is a strong Gr ¨ unbaum coloring. ¨

Corollary 2.4. Every 4-vertex-colorable triangulation on any surface S^g or N^g is strong Grunbaum ¨ colorable.

Corollary 2.4 follows directly from the proof in [1] that every 4-vertex-colorable triangulation is Grunbaum colorable. ¨

Corollary 2.5. A Grunbaum coloring of any triangulation with only contractible triangles is a ¨ strong Grunbaum coloring. ¨

2.2. Triangulations containing K⁵

From Corollary 2.3 we see that it remains to consider triangulations with noncontractible 3 cycles. The most elementary nonplanar subgraph to consider is K5.

Theorem 2.6. Any triangulation containing K⁵ is not strong Grunbaum colorable. ¨

Proof. We will show that six of the ten 3-cycles of K⁵ cannot be simultaneously be Grunbaum ¨ colored, so for any embedding of K⁵ there does not exist a strong Grunbaum coloring. For illus- ¨ tration, consider an embedding of K⁵ on the torus where 4 of the 3-cycles are facial triangles and 6 of the 3-cycles are noncontractible. In Figure 1(left), we color the 1-2-5 facial triangle purple-

Figure 1. A K⁵ on the torus with (left) one facial triangle colored (center) an additional noncontractible cycle colored (right) a contradiction to Grunbaum coloring a different noncontractible cycle. ¨

teal-gold. Note that edge 5-3 cannot be gold if the 2-3-5 facial triangle is to have three colors; nor can edge 5-3 be purple if the 1-5-3 cycle is to have three colors. Thus, edge 5-3 must be teal (see

Figure 1(center)). Now, examine edge 4-5. This edge cannot be purple if the 1-4-5 facial triangle is to have three colors, nor can it be teal if the 3-4-5 facial triangle is to have three colors; thus, edge 4-5 must be gold. However, this prohibits the 4-5-2 noncontractible 3-cycle from receiving three colors, so it is not possible to create a strong Grunbaum coloring of ¨ K5.

Note that this does not extend to subdivisions of K5, as the example in Figure 2 shows. However, Theorem 2.6 allows us to produce Grunbaum-colored triangulations that are not strong ¨

Figure 2. This embedded subdivision of K⁵ easily extends to a strong Grunbaum colored toroidal triangulation. ¨

Grunbaum colorable on every nonspherical surface. ¨

Corollary 2.7. For g ≥ 1, there exists a triangulation T^g embedded on S^g such that T^g has a 3 cycle corresponding to every homotopy generator and has a Grunbaum coloring but not a strong ¨ Grunbaum coloring. Moreover, ¨ T^g has at least g non-3-colored noncontractible 3-cycles (one on each torus in the connected sum).

Proof. Consider the triangulation N of the torus given in Figure 3; it has a Grunbaum coloring but, ¨ because it contains K5, not a strong Grunbaum coloring. ¨

Figure 3. A Grunbaum colored toroidal triangulation containing ¨ K5.

Now consider the Grunbaum-colored triangulation of the cylinder ¨ C shown in Figure 4. First

Figure 4. An even triangulated cylinder with a strong Grünbaum coloring.

we construct a Grünbaum-colored triangulation on the two-holed torus. Begin with two copies of N, say \(N_1\) and \(N_2\). Remove the interior of one (Grünbaum-colored) face of \(N_1\), and identify its edges with the edges on one boundary of C; then, remove the interior of a face of \(N_2\) and identify its edges with the other cylinder boundary. This produces the desired triangulation.

We can use this same process to construct a Grünbaum-colored triangulation on \(\mathbb{S}_g\) as follows: Using copies \(N_1, \ldots N_g\) of N and copies \(C_1, \ldots C_{g-1}\) of C, remove the interior of one face of \(N_1, N_g\) and remove the interior of two faces of each of \(N_2, \ldots N_{g-1}\). For each \(1 \leq i \leq g-1\), identify the edges bounding a removed face of \(N_i\) with one boundary of \(C_i\) and identify the edges bounding a (different) removed face of \(N_{i+1}\) with the other boundary of \(C_i\). This produces a triangulation \(T_g\) embedded on \(\mathbb{S}_g\), for \(g \geq 1\), such that \(T_g\) has a \(K_5\) contained in every torus of the connected sum, and therefore a 3-cycle corresponding to every homotopy generator. \(T_g\) therefore also has a Grünbaum coloring but not a strong Grünbaum coloring.

The toroidal triangulation containing \(K_5\) shown in Figure 3 has chromatic number 6. A natural question is whether the situation is different for toroidal triangulations with chromatic number 5, or for even triangulations. This is not the case. Figure 5 shows a toroidal triangulation that has a Grünbaum coloring but cannot have a strong Grünbaum coloring, but that is even and has chromatic number 5.

Figure 5. A 5-chromatic even toroidal triangulation that has a Grünbaum coloring but cannot have a strong Grünbaum coloring.

We next treat the case of nonorientable surfaces.

Corollary 2.8. For \(g \ge 1\), there exists a triangulation \(T'_g\) embedded on \(\mathbb{N}_g\) such that \(T'_g\) has a 3-cycle corresponding to every homotopy generator and has a Grünbaum coloring but not a strong

Grünbaum coloring. Moreover, \(T'_g\) has at least g non-3-colored noncontractible 3-cycles (one on each projective plane in the connected sum).

Proof. Consider the triangulation of the projective plane given in Figure 6; it has a Grünbaum coloring but, because it contains \(K_5\), not a strong Grünbaum coloring.

Figure 6. A Grünbaum-colored projective-planar triangulation containing \(K_5\).

Using the same construction given in the proof of Proposition 2.7 but with the triangulation from Figure 6, we obtain a triangulation \(T'_g\) embedded on \(\mathbb{N}_g\), for \(g \geq 1\), such that \(T'_g\) has a 3-cycle corresponding to every homotopy generator and has a Grünbaum coloring but not a strong Grünbaum coloring.

2.3. Structural Observations

After finding that any triangulation containing \(K_5\) cannot be strong Grünbaum colorable, the next natural question to ask is whether a Grünbaum colorable triangulation without \(K_5\) must have a strong Grünbaum coloring. As Proposition 2.9 attests, the answer is 'no.' However, at the same time we can find many strong Grünbaum colorings of \(K_5\)-free nonplanar triangulations. In Proposition 2.10 we construct a family of such triangulations with at least one 3-cycle corresponding to each homotopy generator. We close the section with an example of a Grünbaum colored triangulation with a single 3-cycle and no strong Grünbaum coloring.

Proposition 2.9. There exists a \(K_5\)-free triangulation \(T_g\) embedded on \(\mathbb{S}_g\), for \(g \geq 1\), and there exists a \(K_5\)-free triangulation \(T'_{2g}\) embedded on \(\mathbb{N}_{2g}\), for \(2g \geq 2\), such that \(T_g\), \(T'_{2g}\) has a 3-cycle corresponding to every homotopy generator and has a Grünbaum coloring but not a strong Grünbaum coloring.

Proof. By examination of Figure 7 we can see that these triangulations, of the torus and Klein bottle respectively, have Grünbaum colorings. Using the construction given in the proof of Corollary 2.7 analogous triangulations can be constructed for any \(\mathbb{S}_g\), g>1 and for any \(\mathbb{N}_{2g}\), 2g>2. To show that the triangulations in Figure 7 cannot be strong Grünbaum colored, we work in the dual with 3-regular graphs. Here, any triple of edges dual to a noncontractible 3-cycle in the triangulation—a triple of edges crossing a noncontractible loop in the surface—must get 3 different colors.

Figure 7. A Grunbaum-colored toroidal triangulation and a Gr ¨ unbaum-colored triangulation of the Klein bottle, neither ¨ containing K5.

Consider the embedded gadget shown at left in Figure 8. If it is part of the dual to a strong Grunbaum coloring, then it must have three different colors on the left-hand triple of edges. Check- ¨

Figure 8. A gadget and its possible "strong" proper 3-colorings.

ing possible edge colorings by brute force produces only the three proper edge colorings shown at right. Note that for each of these three colorings, the middle-left partial edge is always the same color as the upper-right partial edge.

Now examine the toroidal 3-regular graph shown in Figure 9, composed of three copies of the gadget from Figure 8. It is dual to the triangulation in Figure 7. Suppose that edge e is assigned color a in a "strong" proper edge 3-coloring (so that it will be dual to a strong Grunbaum coloring), ¨

Figure 9. Three copies of the Figure 8 gadget form a toroidal embedding dual to Figure 7.

with color b assigned to edge f. This forces the upper-right edges emanating from each gadget to be assigned color b, which means that both edge e and edge f must be assigned color b. Therefore this graph's dual (Figure 7, top) cannot have a strong Grünbaum coloring.

This same drawing, but with the top-left partial edge joined to the bottom-right partial edge and the bottom-left partial edge joined to the top-right partial edge, gives an embedding on the Klein bottle. Again assigning color b to edge f, we find that the upper-right partial edge must also be color b. This eliminates the possibility that the dual (Figure 7, bottom) could have a strong Grünbaum coloring.

Note that Proposition 2.9 gives no information about the existence of a \(K_5\)-free triangulation T embedded on the projective plane such that T has at least one noncontractible 3-cycle and has a Grünbaum coloring but not a strong Grünbaum coloring.

At this point it seems that perhaps strong Grünbaum colorings are unusual on most surfaces, even for triangulations with a sparse distribution of noncontractible 3-cycles. Yet, the next proposition gives strong Grünbaum colorings for any nonspherical surface.

Proposition 2.10. Given \(g \ge 1\), there exists a triangulation \(T_g\) embedded on \(\mathbb{S}_g\) and there exists a triangulation \(T'_g\) embedded on \(\mathbb{N}_g\) such that \(T_g, T'_g\) has a 3-cycle corresponding to every homotopy generator and has a strong Grünbaum coloring.

Proof. Consider the triangulations of the torus and projective plane given in Figure 10; each has a strong Grünbaum coloring. Note that the Grünbaum coloring of the triangulated cylinder shown in Figure 4 is a strong Grünbaum coloring; thus we may use the same construction as given in the proof of Proposition 2.7 for each of the triangulations given in Figure 10 to produce the desired examples.

In the opposite direction, we may consider a triangulation with a single non-contractible 3-cycle. In this mildest case, must every such triangulation with a Grünbaum coloring also have a strong Grünbaum coloring? It turns out that the answer is 'no.'

Proposition 2.11. There exists a triangulation embedded on the torus with exactly one non-contractible 3-cycle that has a Grünbaum coloring but not a strong Grünbaum coloring.

Figure 10. Strong Grunbaum colored triangulations on torus(left) and projective plane (right). ¨

Proof. We will show that the dual to the properly edge 3-colored graph in Figure 11 has the desired property. This graph has exactly one triple of edges dual to a non-contractible 3-cycle. The proper

Figure 11. A proper edge coloring of a 3-regular toroidal graph.

edge 3-coloring immediately gives a Grunbaum coloring of the dual triangulation that is not strong ¨ Grunbaum, so it remains to show that no other proper edge 3-coloring of the Figure 11 embedded ¨ graph can correspond to a strong Grunbaum coloring of the dual triangulation. ¨

As shown in Figure 14, this graph is constructed by combining two (uncolored) copies of the embedded gadget shown in Figure 12 with three (uncolored) copies of the embedded gadget shown at left in Figure 13 and one (uncolored) copy of the gadget shown at right in Figure 13. For ease of reference, for each gadget we will call the left-hand pendant edges the input of the gadget and the right-hand pendant edges the output of the gadget.

Consider the embedded gadget shown at left in Figure 12. If it is part of the dual to a strong Grunbaum coloring, then it must have three different colors on the left-hand triple of pendant edges. ¨ Checking possible edge colorings by brute force produces only the six proper edge colorings shown at right in Figure 12. Note the five different colorings of the output.

Next consider the left part of Figure 13, which shows the colorings of an embedded stick gadget where the input colorings match the patterns of the output colorings from Figure 12. At right in

Figure 12. A gadget and its possible "strong" proper 3-colorings.

Figure 13 is our third, small gadget: if the input edges are the same color, then the output edges must be a different color; if the input edges are different colors, then the output has the same two colors with positions swapped.

Now examine the toroidal 3-regular graph shown in Figure 14. Suppose that the left-hand triple of edges is assigned three different colors in a "strong" proper edge 3-coloring (so that it will be dual to a strong Grunbaum coloring). No matter which coloring the left (Figure 12) gadget has, ¨ this coloring will propagate across the three copies of the Figure 13 stick gadget to output one of the five output colorings of the Figure 12 gadget. Then the Figure 13 small gadget changes the coloring: the four pendant edges leading into the reflected Figure 12 gadget on the right must have a coloring that is not one of the five possible colorings that will allow the triple of edges at right to receive three different colors.

Therefore the Figure 14 graph's dual cannot have a strong Grunbaum coloring. This completes ¨ the proof.

2.4. Revealing the challenge: a hypergraph reformulation of the problem

So far in this paper we have built a catalog of results about conditions when a strong Grunbaum ¨ coloring does and does not exist, but a structural classification seems to be out of reach. This difficulty motivates a reframing of the problem.

Figure 13. At left, propagation of colorings from Figure 12 across an embedded gadget; at right, the possible colorings of an unembedded gadget.

Figure 14. The decomposition of the Figure 11 graph into gadgets.

So far we have described a strong Grunbaum coloring of a triangulation ¨ T as dual to a proper edge 3-coloring of an embedded cubic graph G that also has some special triples of edges that must receive three different colors. Another way of conceptualizing this structure is as a hypergraph H constructed from our embedded cubic graph G, where we add a vertex v for each dual noncontractible 3-cycle of T, and v is incident to the three corresponding edges in G. In H, every vertex is incident to three edges but may have much higher degree—in particular, an added vertex has degree at least 5 because it is adjacent to the two vertices on each of its three incident edges (and at most two of those edges share a vertex). The strong Grunbaum coloring now corresponds ¨ to a proper edge coloring of H.

We may require H to be linear, i.e. having no two edges that share more than one vertex, by not allowing T to have multiple edges. Note that H is not uniform: most edges have size 2 (as they are not dual to edges in non-contractible 3-cycles), and some have size 3 or more. An edge of H that is dual to an edge of T in exactly one non-contractible 3-cycle will have size 3, but an edge of H that is dual to an edge of T in multiple non-contractible 3-cycles will have larger size.

Unfortunately, as of this writing there are no known results on proper edge coloring of non-

uniform hypergraphs. In some sense this explains why we are not easily able to obtain stronger results, especially about which triangulations have (or do not have) strong Grunbaum colorings. ¨

3. Extra colors

A natural extension of determining which triangulations have strong Grunbaum colorings is: ¨ For a triangulation with no strong Grunbaum coloring, how many additional colors are needed for ¨ both facial and non-contractible triangles to be assigned three colors each?

Intuitively we expect that sparser non-contractible 3-cycles will indicate fewer additional colors are needed and denser or overlapping non-contractible 3-cycles will indicate more additional colors are required. For example, consider a triangulation that has only a few non-contractible 3-cycles that are far apart. At worst, each non-contractible 3-cycle could be forced to be monochromatic in any Grunbaum coloring. In this case, at most 2 additional colors will be needed overall, for a total ¨ of 5 colors. On the other hand, if a triangulation has many non-contractible 3-cycles with edges shared pairwise, we expect more colors will be needed. Still, K⁶ embedded on N¹ (with many non-contractible 3-cycles) appears to need only 5 colors, so perhaps only a few extra colors often suffices.

Encouraged by such examples, we attempt to find upper bounds on the number of extra colors needed to strong Grunbuam color an embedded triangulation ¨ T. To quantify, let b(T) denote the least number of edge colors needed so that every facial triangle and every non-contractible 3-cycle uses exactly three colors.

3.1. A potential hypergraph-based upper bound

While there are no results on edge coloring non-uniform hypergraphs, there is a conjecture that generalizes Vizing's theorem, namely that χ ′ (H) ≤ ∆(H) + 1. This holds for ∆(H) ≤ 5 [9], but is open for ∆(H) > 5. (The generalized Vizing bound is sometimes achieved by hypergraphs not generated from embedded graphs: Consider a hypergraph with vertices a, b, c, d, e, f, g and edges abc, ade, afg, bdf, beg, cef, cdg, which has ∆(H) = 6, χ′ (H) = 7.)

In the case of a single non-contractible 3-cycle, we see that this bound is not useful. Such a triangulation with a Grunbaum coloring but no strong Gr ¨ unbaum coloring needs at most 2 additional ¨ colors for the non-contractible 3-cycle. As noted in Section 2.4, here ∆(H) ≥ 5, so the generalized Vizing conjecture gives an upper bound for b(H) of at least 6 in this case. Examining Figure 3, we see that with non-contractible 3-cycles that share edges, we may still only need 2 additional colors, but the associated hypergraph has ∆(H) = 10, for a conjectured hypergraph Vizing upper bound of 11. More generally, non-contractible 3-cycles that are not disjoint drive up ∆(H) and thereby make the use of a hypergraph version of the Vizing bound unlikely.

Suppose instead that results on proper edge coloring of non-uniform hypergraphs existed. To use such results would require encoding a given embedding as a hypergraph. In turn, this means identifying every non-contractible 3-cycle, which is exactly why generating precise results—or even computing examples!—is so difficult.

3.2. A chromatic-number-based upper bound

Consider a complete graph: in this case, every three edges form a 3-cycle and so a strong Grunbaum coloring is also a proper edge coloring. Thus, ¨ b(Kn) = n−1 if n is even and b(Kn) = n if n is odd. We can use this to find an upper bound for b(T) in terms of the chromatic number of T, but in fact this holds for graphs in general, where b(G) denotes the least number of edge colors needed so that every triangle in a proper edge coloring receives three colors:

Theorem 3.1 (by Mike Albertson). For any simple graph G, b(G) ≤ b(Kχ(G)) = χ(G) if χ(G) is odd and = χ(G) − 1 if χ(G) is even.

Proof. We properly vertex color G using χ(G) colors, and consider an edge coloring of Kχ(G) . Given an edge e of G with vertices v1, v² that have colors c1, c2, we assign e the same color as the edge of Kχ(G) with incident vertices of colors c1, c2. Then any triangle of G will have three different edge colors.

3.3. Comparing/contrasting the two bounds

The conjectured hypergraph version of Vizing's theorem depends on the degree of the hypergraph, which in turn depends on the structure of the non-contractible 3-cycles. The chromatic number of a triangulation is bounded above by the Heawood number of the embedding surface. These parameters are completely unrelated, so we expect one bound to be better for some embeddings, and the other to be better for other embeddings. For example, a graph with large maximum degree will likely have a lower Heawood number. In any event, neither of these two approaches appears to be helpful for any large class of cases.

Acknowledgement

Thanks to Corrine Yap for helping us learn about hypergraphs and contributing the example in Section 3.1, and to Mike Albertson for suggesting the chromatic-number-based upper bound. We are also grateful to the anonymous referee who suggested superior terminology and smoothing of text.

References

• [1] M.O. Albertson, H. Alpert, s-m. belcastro, and R. Haas, Grunbaum colorings of toroidal tri- ¨ angulations, Journal of Graph Theory 63:1 (2010), 68–81. https://arxiv.org/abs/ 0805.0394
• [2] J. Balogh, P. Hu, B. Lidicky, F. Pfender, J. Volec, and M. Young, Rainbow triangles in threecolored graphs, Journal of Combinatorial Theory, Series B 26 (2017), 83–113. https: //arxiv.org/abs/1408.5296
• [3] s-m. belcastro, Small snarks and 6-chromatic triangulations on the Klein bottle, Australasian J. Combinatorics 65:3 (2016), 232–250. http://ajc.maths.uq.edu.au/pdf/65/ ajc_v65_p232.pdf

• [4] M. Kasai, N. Matsumoto, and A. Nakamoto, Grunbaum colorings of triangulations on the ¨ projective plane, Discrete Applied Mathematics 215 (2016), 155–163. https://www. sciencedirect.com/science/article/pii/S0166218X16303328
• [5] S. Lawrencenko and A.M. Magomedov, All face 2-colorable d-angulations are Grunbaum ¨ colorable, Journal of Combinatorial Mathematics and Combinatorial Computing 95 (2015), 301–307. http://arxiv.org/abs/1501.01261
• [6] S. Lawrencenko, M.N. Vyalyi, and L.V. Zgonnik, Grunbaum coloring and its generalization ¨ to arbitrary dimension, Australasian Journal of Combinatorics 67:2 (2017), 119–130. http: //arxiv.org/abs/1607.03959
• [7] R. Li, B. Ning, and S. Zhang, Color Degree Sum Conditions for Rainbow Triangles in Edge-Colored Graphs, Graphs and Combinatorics 32 (2016), 2001–2008. https://link. springer.com/article/10.1007/s00373-016-1690-2
• [8] B. Li, B. Ning, C. Xu, and S. Zhang, Rainbow triangles in edge-colored graphs, European Journal of Combinatorics 36 (2014), 453–459. http://arxiv.org/abs/1212.6348
• [9] G-H. Zhang and B. Skinner, Chromatic index of simple hypergraphs, Discrete Mathematics 343:12 (2020), 112087. https://doi.org/10.1016/j.disc.2020.112087