The Grötzsch Theorem for the hypergraph of maximal cliques

Bojan Mohar^{∗} and Riste Škrekovski^{∗}

Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana Slovenia

                  bojan.mohar@uni-lj.si
              riste.skrekovski@fmf.uni-lj.si

Submitted: September 5, 1998; Accepted: June 7, 1999.

Mathematical Subject Classification: 05C15, 05C65.

Abstract

In this paper, we extend the Grötzsch Theorem by proving that the clique hypergraph H(G) of every planar graph is 3-colorable. We also extend this result to list colorings by proving that H(G) is 4-choosable for every planar or projective planar graph G. Finally, 4-choosability of H(G) is established for the class of locally planar graphs on arbitrary surfaces.

1 Introduction

Let G be a graph. The hypergraph H = H(G) with the same vertex set as G whose (hyper)edges are the maximal cliques of G is called the clique hypergraph of G. A k-coloring of H is a function c : V (H) → {1, …, k} such that no edge of H is monochromatic, i.e., |c(e)| ≥ 2 for every e ∈ E(H). The minimal k such that H admits a k-coloring is called the chromatic number of H and is denoted by χ(H). The reader can find more about this kind of colorings in [2, 5].

∗Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1-0502-0101-98.

A k-list-assignment of G is a function L which assigns to each vertex v ∈ V (G) a set L(v) (called the list of v) which has at least k elements. The elements of L(v) are called the admissible colors for v. An L-coloring of G (or H(G)) is a function c : V (G) → ∪_{v}L(v) such that c(v) ∈ L(v) for every v ∈ V (G) and no edge of G (or H(G)) is monochromatic. A coloring of H(G) is strong if no 3-cycle of G is monochromatic. G (or H(G)) is (strongly) kchoosable if, for every k-list-assignment L, there exists a (strong) L-coloring of G (or H(G)).

If G is a triangle-free graph, then H(G) = G. Hence, χ(H(G)) = χ(G). Grötzsch [4] (see also [5, 8, 9]) proved the following beautiful theorem.

Theorem 1.1 (Grötzsch) Every triangle-free planar graph is 3-colorable. Moreover, every 3-coloring of a 4- or 5-cycle of G can be extended to a 3-coloring of the whole graph.

In this paper we extend the Grötzsch Theorem by proving that the clique hypergraph of every planar graph is 3-colorable (Theorem 2.6). In Section 3 we extend Theorem 2.6 to list colorings by proving that H(G) is 4-choosable for every planar or projective planar graph G. This result is best possible since there are triangle-free planar graphs which are not 3-choosable [10]. As a side result it is also proved that every precoloring of a k-cycle (k ≤ 7) of a triangle-free graph can be extended to an L-coloring for an arbitrary 4-list-assignment L (Corollary 3.2). In the last section, 4-choosability of H(G) is established for the class of locally planar graphs on arbitrary surfaces.

All graphs in this paper are finite and simple. If U⊆V (G), then G(U) is the induced subgraph of G with vertex set U. If G is a plane graph and C is a cycle of G, then Int(C) denotes the subgraph of G consisting of C and all vertices and edges in the disk bounded by C. Similarly, Ext(C)⊆G is the exterior of C.

2 An extension of the Grötzsch Theorem

The Grötzsch Theorem 1.1 is easily extended to planar graphs with one triangle.

Corollary 2.1 Let G be a plane graph with precisely one 3-cycle C = xyz. Let c : V (C) → {1, 2, 3} be a coloring of H(C). Then c can be extended to a 3-coloring of H(G).

Proof. If two vertices of H(C) are colored the same, we may assume that these vertices are y and z. Subdivide the edge yz by inserting a vertex w of degree 2 and set c(w) ∈ {1, 2, 3}\{c(y), c(z)}. Now, apply Theorem 1.1 to extend c to Int(G) and Ext(G), respectively. Finally, observe that c is the required coloring of H(G).

Planar graphs which differ “the most” from triangle-free graphs contain triangles which cover all edges of the graph. For these graphs we can save one additional color as shown below.

Theorem 2.2 Let G be a planar graph with at least one edge such that each edge of G is contained in some 3-cycle of G. Then χ(H(G)) = 2.

Proof. By the 4-Color Theorem [1, 7], there is a 4-coloring of G. For i = 1, 2, 3, 4, let U_{i} ⊆ V (G) be the set of vertices colored i. Now, let c(v) = 1 if v ∈ U_{1} ∪ U_{2}, and let c(v) = 2 if v ∈ U_{3} ∪ U_{4}. Since every maximal clique K in G contains at least 3 vertices, K uses at least 3 colors in the 4-coloring of G, and hence c uses both colors on K. Therefore, c is a 2-coloring of H(G).

For the skeptics of the proof of the 4-Color Theorem and since we do not want to use this powerful theorem for our application if not necessary, we state a weaker result with an elementary proof:

Lemma 2.3 Let G be as in Theorem 2.2. Then H(G) has a strong 3coloring.

Proof. We use the same proof as for Theorem 2.2 except that we apply the 5-Color Theorem for planar graphs and set c(v) = 3 if v ∈ U_{5}.

A planar graph is a near-triangulation, if every facial walk, except possibly the outer walk, is a triangle.

Proposition 2.4 Let G be a connected plane graph without separating 3cycles.

(a) Suppose that no edge of G lies on exactly one 3-cycle. Then G is either a triangulation or a triangle-free graph.

(b) Let C be be the outer cycle of G. Suppose that no edge of E(G)\E(C) lies on exactly one 3-cycle. Then G is either a near-triangulation or G has no triangles except possibly C.

Proof. Note that each 3-cycle of G is the boundary of a face. If G is neither a (near-)triangulation nor a triangle-free graph (with possible exception C in case (b)), then there is a vertex u contained in some 3-cycle C′ (and C′ ≠ C in case (b)) such that the 3-cycles containing u do not form, locally, a (near) triangulation around u. Since all 3-cycles containing u are facial, there are at least two edges incident with u that are contained in precisely one 3cycle. Moreover, in case (b), one such edge is not on C. This contradiction completes the proof.

Lemma 2.5 Let G be a connected plane graph whose outer cycle C is a 3-cycle. Let c : V (C) → {1, 2, 3} be a coloring of H(C). Then c can be extended to a strong 3-coloring of H(G).

Proof. The proof is by induction on |V (G)| + |E(G)|. We may assume that G ≠ C. Let C′ be a 3-cycle of G (possibly C′ = C) such that C′ has at least one vertex in its interior but, subject to this condition, Int(C′) is as small as possible. Let G_{1} be the graph obtained from G by removing all vertices and edges in the interior of C′. By the induction hypothesis, there is a strong 3-coloring c_{1} of H(G_{1}) extending c. This 3-coloring induces a 3-coloring c′ of H(C′), since c_{1} is strong. If C′ ≠ C, then Int(C′) is smaller than G. Therefore, by the induction hypothesis, c′ can be extended to a strong 3-coloring of H(Int(C′)). Since every 3-cycle of G is either in G_{1} or in Int(C′), this gives rise to a strong 3-coloring of H(G) extending c.

Suppose now that C′ = C. Then G has no separating 3-cycles. Suppose that G has an edge e = uv where u ∉ V (C) such that e lies in exactly one 3-cycle C^{∗} = uvw. Since there are no separating triangles and since u ∉ V (C), C^{∗} is facial and different from C. Let v_{1}, v_{2}, …, v_{d} (d = deg(u)) be the neighbors of u enumerated in the clockwise order determined by the plane embedding of G. We may assume that v_{1} = v and v_{2} = w. Let k ≥ 2 be such that uv_{i}v_{i+1} are (facial) 3-cycles for i = 1, …, k − 1 but uv_{k}v_{k+1} (index taken modulo d) is not a 3-cycle in G. Since e lies in precisely one 3-cycle, k exists. Let G′ be the subgraph of G obtained by removing the edges uv_{2}, uv_{4}, uv_{6}, …, uv_{k} (if k is even) or uv_{2}, uv_{4}, uv_{6}, …, uv_{k−1} (if k is odd). By the induction hypothesis, H(G′) has a strong 3-coloring extending c. Observe that no edge among the edges uv_{1}, uv_{3}, uv_{5}, … belongs to a 3cycle in G′. Therefore the colors of v_{1}, v_{3}, v_{5}, … are distinct from the color of u. This easily implies that the 3-coloring of H(G′) is also a strong 3-coloring of H(G).

Now we may assume that G has no separating 3-cycles and that no edge in E(G)\E(C) belongs to exactly one 3-cycle in G. By Proposition 2.4(b), G is either a triangulation, or C is the only 3-cycle of G. In the latter case c can be extended to a (strong) 3-coloring of H(G) by Corollary 2.1. Otherwise, G is a triangulation of the plane. In particular, each edge of G belongs to a 3cycle in G. Lemma 2.3 implies that H(G) is (strongly) 3-colorable. Moreover, it is easy to use the 5-coloring of G from the proof of Lemma 2.3 (by possibly permuting the colors) so that the corresponding strong 3-coloring of H(G) is an extension of c. This completes the proof.

Theorem 2.6 The clique hypergraph of every planar graph is strongly 3colorable.

Proof. If G has a 3-cycle C, then color H(C) arbitrarily and extend the coloring to Int(C) and to Ext(C) (respectively) by applying Lemma 2.5. Otherwise, χ(H(G)) = χ(G) ≤ 3 by Theorem 1.1.

3 List-coloring planar and projective planar graphs

The main results of this section are Corollary 3.4 and Theorem 3.8 which extend Theorems 2.2 and 2.6, respectively, to list colorings. As mentioned before, we need one more color since there exist triangle-free planar graphs which are not 3-choosable [10].

Lemma 3.1 Let G be a planar graph and let C = x_{1}x_{2} ⋯ x_{k} be a k-cycle of G with k ≤ 7. Let L be a 4-list-assignment for G and let c be a mapping which assigns to each vertex of C a color from its list. Suppose that G contains no 3-cycle except possibly C. Then c can be extended to an L-coloring of G − E(G(V (C))).

Proof. Let G be a counterexample with |V (G)\V (C)| as small as possible. Then G is connected and without vertices of degree 1. By minimality, we may assume that C is the outer cycle of G. Similarly, C is an induced cycle and every vertex in V (G)\V (C) has degree at least 4. If k = 3, then we can subdivide an edge of C and arbitrarily color the new vertex. So, assume that k ≥ 4. If k ≥ 5, then we may as well assume that no two consecutive vertices of C have degree 2. Otherwise, we could contract the edge joining two vertices x_{i}, x_{i+1} of degree 2 and replace C by a (k −1)-cycle. A standard application of Euler’s formula shows that

∑_{i≥0}(4 − i)n_{i} + ∑_{i≥0}(4 − i)f_{i} = 8  (1)

where n_{i} is the number of vertices of degree i and f_{i} is the number of facial walks of length i. Since C is a facial k-cycle, f_{k} ≥ 1. Now, (1) implies that 2n_{2} + n_{3} ≥ k + 4. However, this inequality cannot be satisfied subject to the above assumptions on vertex degrees in G.

The first part of the following Grötzsch-type result was first observed by Kratochvíl and Tuza [6]. Every planar triangle-free graph has a vertex of degree at most 3, so it is easy to make the induction. On the other hand, the second part of Corollary 3.2 is a straightforward consequence of Lemma 3.1.

Corollary 3.2 Every triangle-free planar graph G is 4-choosable. Moreover, if L is a 4-list-assignment of G and C is a k-cycle of G with k ≤ 7, then every L-coloring of G(V (C)) can be extended to an L-coloring of G.

In what follows, we will need the next technical result.

Lemma 3.3 Let G be a plane graph with outer facial walk C = x_{1}x_{2} ⋯ x_{n}, let L be a 3-list-assignment of G, and let c be an L-coloring of x_{1} and x_{n} (possibly c(x_{1}) = c(x_{n})). Suppose that each edge with an endvertex in V (G)\V (C) lies on at least one 3-cycle. Then c can be extended to a strong L-coloring of H(G) (or H(G) − x_{1}x_{n} if c(x_{1}) = c(x_{n}) and x_{1}x_{n} ∈ E(H(G))) such that any two vertices of C, that are adjacent in G − x_{1}x_{n}, are colored differently.

Proof. Suppose that the theorem is false and G is a counterexample with |V (G)| as small as possible. We leave it to the reader to verify that G is 2-connected. Then C is a cycle. Suppose that C has a chord x_{i}x_{j} (i < j). Let G_{1} = Int(x_{j}x_{j+1} ⋯ x_{i}x_{j}) and G_{2} = Int(x_{i}x_{i+1} ⋯ x_{j}x_{i}). Then x_{1} and x_{n} are vertices of G_{1}. By the minimality of G, we can extend c to H(G_{1}). The resulting coloring has different colors on x_{i} and x_{j}. Then we can extend the induced coloring of c on {x_{i}, x_{j}} to H(G_{2}). This gives rise to a required strong coloring of H(G) (or H(G) − x_{1}x_{n}), a contradiction.

So assume that C is chordless. Let G′ = G − x_{n−1} and denote by C′ the outer walk of G′. Note that every edge of G′ with an endvertex in V (G′)\V (C′) lies on at least one 3-cycle of G, and that this 3-cycle is also contained in G′. By minimality, c can be extended to a strong L-coloring c̄ of H(G′) so that any two adjacent vertices of C′ are colored differently. Finally, let c̄(x_{n−1}) ∈ L(x_{n−1})\{c(x_{n}), c̄(x_{n−2})}. We claim that c̄ is a strong L-coloring of H(G) (or H(G) − x_{1}x_{n}). Suppose not. Then there exists a monochromatic edge xx_{n−1}. Since x ∉ V (C), there is a 3-cycle of G containing xx_{n−1}, and so there is a monochromatic triangle xx_{n−1}y. Since x and y are adjacent vertices and both belong to C′, this is not possible. This completes the proof.

Similarly as in Theorem 2.2 for usual colorings, we can save a color under an additional assumption. The following claim is an easy consequence of the above lemma.

Corollary 3.4 Let G be a planar graph such that each edge of G lies on some 3-cycle of G. Then H(G) is strongly 3-choosable.

In the sequel we shall use the following lemma whose easy proof is left to the reader.

Lemma 3.5 Let G be a graph such that no edge of G belongs to more than two 3-cycles in G. Let uv_{1} be an edge which belongs to exactly one 3-cycle uv_{1}v_{2} in G. Let P = v_{1}v_{2} ⋯ v_{k} be the maximal path in N(u) containing the edge v_{1}v_{2}. Let G′ be the subgraph of G obtained by removing the edges uv_{2}, uv_{4}, uv_{6}, …, uv_{k} (if k is even) or uv_{2}, uv_{4}, uv_{6}, …, uv_{k−1} (if k is odd). Then every (strong) coloring of H(G′) is also a (strong) coloring of H(G).

Lemma 3.6 Let G be a connected plane graph with outer cycle C = x_{1}x_{2} ⋯ x_{k} (k ≤ 7), let L be a 4-list-assignment of G, and let c(v) ∈ L(v) for v ∈ V (C). Then c can be extended to V (G) such that no edge of H(G) with a vertex in V (G)\V (C) and no 3-cycle of G with a vertex in V (G)\V (C) is monochromatic.

Proof. The proof is by induction on |V (G)| + |E(G)| and follows the same lines as the proof of Lemma 2.5. We may assume that G ≠ C and that C is chordless. Suppose first that G has a nonfacial 3-cycle C′. By the induction hypothesis, we first extend c to V (Ext(C′)) and afterwards extend the induced coloring of V (C′) to V (Int(C′)). It is easy to see that this gives the required extension of c.

Suppose now that G has only facial 3-cycles. Suppose that G has an edge e = uv_{1} where u ∉ V (C) such that e lies in exactly one 3-cycle. Let G′ be the subgraph of G as in Lemma 3.5. Note that V (G) = V (G′). By the induction hypothesis, we can extend c to V (G′). Finally observe that c is also the required extension for G.

Now we may assume that G has only facial 3-cycles and that no edge in E(G)\E(C) belongs to exactly one 3-cycle in G. By Proposition 2.4(b), G is either a near-triangulation, or G has no 3-cycles (except possibly C). In the latter case, c can be extended by Lemma 3.1. Otherwise, G is a near-triangulation of the plane, which we assume henceforth.

Suppose that a vertex v ∈ V (G)\V (C) has two neighbors x_{i}, x_{j} on C which are not consecutive vertices of C. Since k ≤ 7, there is a color a ∈ L(v) such that a = c(x) for at most one vertex x ∈ V (C). Set c(v) = a and apply induction on Int(C′) and Int(C′′) where C′ and C′′ are the cycles of C ∪ {x_{i}v, x_{j}v} different from C. By the choice of a and since G is a neartriangulation, the obtained extensions of c determine a required extension of c to V (G).

For i = 1, …, k − 1, let v_{i} be the vertex of G such that v_{i}x_{i}x_{i+1} is a 3-cycle of G (distinct from C). We say that a color a ∈ L(v_{i}) is bad if c(x_{i}) = c(x_{i+1}) = a. By the previous paragraph, each vertex v_{i} has at most one bad color in its list. Let L′′ be the 3-list-assignment of G which is obtained from L by removing bad colors from the lists L(v_{i}), i = 1, …, k −1. Let G′′ = G−{x_{2}, x_{3}, …, x_{k−1}} and apply Lemma 3.3 on G′′ and the reduced list-assignment L′′. We claim that the resulting strong coloring of H(G′′) (or H(G′′) − x_{1}x_{k}) determines the required extension of c. Suppose not. Then there is a monochromatic 3-cycle xyz (since every edge of G belongs to a 3-cycle) where z ∉ V (C). We may assume that x = x_{i}, 1 < i < k. Since L′′(z) contains no bad colors, y ∉ {x_{1}, …, x_{k}}. Therefore, yz is an edge on the outer facial walk of G′′. Since any two adjacent vertices on the outer walk of G′′ are colored differently, we have a contradiction.

In Theorem 3.8, we will use the following lemma.

Lemma 3.7 Suppose that G is a planar graph with outer cycle C of length 6. Suppose that every vertex and every edge of G lies on a path of length 3, but not on a path of length 2, which connects two diagonally opposite vertices of C. Then G − V (C) is a 3-choosable graph and every face of G is of size ≤ 6.

Proof. Observe that G−V (C) is an outerplanar graph. So it is 3-choosable. The fact that every face of G is of size ≤ 6 can be easily proved by induction on the number of paths of length 3 between diagonally opposite vertices of C.

Theorem 3.8 Let G be a graph embedded in the plane or the projective plane. Then H(G) is strongly 4-choosable.

Proof. Suppose that the theorem is false and that G is a minimum counterexample. Let L be a 4-list-assignment for G such that H(G) is not strongly L-colorable. We shall establish some additional properties of G.

(a) G has at least one facial 3-cycle. If every facial walk has length at least 4, then standard application of Euler’s formula (an inequality similar to (1)) shows that G contains a vertex v of degree at most 3. By minimality, H(G − v) has a strong L-coloring which can, obviously, be extended to a strong L-coloring of H(G).

(b) Every contractible 3-cycle of G is facial. This is an easy consequence of Lemma 3.6 and the minimality of G: First color the exterior of the 3-cycle, then extend the coloring into the interior of the cycle.

(c) G has no noncontractible 3-cycles. Suppose that C = xyz is a noncontractible 3-cycle of G. By cutting G along C, we get a plane graph G′ with the outer cycle C′ = x′y′z′x′′y′′z′′, where x′, x′′ correspond to x, etc. Let us observe that C′ is a chordless cycle of G′. Our goal is to prove that H(G) has a strong L-coloring, which would be a contradiction. This is true if H(G′) has a strong L-coloring such that x′ and x′′ (resp. y′ and y′′, z′ and z′′) have the same color, and such that vertices of every 3-path from x′ to x′′, from y′ to y′′, or from z′ to z′′ receive at least 2 different colors (so that the corresponding noncontractible 3-cycle in G is strongly colored).

Let a ∈ L(x), b ∈ L(y)\{a} and c ∈ L(z)\{a, b}. Color x′ and x′′ by a, y′ and y′′ by b, and color z′ and z′′ by c. Let G′′ be the subgraph of G′ which consists of precisely those vertices and edges which belong to some path of length 3 which connects two diagonally opposite vertices of C′. Note that C′ ⊆ G′′. (The possibility G′′ = C′ is not excluded). By Lemma 3.7, we can L-color the graph G′′ − V (C′). Finally for each inner face C′′ of G′′, extend the coloring of V (C′′) to Int(C′′) using Lemma 3.6. We claim that we have a strong L-coloring of H(G).

If D is a noncontractible 3-cycle of G, then it determines a path of length 3 between two diagonally opposite vertices of C′ in G′. If it uses an edge of C′, then it has at least two colors. Otherwise, an edge of D is in E(G′′ − V (C′)). Since G′′ − V (C′) has been L-colored as a graph, the colors of endvertices of that edge are distinct. If D is a contractible 3-cycle, it is contained in some Int(C′′). Clearly, C′′ cannot be monochromatic, so the coloring of Int(C′′) obtained by Lemma 3.6 uses at least two colors on D. Finally, consider an edge pq ∈ E(G) which is also an edge of H(G). Then pq is an edge in some Int(C′′) − E(C′′). Since pq is not contained in a 3-cycle of Int(C′′), the colors of p and q are distinct. This proves that we have a strong L-coloring of H(G).

(d) No edge of G belongs to exactly one 3-cycle. Because of (b) and (c), all 3-cycles in G are facial. This enables us to use Lemma 3.5 and minimality.

By (a)–(d), G is a triangulation of the projective plane with no subgraph isomorphic to K_{4}. By Euler’s formula, G has a vertex v of degree at most 5. By minimality, there is a strong L-coloring of H(G − v). Let L_{v} be the set of colors used on the neighbors of v at least twice. Then |L_{v}| ≤ 2. Since each face of G containing v is a 3-cycle, we may color v by any color in L(v)\L_{v} to get a strong L-coloring of H(G). This completes the proof.

4 List-coloring locally planar graphs

Let G be a graph embedded in a surface S. The edge-width ew(G) is the length of a shortest noncontractible cycle of G. (If there are no noncontractible cycles, then we set ew(G) = ∞. Observe that G is planar in such a case.) Recall that the Euler genus of the surface S is equal to 2 − χ_{S}, where χ_{S} denotes the Euler characteristic of S.

Lemma 4.1 Let G be a connected graph which is (2-cell) embedded in a surface of Euler genus g.

(a) If ew(G) ≥ 6g − 11, then G has a vertex of degree at most 6.

(b) If ew(G) ≥ 19g − 37, each facial walk has length at least 4, and G has no vertices of degree less than 4, then G contains a facial 4-cycle C whose vertices all have degree 4 in G.

Proof. If g = 0, then (a) is well-known and there are no graphs satisfying the assumptions of (b). Hence we may assume that ew(G) < ∞ and so |V (G)| ≥ ew(G).

By Euler’s formula and simple counting arguments, we have ∑(6−i)n_{i} ≥ 12 − 6g, where n_{i} is the number of vertices of degree i (i ≥ 0). If there are no vertices of degree 6 or less, then |V (G)| = ∑_{i≥7} n_{i} ≤ 6g − 12 and hence ew(G) ≤ 6g − 12. This proves (a).

To prove (b), we will apply the discharging method. A similar derivation as used to prove (1) shows that

∑_{i≥4}(4 − i)n_{i} + ∑_{i≥4}(4 − i)f_{i} = 8 − 4g  (2)

where f_{i} is the number of facial walks of length i. Give charge 4 − i to each vertex of G of degree i and to each face of G of size i. By (2), the total charge, taken over all vertices and faces equals 8 − 4g. Now, we redistribute the charge according to the following rules so that the total charge remains unchanged.

Rule 1. Every vertex v of degree 4 sends charge \frac{1}{5} to each face of size ≥ 5 that v is incident with.

Rule 2. Every vertex v of degree 4 sends charge \frac{2}{19} to all its neighboring vertices of degree ≥ 5.

Rule 3. Every vertex v of degree 4 sends charge \frac{1}{19} to all vertices of degree ≥ 5 which lie in a common 4-sided face F diagonally opposite to v in F.

It is easy to see that the charge of every face remains nonpositive. If u is a vertex of degree i ≥ 5, then its new charge is ≤ (4 − i) + \frac{3}{19}i ≤ −1 + \frac{15}{19} = \frac{−4}{19}. Now, we assume that there is no 4-sided facial cycle with all vertices of degree 4. If v is a vertex of degree 4 incident with a face of size more than 4, then its new charge is no more than −\frac{1}{5} − \frac{3}{19} < −\frac{4}{19}. If v is incident with 4 faces of size 4, then its new charge is again ≤ −\frac{4}{19}. The total charge is 8 − 4g. Hence:

8 − 4g ≤ −\frac{4}{19}|V (G)|

which implies that |V (G)| ≤ 19(g − 2).

Theorem 4.2 Let G be a graph embedded in a surface of Euler genus g. If ew(G) ≥ 19g − 34, then H(G) is strongly 4-choosable.

Proof. Suppose that the theorem is false and G is a minimal counterexample. Let L be the corresponding 4-list-assignment. If G′ is a subgraph of G, then ew(G′) ≥ ew(G). This implies that for every proper subgraph of G, H(G) is L-colorable. Then G has no vertices of degree less than 4. By Theorem 3.8 we may assume that g ≥ 2. Then ew(G) > 3, so every 3-cycle is contractible. The same argument as used to verify (b) in the proof of Theorem 3.8 shows that every 3-cycle of G is facial. Lemma 3.5 implies that every edge of G is either in none or in precisely 2 triangles of G. This implies that G is either triangle-free or a triangulation.

Suppose first that G is a triangulation. By Lemma 4.1(a), G has a vertex v of degree at most 6. By minimality, there is an L-coloring of H(G − v). Let L_{v} be the set of colors used on the neighbors of v at least twice. Then |L_{v}| ≤ 3. Since each face of G containing v is a 3-cycle, we may color v by any color in L(v)\L_{v} to get a strong L-coloring of H(G).

Suppose now that G is triangle-free. By Lemma 4.1(b), G has a facial 4-cycle C such that all its vertices have degree 4 in G. By minimality, Lcolor H(G − V (C)) = G − V (C). The resulting coloring c_{1} leaves at least two admissible colors on each vertex of C. Therefore, c_{1} can be extended to an L-coloring of G, a contradiction.

5 Some problems and remarks

Here we want to state the following problems, which we were not able to deal with at the moment. Let us denote by χ_{l}(H(G)) the minimum k such that H(G) is k-choosable.

Problem 5.1 Let a(S) be the smallest integer such that every triangle-free graph embeddable on the surface S has a vertex of degree at most a(S). Is it true that for every graph G embeddable on S, χ_{l}(H(G)) ≤ a(S) + 1?

Note that Theorem 3.8 answers this question in the positive when S is the plane or the projective plane. It may well be true that the maximum χ_{l}(H(G)) for graphs on a fixed surface S is comparable to the maximum chromatic number of triangle-free graphs on S (cf. Gimbel and Thomassen [3]).

Problem 5.2 Suppose that G is an arbitrary planar graph such that each edge lies on at least one 3-cycle. Is H(G) 2-choosable?

By Theorem 2.5, H(G) (from the above problem) is 2-colorable. This theorem relies on the 4-Color Theorem. So, it would be an interesting problem to find a direct proof of Theorem 2.5.

Kratochvíl (private communication) proved that 2-colorability of the hypergraph of maximal cliques of a graph is NP-complete. Even more, the problem remains NP-complete if we restrict to the class of perfect graphs. In our paper, we have considered mostly planar graphs. So, naturally, we encounter the following problem.

Problem 5.3 Is the problem of 2-coloring the clique hypergraph of planar graphs NP-complete?

Let us observe that 2-coloring of H(G) can be checked in polynomial time if either G is triangle-free or if every edge of G lies in a 3-cycle.

Acknowledgment. We are grateful to anonymous referee who pointed out a “hidden” error in an earlier version of the paper.

References

[1] K. Appel and W. Haken, Every planar map is four colorable, Contemporary Mathematics 98, AMS, 1989.

[2] G. Bacsó, S. Gravier, A. Gyárfás, M. Preissmann, and A. Sebö, About coloring the hypergraph of maximal cliques of a graph, manuscript.

[3] J. Gimbel and C. Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997) 4555–4564.

[4] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin Luther Univ. Halle-Wittenberg, Math. Naturwiss. Reihe 8 (1959) 109–120.

[5] T. R. Jensen and B. Toft, Graph Coloring Problems. Wiley Interscience, New York, 1995.

[6] J. Kratochvíl and Z. Tuza, Algorithmic complexity of list colorings, Discrete Appl. Math. 50 (1994) 297–302.

[7] N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The four-color theorem, J. Combin. Theory Ser. B 70 (1997) 2–44.

[8] R. Steinberg, The state of the three color problem. In J. Gimbel, J. W. Kennedy, and L. V. Quintas (editors), in Quo Vadis, Graph Theory?, Annals of Discrete Mathematics 55 211–248.

[9] R. Steinberg, An update on the state of the three color problem, Graph Theory Notes of NYAS XXV (J. W. Kennedy and L. V. Quintas, eds.) New York Academy of Sciences, 1993.

[10] M. Voigt, A not 3-choosable planar graph without 3-cycles. Discrete Math. 146 (1995) 325–328.