Alewyn P Burger
email: apburger@sun.ac.za.

Joy E Singleton

Further results on Maximal Nontraceable graphs of smallest size

Keywords: maximal nontraceable, xy-maximal nontraceable, z-maximal nontraceable, maximal nonhamiltonian

 22, 23, 30, 31, 38, 39, 40, 41, 42, 43, 46, 47, 48, 49, 50, 51} and they determined g(n) for n ≤ 9. We determine g(n) for 18 of the remaining 26 values of n, showing that g(n) = 3n-2 2 for n ≥ 54 as well as for n ∈ I ∪{18, 19, 20, 21, 24, 25, 26, 27, 28, 29, 32, 33} and

for n ∈ {10, 11, 14, 15, 16, 17}. We give results based on "analytic" proofs as well as computer searches.

Introduction

We consider only simple, finite graphs G and denote the vertex set, the edge set and the size (number of edges) of G by V (G), E(G) and e(G), respectively. We denote the complement of G by G. The degree of a vertex v in a graph G is denoted by d G (v). If no confusion can result we simply write d(v).

A vertex v ∈ V (G) is a universal vertex of G if it is adjacent to all vertices in G -v. The open neighbourhood of a vertex v in G is the set N G (v) = {x ∈ V (G) : vx ∈ E(G)}. The open neighbourhood of a subgraph H of G is the set N G (H) = {x ∈ V (G) -V (H) : vx ∈ E(G) for at least one v ∈ V (H)}.
If S is a nonempty subset of V (G), then S denotes the subgraph of G induced by S.

A graph G is hamiltonian if it has a Hamilton cycle (a cycle containing all the vertices of G), and traceable if it has a Hamilton path (a path containing all the vertices of G). A graph G is maximal nonhamiltonian (MNH) if G is not hamiltonian, but G + e is hamiltonian for each e ∈ E(G). A graph G is maximal nontraceable (MNT) if G is not traceable, but G + e is traceable for each e ∈ E(G). Let x and y be distinct vertices in G. Then G is xy-traceable if G is traceable between x and y, i.e. has a Hamilton path with x and y as endvertices. Also, G is xy-maximal nontraceable (xy-MNT) if G is not xy-traceable (xy-nontraceable), but G + e is xy-traceable for each e ∈ E(G). A graph G is z-traceable if it is traceable from z (i.e. there exists a Hamilton path with z as an endvertex), and it is z-maximal nontraceable (z-MNT) if G is not z-traceable, but G + e is z-traceable for each e ∈ E(G). A graph G is hypohamiltonian if it is not hamiltonian, but G -v is hamiltonian for every v ∈ V (G).

In [START_REF] Bollobás | Extremal graph theory[END_REF] Bollobás posed the problem of finding the least number of edges in an MNH graph of given order. This problem was solved by combined results given in [START_REF] Bondy | Variations on the hamiltonian theme[END_REF][START_REF] Clark | Smallest maximally nonhamiltonian graphs[END_REF][START_REF] Clark | Smallest maximally nonhamiltonian graphs ii[END_REF][START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF]. A similar problem was investigated for MNT graphs (also referred to as hamiltonian path saturated (HPS) graphs) as well as for m-path cover saturated (mPCS) graphs, which are generalizations of HPS graphs, in [START_REF] Dudek | Hamiltonian path saturated graphs with small size[END_REF][START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF][START_REF] Skupień | Hamiltonian circuits and path coverings of vertices in graphs[END_REF][START_REF] Skupień | Hamiltonian shortage, path partitions of vertices, and matchings in a graph[END_REF]. Suppose g(n) denotes the minimum number of edges of an MNT graph of order n. Frick and Singleton [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF] showed that g

(n) = 3n-2 2
for n ≥ 54 as well as for n ∈ I, where I = {12,

Preliminary results

For easy reference we include certain results from [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF].

Lemma 2.1 [8] If G is a connected MNT graph and v ∈ V (G) with d (v) = 2,
then the neighbours of v are adjacent. Also, one of the neighbours has degree at least 4 and the other neighbour has degree 2 or at least 4. Theorem 2.2 [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF] Suppose G is a connected MNT graph without vertices of degree 1 or adjacent vertices of degree 2. If G has order n ≥ 7 and m vertices of degree 2, then e(G) ≥ 1 2 (3n + m). We include the main steps of the proof of the following theorem, as the proofs of our main results relate to the construction and cases used in this proof.

Theorem 2.3 [8] If G is an MNT graph of order n, then e(G) ≥ 3n -2 2 for n ≥ 10. Proof: If G is not connected, then G = K k ∪ K n-k , for some positive integer k < n and then, clearly, e(G) > 3n-2 2
for n ≥ 10. Thus we assume that G is connected. We need to prove that the sum of the degrees of the vertices of G is at least 3n -2. In view of Theorem 2.2, we let

M = {v ∈ V (G) | d(v) = 2 and no neighbour of v has degree 2}.
The remaining vertices of degree 2 can be dealt with simultaneously with the vertices of degree 1. We let

S = {v ∈ V (G) -M | d(v) = 2 or d(v) = 1}.
Let m = |M | and s = |S|. If S = ∅, then it follows from Theorem 2.2 that e(G) ≥ 1 2 (3n + m). Thus we assume S = ∅.

We observe that, if H is a component of the graph S , then either H ∼ = K 1 or H ∼ = K 2 and N G (H) consists of a single vertex, which is a cut-vertex of G.

An example of such a graph G is depicted in Figure 1.

0 0 1 1 00 11 0 1 0 1 0 1 K 2 G -S K 1 Fig. 1: Example of G
Since G is MNT the graph S has at most three components. We consider three cases: Case 1. S has exactly three components, say H 1 , H This case is a Zelinka Type I construction, cf. [START_REF] Zelinka | Graphs maximal with respect to absence of hamiltonian paths[END_REF].

Case 2.2. N G (H 1 ) = N G (H 2 ): Let N G (H i ) = y i , i = 1, 2 and y 1 = y 2 . Then y 1 y 2 ∈ E(G).
Now G -S is not complete. If v and w are nonadjacent vertices in V (G -S), then (G -S) + vw has a Hamilton cycle containing y 1 y 2 . Hence G -S is either hamiltonian or MNH. We consider these two cases separately: Case 2.2.1. G -S is hamiltonian:

We note that no Hamilton cycle in G -S contains y 1 y 2 , otherwise G would be traceable. Also d G-S (y i ) ≥ 3 for i = 1, 2. We have

e(G) = e(G -M -S) + 2m + 2s -2 ≥ 1 2 (3n + m + s -4) . (1)
Case 2.2.2. G -S is nonhamiltonian, i.e. G -S is MNH:

We have e(G) = e(G -S) + 2s -2 ≥ 1 2 (3n + s -4).

(2)

Case 3. S has exactly one component, say H: We introduce the following terminology which we require in proving certain results in order to show that g(10

Since v∈S d G (v) = 3s -2, for s = 1, 2 it follows that e(G) = e(G -M ) + 2m = 1 2   v∈V (G-M )-S d G-M (v) + v∈S d G-M (v)   + 2m ≥ 1 2 (3 (n -m -s) + 3s -2) + 2m. Hence e(G) ≥ 1 2 (3n + m -2) . (3
) = 15. A vertex v in a subgraph H of a graph G is an attachment vertex of H if v has a neighbour in V (G) - V (H). The circumference c(G) of a graph G is the order of a longest cycle in G. We suppose that a cycle C has an orientation. If u, v ∈ V (C)
= z. If y is adjacent to u ∈ V (C) and z is adjacent to v ∈ V (C), u = v, then |V (C(u, v))| ≥ |V (P )| and |V (C(u, v))| ≥ |V (P )|. Proof: Suppose |V (C(u, v))| < |V (P )|. Then C = C[u, v]zLyu is a cycle such that |V (C )| > |V (C)| which is a contradiction since C is a circumference cycle. A similar argument holds if |V (C(u, v))| < |V (P )|. 2
The following lemma is a direct result of Lemma 2.5.

Lemma 2.6 Suppose c(G) = k. Let C be a circumference cycle of G. Suppose u, v ∈ V (G -V (C)) are endvertices of a path in G -V (C) of order at least k 2 . If both u and v are attachment vertices of G -V (C), then |N C ({u, v})| = 1.
We also require the following lemma in order to prove g(10) = 15.

Lemma 2.7 Suppose G is a graph of order 10 as described in Case 3 of Theorem 2.3, with

H ∼ = K 1 and d G (v) = 3 for all v ∈ V (G) -S. Then G -S is 2-connected.
Proof: Suppose G -S has a cut vertex y and that G has the structure as depicted in Figure 2. Consider G + zy. Since G + zy is traceable it follows that B is traceable from y. If B is not complete, then A is traceable between x and y making G traceable. Hence B is complete.

If B = K 3 , then G has two vertices of degree 2, and if B = K 4 , then d G (y) > 3, both of which lead to contradictions.

Hence G -S is 2-connected. 2

xy-MNT and z-MNT graphs

In this section we investigate some properties of xy-MNT and z-MNT graphs and show how these graphs can be used in constructing MNT graphs. We also present some xy-MNT graphs of small order and smallest size, as well as some cubic xy-MNT graphs of larger orders.

Lemma 3.1 Suppose F is an xy-MNT graph. (a) Then xy ∈ E(F ). (b) If x is not a universal vertex of F , then F -x is traceable from y. (c) If N (x) ∩ N (y) = ∅, then F -{x, y} is traceable from every vertex in V (F ) -{x, y}.
Proof:

(a) If xy / ∈ E(F ), then F + xy is not xy-traceable. (b) Suppose z / ∈ N (x).
Then F +xz has a Hamilton path xzQy and consequently F -x has a Hamilton path zQy. Hence F -x is traceable from y. (a) Then w is nonadjacent to x and y.

(c) Let u ∈ V (F ) -{x, y}. Since N (x) ∩ N (y) = ∅ it follows that ux / ∈ E(F ) or uy / ∈ E(F ). Suppose ux / ∈ E(F ). Then F +
(b) If N (w) = {v 1 , v 2 } and d(v i ) = 4 for i = 1, 2, then v 1 , v 2 ,
x, y is not complete.

Proof:

(a) Suppose w is adjacent to x and u / ∈ N (x). Then F + xu is not xy-traceable, a contradiction. A similar argument holds if w is adjacent to y.

(b) Suppose d(v i ) = 4 for i = 1, 2 and v 1 , v 2 , x, y is complete. Then F + xw is not xy-traceable, a contradiction. 2
Lemma 3.3 Suppose F is a z-MNT graph with n ≥ 5, where z is not a universal vertex and w ∈ V (F ) -{z} with d(w) = 2.

(a) Then w is nonadjacent to z. We also established, by computer, that the smallest MNH graphs G 14 of order 14 and size 22, and G 15 of order 15 and size 24 (see Figure 7) given in [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF] are in fact xy-MNT. A similar search for z-MNT graphs of minimum size was undertaken for orders up to 12. We noted that for 7 ≤ n ≤ 12 all z-MNT graphs of minimum size can be constructed from xy-MNT graphs of minimum size in one or both of the following ways:

(b) If N (w) = {v 1 , v 2 } and d(v i ) = 4 for i = 1, 2, then v 1 , v 2 , z is not complete. Proof: (
(1) Attach a K 1 to x (or y) of a smallest xy-MNT graph of order n -1.

(2) Attach a K 2 to x (or y) of a smallest xy-MNT graph of order n -2. If K i , i = 1, 2 is attached to x (or y), then z is y (or x).

We therefore do not include sketches of these graphs. [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF]. Each of the MNH graphs of orders 12 and 13 have one more edge than the corresponding MNH graphs of smallest size listed in [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF] (b) N Fj (x) ∩ N Fj (y) = ∅ for j ∈ {5, 6, 6 * , 7, 7 * , 9, 12 * , 13, 13 * }. In these cases it is easy to check that [F j , H x , H y ] is MNT.

(c) The graph F * 7 is also a z-MNT graph (but not of smallest size), where z is the universal vertex.

(d) The xy-MNT graphs F 5 , F 6 , F 8 and F 10 were used in [START_REF] Bullock | Maximal nontraceable graphs with toughness less than one[END_REF] and [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF] to construct smallest size MNT graphs of orders 7, 8, 9, 10, 12 and 13.

(e) In F 10 and in G 15 , x and y can be any two adjacent vertices of the graphs.

A cubic xy-MNT graph with N (x) ∩ N (y) = ∅ of order n can be used to construct an MNT graph of order n = n + 2 or n = n + 3 by attaching a K 1 to x and a K 1 or K 2 to y. These MNT graphs realise the lower bound 3n -2

2

. This is the construction used by Dudek, Katona and Wojda in [START_REF] Dudek | Hamiltonian path saturated graphs with small size[END_REF] to produce MNT graphs of order n and size 3n-2 2 for n ≥ 54 as well as for n ∈ {22, 23,30,31,38,39,40,41,42,43,46,47,48,49,50, 51}. This fact motivated us to search for cubic xy-MNT graphs of relevant orders. We used cubic graphs from Gordon Royle's Collection of small graphs (cf. [START_REF] Royle | Gordon Royle's Small graphs[END_REF]) and found xy-MNT graphs for orders 16, 18 and 22 (see Figure 8), but none of order 14. We also found xy-MNT graphs of orders 24, 26 and 30 (see Figure 9) from Brendan McKay's collection of cubic hypohamiltonian graphs (cf. [START_REF] Mckay | Combinatorial data page[END_REF]). We label these graphs Q i , where i is the order of the graph. (a) The graphs Q i , i = 16, 18, 22, 24, 26, 30 all have N (x) ∩ N (y) = ∅ and neither x nor y is a universal vertex of Q i .

(b) The graphs Q 16 , Q 18 are hamiltonian. This is to be expected since the smallest MNH graphs of orders 16 and 18 listed in [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF] have 25 and 28 edges respectively.

(c) In Q 30 , x and y can be any two adjacent vertices of the graph and in Q 22 , Q 24 and Q 26 , where applicable, x, y can be x , y or x , y .

(d) There are no cubic xy-MNT graphs of order 14.

Main Results

In this section we determine g(n) for n = 10, 11, 14 -21, 24 -29, 32, 33. Proof: Let F = Q i for i = 16, 18, 22, 24, 26, 30, H x = K 1 and H y = K 1 or H y = K 2 . The result then follows from Theorems 2.3 and 3.4 and Remark 3.6(a). 2

We now prove that g(n) = 3n 2 for n = 10, 11, 14, 15, 16, 17. We prove g(n) = 3n 2 for n = 10 as a separate theorem using "analytic" arguments. Alternatively, this result can be obtained by using computer results. The cases n = 11, 14, 15, 16 and 17 are proved using computer results. Proof: According to Theorem 2.3, g(10) ≥ 14. Suppose G is an MNT graph of order 10 and size 14. We define M , S, m and s as in Theorem 2.3. It follows from Theorem 2.2 that s = 0. We consider the various cases given in the proof of Theorem 2.3.

Case 1 ( S has 3 components)

The smallest graph of order 10 for this case is the Zelinka type II graph depicted in Figure 10 which has 15 edges. Case 2 ( S has 2 components, H 1 and

H 2 ) Case 2.1 N G (H 1 ) = N G (H 2 )
According to Remark 2.4(b) we need not consider this case.

Case 2.2 N G (H 1 ) = N G (H 2 ) Case 2.2.1 G -S is hamiltonian
From inequality (1) of Section 2 it follows that the only values of m and s that may produce an MNT graph G of order 10 and 14 edges are m = 0 and s = 2, i. e. G -S has no vertices of degree 2. Hence G -S is a cubic xy-MNT graph of order 8. We show that no such graph G -S exists. The subgraphs G s of G can have one of the three structures depicted in Figure 11. From inequality (2) of Section 2 it follows that the only value of s that may produce an MNT graph G of order 10 and 14 edges is s = 2.

According to [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF] the smallest MNH graph of order 8 has 15 edges and thus e(G) > 14. Thus we only consider s = 1, i. e. H ∼ = K 1 . Then, according to Lemma 2.7, G -S is 2-connected. Let z denote the vertex adjacent to H in G, and F = G -S. Then d F (z) = 2 and the other 8 vertices of F must have degree 3 each. Note that F is not traceable from z, otherwise G will be traceable. We show that such a graph G does not exist by attempting to construct F by considering circumference cycles of F .

Let C be a circumference cycle of F . We define, respectively, the degree deficiency, dd(C), of C, and the degree deficiency, dd(F -

V (C)), of F -V (C) in F as dd(C) = v∈V (C) d F (v) -2|V (C)|
and determine possible degree sequences for such graphs. In most cases, for the sake of brevity, we will only state the degree sequence(s) of G and the relevant lemma(s) used for the computation. When determining the degree sequences for G, we use Lemmas 2.1, 3.2(a) and 3.3(a), and the fact that d(v) ≥ 3 for v ∈ V (G) -S -M . In the case where G -S is a hamiltonian xy-MNT graph we use the fact that d G-S (x) ≥ 3 and d G-S (y) ≥ 3 (see Case 2.2.1 of Theorem 2.3). For all cases, no graphs with the relevant degree sequences were found when doing a computer search and hence we do not state this in every case. Case I: n = 11 Suppose G =[F, H z ] is an MNT graph of order 14 and size 20. Then from inequality (3) of Section 2 we can only have m = 0. We consider subcases according to possible values of s.

(i) m = 0 and s = 1: The only possible degree sequence is 13 13 and we use Lemma 4.4(a) in our computation.

(ii) m = 0 and s = 2: It follows from We first consider the case where G -S is an xy-MNT graph and G -S is MNH. The smallest such MNT graph of order 16 has G 14 as subgraph and has 24 edges. We now assume G -S is hamiltonian. It follows from inequality (1) of Section 2 that m + s ≤ 2. Thus m = 0 and s = 2, and the only possible degree sequence is 113 12 44 since d G-S (x) ≥ 3 and d G-S (y) ≥ 3. Hence G-S must be cubic. Applying Lemma 4.3(a) and a computer search, no graph was found.

Conclusion

The smallest size of an MNT graph of order n has now been determined for all except 8 values of n, namely n ∈ K = {34, 35, 36, 37, 44, 45, 52, 53}. The minimum size of MNT graphs of order n ≥ 18, where n / ∈ K, is 3n-2 2 and graphs of this size are constructed from cubic xy-MNT graphs. We suspect that g(n) = 3n-2 2 also for n ∈ K and that these remaining cases could be resolved by finding cubic xy-MNT graphs of orders 32, 34, 42 and 50 either by construction or by the use of more sophisticated algorithms.

) 2 Remark 2 . 4

 224 We note the following:(a) If G is an MNT graph as described in Case 1 of Theorem 2.3, then e(G) > 3n 2 if n > 10. (b) If G isan MNT graph as described in Case 2.1 of Theorem 2.3, then e(G) > 3n 2 if n > 8. (c) The subgraphs G -S in Cases 2.2.1 and 2.2.2 are y 1 y 2 -MNT graphs. The subgraph G -S in Case 3 is a z-MNT graph, where z = N G (H).

  we denote the path on C from u to v (with same orientation as C) by C[u, v] and the other path on C from u to v by C[u, v]. The paths obtained by deleting the endvertices u, v are denoted by C(u, v) and C(u, v), respectively. Lemma 2.5 Suppose C is a circumference cycle of a graph G and G -V (C) has a path P = yLz with endvertices y and z, where we also consider V (L) = ∅ as well as y

Fig. 2 :

 2 Fig. 2: Sketch for Lemma 2.7

Fig. 3 :

 3 Fig. 3: Smallest xy-MNT graphs of order 5 (6 edges) and order 6 (9 edges)

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Smallest xy-MNT graphs of order 7 (12 edges) and of order 8 (13 edges)

Fig. 7 :

 7 Fig. 7: Smallest maximal nonhamiltonian graphs G14 and G15

Fig. 8 :Fig. 9 :Remark 3 . 6

 8936 Fig. 8: Cubic xy-MNT graphs of order 16, 18 and 22

Theorem 4 . 1 2 .

 412 For n ∈ {18, 19, 20, 21, 24, 25, 26, 27, 28, 29, 32, 33}, g(n) = 3n-2

Theorem 4 . 2

 42 The minimum size of an MNT graph of order 10 is 15.

Fig. 10 :

 10 Fig. 10: Zelinka type II graph of order 10

Fig. 11 :

 11 Fig. 11: Structures of Gs

Case 3 (

 3 S has 1 component, H) According to inequality (3) of Section 2 the only possibility for a graph of order 10 to have 14 edges is when m = 0, i. e. when d G (v) = 2 for all v ∈ V (G) -S. For s = 1, e(G) = 14 ⇐⇒ d G (v) = 3 for all v ∈ V (G) -S. For s = 2, taking Lemma 2.1 into account, we have e

Tab. 2 :

 2 m s degree sequence Lemma used for computer search 0 1 13 13 4 4.4(b) if d G (z) = 3 with d(u) = 4; 4.4(a) if d G (z) Subcases for n = 15, where G -S is z-MNTWe have thus shown that g(15) = 23. The graphs [F 13 , K 1 , K 1 ], [F 13 * , K 1 , K 1 ], [F 12 , K 1 , K 2 ], [F 12 * , K 1 , K 2 ] and [F 11 , K 2 , K 2 ]are examples of MNT graphs of order 15 and size 23.Case IV: n = 16We show that no MNT graph G of order 16 and size 23 exists.

  [START_REF] Skupień | Hamiltonian shortage, path partitions of vertices, and matchings in a graph[END_REF] 22, 23, 30, 31, 38, 39, 40, 41, 42, 43, 46, 47, 48, 49, 50, 51} and determined g(n) for n ≤ 9. In this paper we show that g(n) = 3n 2 for n = 10, 11, 14, 15, 16, 17 and g(n) = 3n-2 2 for n ∈ {18, 19, 20, 21, 24, 25, 26, 27, 28, 29, 32, 33} and supply graphs having the minimum number of edges.Many MNT graphs have either xy-MNT graphs or z-MNT graphs as subgraphs and thus we have a section devoted to xy-MNT graphs and z-MNT graphs of smallest size.

  2 , H 3 : In this case the neighbourhoods of H 1 , H 2 , H 3 are pairwise disjoint, G -S is a complete graph of order at least 4 and hence

	e(G) =	n -s 2	+ 2s -3 for s = 3, 4, 5 or 6.
	This case is a Zelinka Type II construction, cf. [14].
	Case 2. S has exactly two components, say H 1 , H 2 :
	There are two subcases.
	Case 2.1. N G (H 1 ) = N G (H 2 ):
	Then G -S is a complete graph and hence
	e(G) =	n -s 2	+ 2s -2 for s = 2, 3 or 4.

  ux has a Hamilton path xuP y, and hence uP is a Hamilton path of F -{x, y}, i. e. F -{x, y} is traceable from u. A similar proof holds if uy / ∈ E(F ).

2

Lemma 3.2 Suppose F is an xy-MNT graph with n ≥ 6, where neither x nor y is a universal vertex and w ∈ V (F ) -{x, y} with d(w) = 2.

  Table 1 gives the minimum sizes of xy-MNT graphs and z-MNT graphs of orders up to 15 and 13 respectively. The xy-MNT graphs F 8 , F 11 , F 12 and F 13 are hamiltonian whereas the others in Figures 3-6 are MNH. The MNH ones for orders 5, 6, 7, 9 and 10 are those listed as the MNH graphs of smallest size in

	Remark 3.5 We note the following:
	(a)
	n	5 6 7	8	9 10 11 12	13	14	15
	Smallest xy-MNT 6 9 12 13 15 15 17 19	21	≤ 22 ≤ 24
	Smallest z-MNT	5 7 9 12 14 16 16 18 ≤ 20
	Tab. 1: Sizes of smallest xy-MNT and z-MNT graphs

  According to Table 1 the smallest MNT graphs of order 11 which can be constructed from xy-MNT or z-MNT graphs have 17 edges. Hence g(11) = 17. The graphs [F 8 , K 1 , K 2 ] and [F 9 , K 1 , K 1 ] are examples of such graphs. Case II: n = 14 From Table 1 it follows that the smallest MNT graph of order 14 that can be constructed from an xy-MNT graph has 21 edges.

  Table 1 that the minimum number of edges is 21. We have shown that g(14) = 21. The graphs [F 12, K 1 , K 1 ], [F * 12 , K 1 , K 1 ], [F 11 , K 1 , K 2 ] and [F 10 , K 2 , K 2 ]are examples of MNT graphs of order 14 and size 21. Case III: n = 15 From Table 1 it follows that the smallest MNT graph of order 15 that can be constructed from an xy-MNT graph has 23 edges. Suppose G =[F, H z ] is an MNT graph of order 15 and size 22, where F is a z-MNT graph. Then from inequality (3) of Section 2 we have m ≤ 1. Table 2 summarizes the possible subcases.

Acknowledgements

We wish to express our thanks to Dr Marietjie Frick who initiated this work and for her helpful comments on our draft manuscript.

Research towards this paper was supported financially by the South African National Research Foundation under grant number GUN 77248.

We consider the following construction.

Construction 1: Suppose F is an xy-MNT graph and H x ∼ = K n and H y ∼ = K m , for positive integers n and m. Suppose the vertex sets V (F ), V (H x ) and V (H y ) are disjoint. Then [F, H x , H y ] denotes the graph obtained by joining each vertex of H x to x and each vertex of H y to y. Theorem 3.4 Suppose F is an xy-MNT graph and neither x nor y is a universal vertex of F . If N F (x) ∩ N F (y) = ∅, then G = [F, H x , H y ] is MNT.

Proof: Since F is not xy-traceable it follows that G is not traceable. We now prove that G + uv is traceable for all u, v ∈ V (G), where uv / ∈ E(G). Suppose that u, v ∈ V (F ). Since F + uv has a Hamilton path between x and y it follows that G + uv is traceable.

Suppose u ∈ V (H x ) ∪ {x} and v ∈ V (H y ). Then, since x is not a universal vertex it follows from Lemma 3.1(b) that there is a Hamilton path in G + uv.

Suppose u ∈ V (H x ) and v ∈ V (F ) -{x, y}. Then, from Lemma 3.1(c), there is a Hamilton path in G + uv.

All other cases for u and v follow from symmetry.

2

We now consider z-MNT graphs. It follows from the definition that if F z is a z-MNT graph, then F z -z is traceable from each v / ∈ N F z (z), but not traceable from any u ∈ N F z (z).

Construction 2: Suppose F z is a z-MNT graph and H z ∼ = K n . Suppose the vertex sets V (F z ) and V (H z ) are disjoint. Then [F z , H z ] denotes the graph obtained by joining each vertex of H z to z.

It is easy to see that the graph

Suppose F is an xy-MNT graph and F z is a z-MNT graph, where x and z are universal vertices and [F, H x , H y ] and [F z , H z ] are MNT graphs of order n ≥ 10. Then V (F ) ∪ V (H y ) -x and F z -z are themselves MNT. If each of H x , H y and H z is either a K 1 or K 2 , then by using Theorem 2.3 and results for the minimum size of MNT graphs of orders less than 10 given in [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF] it is not difficult to check that [F, H x , H y ] and [F z , H z ] have size greater than 3n 2 . Thus, since smallest MNT graphs of a specific order may arise from xy-MNT or z-MNT graphs, we searched, with the aid of a computer, for xy-MNT and z-MNT graphs of given order and smallest size in which neither x nor y nor z is a universal vertex. The algorithm for xy-MNT graphs F of order n starts with an initial graph of order n that is necessarily a subgraph of any xy-MNT graph of order n. From Lemmas 3.1(a) and (b) we choose an n-path of the form xyQ as the initial graph. The algorithm then performs a depth-first tree search, systematically adding all possible combinations of edges, but keeping the graph xy-nontraceable. When a predetermined upper bound on the number of edges is reached, that branch is terminated.

We could find all xy-MNT graphs of minimum size of order 5 up to 13 in reasonable computing time. These graphs are depicted in the Figures 3456

Since F is connected dd(F -V (C)) > 0 and thus

Since F is not traceable from z it follows that c(F ) ≤ 8. Suppose C is a circumference cycle of F of order k ≤ 8. We denote the vertices on C in an anti-clockwise direction by x 0 , x 1 , ..., x k-1 , where

Since similar techniques are used in proving the cases c(F ) = 8 and c(F ) = 7 as in the case c(F ) = 6, we only prove the following:

Now dd(C) = 5 and the only graphs v 0 , v 1 , v 2 with 0 < dd( v 0 , v 1 , v 2 ) ≤ 5 are P 3 and K 3 . Each of P 3 and

and v i and v j are endvertices of a path of order 3. Since, according to Lemma 2.7, F is 2-connected it follows that v i and v j have distinct neighbours on C which contradicts Lemma 2.6. Hence d

Now dd(C) = 6 and the only graphs z, v 1 , v 2 with 0 < dd( z, v 1 , v 2 ) ≤ 6 are K 1 ∪ K 2 , P 3 and K 3 . Using reasoning similar to that in (a) it can be seen that z, v 1 , v 2 cannot be isomorphic to P 3 or

Then d F (w 3 ) = 3. Then, according to Lemma 2.5 we may assume w 2 x 0 , w 3 x 3 ∈ E(F ), but then w 3 x i / ∈ E(F ) for i = 1, 2, 4, 5 and hence d F (w 3 ) < 3. c(F) at most 5

Clearly at least one component of F -V (C), say A, has at least two vertices. Then there are two distinct vertices in A which, since F is 2-connected, have distinct neighbours on C. This contradicts Lemma 2.6.

Thus g(10) ≥ 15 and since there exist MNT graphs of order 10 and size 15 (for example, the graph in Figure 10 and [F 8 , K 1 , K 1 ] which was first reported in [START_REF] Bullock | Maximal nontraceable graphs with toughness less than one[END_REF]) it follows that g(10) = 15. 2

In the proof of Theorem 4.5 we will consider degree sequences of graphs. Since all values in the degree sequences that we consider are less than 10, we will use, for example, the notation 123 4 4 for a graph having degrees 1, 2, 3, 3, 3, 3, 4. We use a computer search using the same algorithm as described in Section 3, but with a restriction on the degree sequence of a specific path, where we define the degree sequence of a path

These extra restrictions enabled the relevant searches to be completed in a reasonable time. The following two lemmas describe the paths used for different cases in the computer algorithms. (a) There is a Hamilton path P in F -z.

a Hamilton path P v i wv j , where {i, j} = {1, 2}.

Proof:

(a) and (b) are obvious.

(c) From Lemma 3.3(b) v 1 and v 2 are not both adjacent to z. Say v j is not adjacent to z for j ∈ {1, 2}.

Then F + zv j must be z-traceable. Therefore there is a Hamilton path zv j wv i P in F . (Note the path cannot end in w, otherwise F -z is hamiltonian, making F z-traceable.) Therefore F -z has a Hamilton path P v i wv j , where {i, j} = {1, 2}. Proof: According to Theorem 2.3, g(n) ≥ 3n-2 2

for n ≥ 10. In order to show that there are no MNT graphs of order n and size 3n-2 2 for n = 11, 14, 15, 16 and 17, it follows from Theorem 2.2 and Remarks 2.4(a) and (b), that we need only consider Cases 2.2 and 3 of Theorem 2.3. This implies from Remark 2.4(c) that we need only consider MNT graphs constructed from xy-MNT and z-MNT graphs. In some cases we are able to use Table 1 to determine the minimum size of an MNT graph of a specific order constructed from an xy-MNT graph and/or a z-MNT graph of minimum size. If not, we consider values of m and s that could possibly produce MNT graphs G of order n with 3n-2 2 edges We next consider the case where G-S is a z-MNT graph. If such a graph exists then from inequality (3) of Section 2 we have m = 0. The possible subcases are:

(i) m = 0 and s = 1: The degree sequence is 13 15 and we use Lemma 4.4(a).

(ii) m = 0 and s = 2: No degree sequence for G is possible.

We have thus shown that g(16) = 24 and that [G 14 , K 1 , K 1 ] is an MNT graph with order 16 and size 24 (see Figure 7). Case V: n = 17 We show that no MNT graph G of order 17 and size 25 exists. We first consider the case where G -S is an xy-MNT graph and G -S is MNH. The smallest such MNT graphs of order 17 have either G 14 or G 15 as subgraphs and have 26 edges. We thus need to consider the case where G -S is a hamiltonian xy-MNT graph in which case m + s ≤ 3 (inequality (1)); and the case where G -S is a z-MNT graph in which case m ≤ 1 (inequality (3)). Obviously, there can be some doubt about the correctness of an algorithm when no graphs are found. The fact that MNH graphs of certain orders that were found in [START_REF] Lin | On smallest maximally nonhamiltonian graphs[END_REF] were also found with this algorithm is reassuring. Furthermore, since the algorithm does not take into account isomorphisms of graphs, it is unlikely that a graph would be missed since the algorithm has usually more than one chance to find a graph if it exists. The source code for the algorithm can be viewed at [START_REF] Burger | Maximal nontraceable graphs[END_REF].

We summarize the results contained in [START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF] and in Theorems 4.1, 4.2 and 4.5 in the following theorem: for n ≥ 10, n / ∈ J ∪ K where K = {34, 35, 36, 37, 44, 45, 52, 53}.


Luis Barba

Ruy Fabila-Monroy

Dolores Lara

Jesús Leaños

Cynthia Rodríguez

Gelasio Salazar

Francisco J Zaragoza

The Erd ős-S ós Conjecture for Geometric Graphs †

Keywords: extremal graph theory, geometric graph, spanning tree

Let f (n, k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that

For the case when k = n, we show that 2 ≤ f (n, n) ≤ 3. For the case when k = n and G is a geometric graph on a set of points in convex position, we completely solve the problem and prove that at least three edges must be removed.

Introduction

One of the most notorious problems in extremal graph theory is the Erdős-Sós Conjecture, which states that every simple graph with average degree greater than k -2 contains every tree on k vertices as a subgraph. This conjecture was recently proved true for all sufficiently large k (unpublished work of Ajtai, Komlós, Simonovits, and Szemerédi).

In this paper we investigate a variation of this conjecture in the setting of geometric graphs. Recall that a geometric graph G consists of a set S of points in the plane (these are the vertices of G), plus a set of straight line segments, each of which joins two points in S (these are the edges of G). In particular, any set S of points in the plane in general position (no three of its points are collinear) naturally induces a complete geometric graph. For brevity, we often refer to the edges of this graph simply as edges of S. If S is in convex position then G is a convex geometric graph. A geometric graph is planar if no two of its edges cross each other. An embedding of an abstract graph H into a geometric graph G is an isomorphism from H to a planar geometric subgraph of G. For r ≥ 0, an r-edge is an edge of G such that in one of the two open semi-planes defined by the line containing it, there are exactly r points of G. The convex hull of S is the intersection of all convex sets containing S. We will frequently need to refer to the vertices and edges at the boundary of the convex hull of S, which for brevity we will denote simply as convex hull vertices and convex hull edges of S.

In this paper all point sets are in general position and G is a complete geometric graph on n points. It is well known that for every integer 1 ≤ k ≤ n, G contains every tree on k vertices as a planar subgraph [START_REF] Bose | Optimal algorithms to embed trees in a point set[END_REF]. Even more, it is possible to embed any such tree into G, when the image of a given vertex is prespecified [START_REF] Ikebe | The rooted tree embedding problem into points in the plane[END_REF].

Let F be a subset of edges of G, which we call forbidden edges. If T is a tree for which every embedding into G uses an edge of F , then we say that F forbids T . In this paper we study the question of what is the minimum size of F so that there is a tree on k vertices that is forbidden by F . Let f (n, k) be the minimum of this number taken over all complete geometric graphs on n points. As

f (2, 2) = 1, f (3, 3) = 2, f (4, 3) = 3, f (4, 4) = 2 and f (n, 2) = n
2 , we assume through out the paper that n ≥ 5 and k ≥ 3.

We show the following bounds on f (n, k).

Theorem 1.1 1 2 n 2 k -1 - n 2 ≤ f (n, k) ≤ 2 n(n -2) k -2 Theorem 1.2 2 ≤ f (n, n) ≤ 3
In the case when G is a convex complete geometric graph, we show that the minimum number of edges needed to forbid a tree on n vertices is three.

An equivalent formulation of the problem studied in this paper is to ask how many edges must be removed from G so that it no longer contains every planar subtree on k vertices. A related problem is to ask how many edges must be removed from G so that it no longer contains any planar subtree on k vertices. For the case of k = n, in [START_REF] Károlyi | Ramsey-type results for geometric graphs[END_REF], it is proved that if any n -2 edges are removed from G, it still contains a planar spanning subtree. Note that if the n -1 edges incident to any vertex of G are removed, then G no longer contains a spanning subtree. In general, for 2 ≤ k ≤ n -1, in [START_REF] Aichholzer | Edge-removal and non-crossing configurations in geometric graphs[END_REF], it is proved that if any set of n(n-k+1) 2 -1 edges are removed from G, it still contains a planar subtree on k vertices. In the same paper it is also shown that this bound is tight-a geometric graph on n vertices and a subset of n(n-k+1) 2 of its edges are shown, so that when these edges are removed, every planar subtree has at most k -1 vertices. In [START_REF] García | Packing trees into planar graphs[END_REF] the authors study the seemingly unrelated (non-geometric) problem of packing two trees into planar (i) (abstract) graphs. That is, given two trees on n vertices, the authors consider the question of when it is possible to find a planar graph having both of them as spanning trees and in which the trees are edge disjoint. However, although theirs is a combinatorial question rather than (i) A planar (abstract) graph is an abstract graph that can be embedded in the plane; the embedding may not be unique.

Fig. 1: An embedding of a tree using the algorithm. geometric, their Theorem 2.1 implies our Lemma 2.2. We provide a self contained proof of Lemma 2.2 for completeness.

A previous version of this paper appeared in the conference proceedings of EUROCG'12 [START_REF] Barba | The Erdős-Sós conjecture for geometric graphs[END_REF].

Spanning Trees

In this section we consider the case when k = n. Let T be a tree on n vertices. Consider the following algorithm to embed T into G. Choose a vertex v of T and root T at v. For every vertex of T choose an arbitrary order of its children. Suppose that the neighbors of v are u 1 , . . . , u m , and let n 1 , . . . , n m be the number of nodes in their corresponding subtrees. Choose a convex hull point p of G and embed v into p. Sort the remaining points of G counter-clockwise by angle around p. A wedge is a region of the plane bounded by two infinite rays sharing a common apex. Choose m + 1 rays centered at p so that the wedge between two consecutive rays is convex and between the i-th ray and the (i + 1)-th ray there are exactly n i points of G. Let S i be this set of points. A convex hull vertex q of S i is visible from p if the line segment with endpoints p and q intersects the convex hull of S only at q. For each u i choose a convex hull vertex of S i visible from p and embed u i into this point. Recursively embed the subtrees rooted at each u i into S i . Note that this algorithm provides an embedding of T into G. We will use this embedding frequently throughout the paper. See Figure 1.

For every integer n ≥ 2 we define a tree T n as follows: If n = 2, then T n consists of only one edge; if n is odd, then T n is constructed by subdividing once every edge of a star on n+1 2 vertices; if n is even and greater than 2, then T n is constructed by subdividing an edge of T n-1 . See Figure 2.

We prove the lower bound of f (n, n) ≥ 2 of Theorem 1.2.

Theorem 2.1 If G has only one forbidden edge, then any tree on n vertices can be embedded into G, without using the forbidden edge.

Proof: Let e be the forbidden edge of G. Let T be a tree on n vertices. Choose a root for T . Sort the children of each node of T , by increasing size of their corresponding subtrees. Embed T into G with the embedding algorithm, choosing at all times the rightmost point (the first point when sorting clockwise around the root) as the root of the next subtree. Suppose that e is used in this embedding. Let e := pq so that u is embedded into p and v is embedded into q (note that u is the parent of v in T ). Suppose that the subtree rooted at v has m ≥ 2 nodes. In the algorithm, we embedded this subtree into a set of exactly m points. We chose a convex hull point (q), of this set visible from p to embed v. In this case we may choose another convex hull point visible from p to embed v and continue with the algorithm. Note that pq is no longer used in the final embedding.

Suppose that v is a leaf, and that v has a sibling v whose subtree has at least two nodes. Then we may interchange v and v in the order of the children of u, so that e is no longer used in the embedding, or if it is, then v is embedded into q, but then we proceed as above.

Suppose that v is a leaf, has at least one sibling and all its siblings are leaves. The subtree rooted at u is a star. We choose a point distinct from p and q in the point set where this subtree is embedded, and embed u into this point. Afterward we join it to the remaining points. This produces an embedding that avoids e.

Assume then, that v is a leaf and that it has no siblings. We distinguish the following cases:

1. u has no siblings. In this case, the subtree rooted at the parent of u is a path of length two. If u has no grandparent then n = 3 and T can be trivially embedded into G without using e. Suppose u has a grandparent. In this case there are only four vertices to consider: v, u, the parent of u and the grandparent of u. We keep the current location of the grandparent of u, and change the points into which the remaining vertices are embedded. This can always be done so that e is not used in the embedding. All possible cases are shown in Figure 3.

2. u has a sibling u whose subtree is not an edge. We may change the order of the siblings of u, with respect to their parent, so that the subtree rooted at u will be embedded into the point set containing p and q. In the initial order-increasing by size of their corresponding subtrees-u is after u. We may assume that in the new ordering, the order of the siblings of u before it, stays the same. Therefore p is the rightmost point of the set into which the subtree rooted at u will be embedded. Embed u into p. Either we find an embedding not using e, or this embedding falls into one of the cases considered before.

3. u has at least one sibling, and the subtree at every sibling of u is an edge.

Suppose that u has no grandparent; then T is equal to T n and n is odd. Let w be the parent of u. Embed w into p. Let p 1 , . . . , p n-1 be the points of G different from p sorted counter-clockwise Fig. 3: The embedding of a path of length three. The grandparent of u is highlighted and the forbidden edge is dashed.

by angle around p; choose p 1 so that the angle between two consecutive points is less than π. Let u 1 , . . . , u (n-1)/2 be the neighbors of w. Embed each u i into p 2i-1 and its child into p 2i . If q equals p 2j-1 for some j then embed u j into p 2j and its child into p 2j-1 . This embedding avoids e.

Suppose that w is the grandparent of u and let p be the point into which w is embedded. Let S be the point set into which the subtree rooted at the parent of u is embedded. Note that S has an odd number of points. We replace the embedding as follows. Sort S counter-clockwise by angle around p . Call a point even if it has an even number of points before it in this ordering. Call a point odd if it has an odd number of points before it in this ordering. If e is incident to an odd point, then we embed the parent of u into this point. The remaining subtree rooted at u can be embedded without using e. If the endpoints of e are both even, between them there is an odd point. We embed the parent of u into this point. The remaining vertices can be embedded without using e (see Figure 4).

2

The upper bound of f (n, n) ≤ 3 of Theorem 1.2 follows directly from Lemma 3.2. Now we prove in Lemma 2.2 and Theorem 2.3, that if G is a convex geometric graph, at least three edges are needed to forbid some tree on n vertices. Lemma 2.2 Let T be a tree on n vertices. If G is a convex geometric graph, then T can be embedded into G using less than n 2 convex hull edges of G.

Proof: If T is a star, then any embedding of T into G uses only two convex hull edges. If T is a path then it can be embedded into G using at most two convex hull edges. Therefore, we may assume that T is neither a star nor a path. Since T is not a path, it has a vertex of degree at least three. Choose this vertex as the root. Since T is not a star, the root has a child whose subtree has at least two nodes. Order the children of T so that this node is first. Embed T into G with the embedding algorithm.

Let u and v be vertices of T , so that u is the parent of v. Suppose that the subtree rooted at v has at least two nodes. Then in the embedding algorithm we have at least two choices to embed v once the ordering Fig. 4: The two sub-cases, when u has a grandparent w, and all the subtrees of its children are edges. Odd points are painted in black and even points in white. The forbidden edges are dashed.

of the children of u has been chosen. At least one of the choices is such that uv is not embedded into a convex hull edge. Therefore, we may assume that the embedding is such that each convex hull edge used, is incident to a leaf.

Note that every vertex of T , distinct from the root, is incident to at most one convex hull edge in the embedding. Since the first child of the root is not a leaf, no convex hull edge is used to embed this child. Only in the embedding of the last child of the root a convex hull may have been used. Therefore every vertex of T is incident to at most one convex hull edge. Thus the set of convex hull edges used in the embedding is a matching. Therefore at most n/2 convex hull edges are used in the embedding.

Suppose that exactly n/2 convex hull edges are used. One of these edges must be incident to the root. Since the root was chosen of degree at least three it has a child which is not a leaf nor the first child; we place this vertex last in the ordering of the children of the root. The leaf adjacent to the root can no longer be a convex hull edge and the embedding uses less than n/2 convex hull edges. 2

Theorem 2.3 If G is a convex geometric graph and has at most two forbidden edges, then any tree on n vertices can be embedded into G, without using a forbidden edge.

Proof: Let f 0 be an embedding given by Lemma 2.2, of T into G. For 0 ≤ i ≤ n, let f i be the embedding produced by rotating f 0 , i places to the right. Assume that in each of these rotations at least one forbidden edge is used, as otherwise we are done. Let e 1 , . . . , e m be the edges of T that are mapped to a forbidden edge in some rotation. Assume that the two forbidden edges are an l-edge and an r-edge respectively. Suppose that l = r. Then, each edge of T can be embedded into a forbidden edge at most once in all of the n rotations. Thus m ≥ n. This is a contradiction, since T has n -1 edges.

Suppose that l = r. Then, each of the e i is mapped twice to a forbidden edge. Thus m ≥ n/2. By Lemma 2.2, f 0 uses less than n/2 convex hull edges. Therefore, l = r > 0. But a set of n/2 or more r-edges, with r > 0, must contain a pair of edges that cross. And we are done, since f 0 is an embedding.

Fig. 2 :

 2 Fig. 2: T7 and T8.

Acknowledgments

Part of this work was done at the "First Workshop in Combinatorial Optimization at Cinvestav". It was continued during a visit of L. Barba, R. Fabila-Monroy, J. Leaños and G. Salazar to Abacus research center (ii) .

‡ Partially supported by CONACYT of Mexico, Grant 153984. § Partially supported by CONACYT of Mexico, Grant 106432. 1365-8050

3 Bounds on f (n, k)

In this section we prove Theorem 1.1. First we show the upper bound. Lemma 3.1 If T n is embedded into G n then every edge incident to a leaf of T n must be embedded into a convex hull edge.

Proof: Let e := uv be an edge of T n incident to leaf. Suppose that u is the leaf vertex. Then v is of degree two. Suppose that e is not embedded into a convex hull edge of G. Then e divides S \ {u, v} into two non-empty subsets S 1 and S 2 , so that S 1 lies on the opposite side of S 2 with respect to e. Assume that the parent of v is embedded into S 1 . Then no vertex of T n can be embedded into S 2 without crossing e. Therefore e must be a convex hull edge of G. 2

Lemma 3.2 If G is a convex geometric graph, then forbidding three consecutive convex hull edges of G forbids the embedding of T n .

Proof: Recall that T n comes from subdividing a star, let v be the non leaf vertex of this star. Let p 1 p 2 , p 2 p 3 , p 3 p 4 be the forbidden edges, in clockwise order around the convex hull of G. Note that by Lemma 3.1, in any embedding of T n into G, an edge incident to a leaf of T n , must be embedded into a convex hull edge. Neither the leaves of T n nor its neighbors can be embedded into p 2 or p 3 , without using a forbidden edge. Thus, v must be embedded into p 2 or p 3 . Without loss of generality assume that v is embedded into p 2 . But then, the embedding must use p 2 p 3 or p 3 p 4 2

Lemma 3.3 If G is a convex geometric graph, then forbidding the convex hull edges incident to any three vertices p 1 , p 2 and p 3 of G, forbids the embedding of T n .

Proof: Note that by Lemma 3.1, neither a leaf of T n , nor its neighbor can be embedded into p 1 , p 2 or p 3 , without using a forbidden edge. But at most two points do not fall into this category.

Proof: Let G be a complete convex geometric graph. We forbid every r-edge of G for r = 0, . . . , 2 n-2 k-2 -2 . Note that, in total we are forbidding at most n 2 n-2 k-2 -2 + 1 ≤ 2 n(n-2) k-2 edges. As every subset of points of G is in convex position, it suffices to show that every induced subgraph H of G on k vertices is in one of the two configurations of Lemmas 3.2 and 3.3.

Assume then, that H does not contain three consecutive forbidden edges in its convex hull nor three vertices, each with its two convex hull edges forbidden. H has at most two (non-adjacent) pairs of consecutive forbidden edges in its convex hull. Therefore every forbidden edge of H in its convex hull-with the exception of at most two-must be preceded by an -edge (of G), with > 2 n-2 k-2 -2 . The number of these -edges contained in H is at least k-2

2 . The points separated by these edges amount to more than

This is a contradiction, since together with the k points of H this is strictly more than n.

2

Now, we show the lower bound of Theorem 1.1.

Proof: Let F be a set of edges whose removal from G forbids some k-tree. Let H := G \ F . Note that H contains no complete K k as a subgraph, otherwise any k-tree can be embedded into this subgraph. By Turán's Theorem [START_REF] Turán | On an extremal problem in graph theory[END_REF], H cannot contain more than k-2 k-1 n 2

2 edges. Thus F must have size at least

2


Aijun Dong
email: dongaijun@mail.sdu.edu.cn

Guizhen Liu
email: gzliu@sdu.edu.cn

Guojun Li
email: guojunsdu@gmail.com.

List Edge and List Total Colorings of Planar Graphs without non-induced 7-cycles †

Keywords: List coloring, Planar graph, Choosability

Giving a planar graph G, let χ l (G) and χ l (G) denote the list edge chromatic number and list total chromatic number of G respectively. It is proved that if G is a planar graph without non-induced 7-cycles, then χ l (G) ≤ ∆(G) + 1 and χ l (G) ≤ ∆(G) + 2 where ∆(G) ≥ 7.

Introduction

The terminology and notation used but undefined in this paper can be found in [START_REF] Bondy | Graph Theory with Applications[END_REF]. Let G be a graph and we use V (G), E(G), F (G), ∆(G) and δ(G) to denote the vertex set, edge set, face set, maximum degree, and minimum degree of G, respectively. Let d G (x) or simply d(x), denote the degree of a vertex (resp. face) x in G. A vertex (resp. face) x is called a k-vertex (resp. k-f ace), k + -vertex (resp.

k + -f ace), or k --vertex, if d(x) = k, d(x) ≥ k, or d(x) ≤ k. We use (d 1 , d 2 , • • • , d n ) to denote a face f if d 1 , d 2 , • • • , d n
are the degrees of vertices which are incident with the face f . If u 1 , u 2 , • • •, u n are the vertices on the boundary walk of a face f , then we write f = u 1 u 2 • • • u n . Let δ(f ) denote the minimal degree of vertices which are incident with f . We use f i (v) to denote the number of i-faces which are incident with v for each v ∈ V (G). Let n i (f ) denote the number of i-vertices which are incident with f for each f ∈ F (G). A cycle C of length k is called k-cycle, and if there is at least one edge

xy ∈ E(G)\E(C) and x, y ∈ V (C), the cycle C is called non-induced k-cycle.
The mapping L is said to be a total assignment for a graph G if it assigns a list L(x) of possible colors to each element

x ∈ V (G)∪E(G). If G has a proper total coloring φ(x) ∈ L(x) for all x ∈ V (G)∪E(G), then we say that G is total-L-colorable. Let f : V (G)∪E(G) → N where f is a function into the positive integers. We say that G is total-f -choosability if it is total-L-colorable for every total assignment L satisfying |L(x)| = f (x) for all x ∈ V (G) ∪ E(G). The list total coloring number χ l (G) of G is the smallest integer k such that G is total-f -choosability when f (x) = k for each x ∈ V (G) ∪ E(G).
The list edge coloring number χ l (G) of G is defined similarly in terms of coloring edges alone; and so is the concept of edge-f -choosability. On the list coloring number of a graph G, there is a famous conjecture known as the List Coloring Conjecture.

Conjecture 1 For a multigraph G, (a) χ l (G) = χ (G); (b) χ l (G) = χ (G).
Part (a) of Conjecture 1 was formulated independently by Vizing, by Gupta, by Alberson and Collins, and by Bollobás and Harris [START_REF] Hägkvist | Some upper bounds on the total and list chromatic numbers of multigraphs[END_REF][START_REF] Jensen | Graph Coloring Problem[END_REF]. It is well known as the List Coloring Conjecture. Part (b) was formulated by Borodin, Kostochka and Woodall [START_REF] Borodin | List edge and list total colourings of multigraphs[END_REF]. Part (a) has been proved for bipartite multigraphs [START_REF] Galvin | The list chromatic index of a bipartite multigraph[END_REF]. Part (a) and Part (b) have been proved for outerplanar graphs [START_REF] Wang | Choosability, edge-choosability and total choosability of outerplane graphs[END_REF], and graphs with ∆ ≥ 12 which can be embedded in a surface of nonnegative characteristic [START_REF] Borodin | List edge and list total colourings of multigraphs[END_REF]. There are several related results for planar graphs, such as planar graphs without 4-cycles by Hou et al. [START_REF] Hou | List Edge and List Total Colorings of Planar Graphs without 4-cycles[END_REF], planar graphs without 4and 5-cycles or planar graphs without intersecting 4-cycles by Liu et al. [START_REF] Liu | List edge and list total colorings of planar graphs without short cycles[END_REF], planar graphs without triangles adjacent 4-cycles by Li et al. [START_REF] Li | Edge choosability and total choosability of planar graphs without no 3-cycles adjacent 4-cycles[END_REF], planar graphs without intersecting triangles by Sheng et al. [START_REF] Sheng | A structural theorem for planar graphs with some applications[END_REF].

To confirm Conjecture 1 is a challenging work. From the Vizing Theorem and the Total Coloring Conjecture, the following weak conjecture is presented.

Conjecture 2 For a multigraph G, (a) χ l (G) ≤ ∆(G) + 1; (b) χ l (G) ≤ ∆(G) + 2.
Part (a) of Conjecture 2 has been proved for complete graphs of odd order [START_REF] Hägkvist | New bounds on the list-chromatic index of the complete graph and other simple graphs[END_REF]. Wang In this paper, we shall show the following result. Theorem Let G be a planar graph without non-induced

7-cycles, if ∆(G) ≥ 7, then χ l (G) ≤ ∆(G) + 1 and χ l (G) ≤ ∆(G) + 2.

Planar graphs without non-induced 7-cycles

First let us introduce some important lemmas.

Lemma 3 Let G be a planar graph without non-induced 7-cycles. Then there is an edge

uv ∈ E(G) such that min{d(u), d(v)} ≤ ∆(G)+1 2 and d(u) + d(v) ≤ max{9, ∆(G) + 2}.
Proof: Suppose to the contrary that G is a minimal counterexample to Lemma 3 in terms of the number of vertices and edges. Then we have δ(G) ≥ 3.

Let Ḡ = G -uv. Then Ḡ is edge-L -colorable by assumption. For d(u) + d(v) ≤ k + 2, there are at most k edges which are adjacent to uv in Ḡ . Thus there is at lest one color in L (uv) which we can use to color uv. Then G is edge-L -colorable, a contradiction.

Let Ḡ = G -uv. Then Ḡ is total-L -colorable by assumption. With loss of generality, let d(u) = min{d(u), d(v)}. Erase the color on u, then there is at least one color in L (uv) which we can use to color uv for d

(u) + d(v) ≤ k + 2. For d(u) ≤ ∆(G)+1 2 ≤ k+1 2
, then u is adjacent to at most k+1 2 vertices and is incident with at most k+1 2 edges. Thus there is at least one color in L (u) which we can use to color u. Then G is total-L -colorable, a contradiction. From the above discussion, we have χ l (G) ≤ k + 1 and χ l (G) ≤ k + 2 where k = max{∆(G), 7}.

2

By Lemma 4, it is easy to obtain the main theorem. Theorem Let G be a planar graph without non-induced 7-cycles, if ∆(G) ≥ 7, then χ l (G) ≤ ∆(G) + 1 and χ l (G) ≤ ∆(G) + 2.

  et al. confirmed part (a) of Conjecture 2 for planar graphs without 6-cycles or without 5-cycles [17, 16]. Zhang et al. proved part (a) of Conjecture 2 for planar graphs without triangles [19]. Hou et al. proved part (a) of Conjecture 2 for planar graphs without adjacent triangles or 7-cycles [8]. Cai et al. confirmed part (a) of Conjecture 2 for planar graphs without chordal 5-cycles [3]. Part (b) of Conjecture 2 was proved by Hou et al. for planar graphs G with ∆(G) ≥ 9 [10]. Dong et al. confirmed Conjecture 2 for planar graphs without 6-cycles with chord [4].

Supported by NSFC grants 11101243, 11161035.

Define an initial charge function w on V (G) ∪ F (G) by setting w(v) = 2d(v) -6 if v ∈ V (G) and w(f ) = d(f ) -6 if f ∈ F (G), so that x∈V (G)∪F (G) w(x) = -12. Now redistribute the charge according to the following discharging rules.

For convenience, let w(v) denote the total charge transferred from a vertex v to all its incident 4and 5-faces where d(v) = 5.

D1 Let f be a 3-face incident with a vertex v. Then v gives f charge 4-w(v) f3

Let the new charge of each element x be w (x) for each x ∈ V (G) ∪ F (G).

In the following, let us check the new charge w

Suppose δ(f ) = 4. Then f is a (4, 6 + , 6 + )-face by assumption. We have w (f ) = -3

Suppose δ(f ) = 5. Then f is a (5, 5 + , 5 + )-face. Suppose f is a (5, 5, 5)-face. For convenience, let f = uvw. Of the three vertices u, v and w, there is at most one vertex which is incident with at least four 3-faces for the reason that G contains no non-induced 7-cycles. Without loss of generality, let

Then we have 4-w(v) f3(v) ≥ 1 for G contains no non-induced 7-cycles and by D1, D2 and D3. Thus w (f ) ≥ -3


Olga Glebova

Yury Metelsky

Pavel Skums
email: skumsp@gmail.com

Krausz dimension and its generalizations in special graph classes

Keywords: Krausz dimension, intersection graph, linear k-uniform hypergraph, chordal graph, split graph, polar graph

A Krausz (k, m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-Krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k, m)-partition. In particular, 1-Krausz dimension or simply Krausz dimension kdim(G) is a well-known graph-theoretical parameter.

In this paper we prove that the problem "kdim(G) ≤ 3" is polynomially solvable for chordal graphs, thus partially solving the open problem of P. Hlineny and J. Kratochvil. We solve another open problem of P. Hlineny and J. Kratochvil by proving that the problem of finding Krausz dimension is NP-hard for split graphs and complements of bipartite graphs. We show that the problem of finding m-Krausz dimension is NP-hard for every m ≥ 1, but the problem "kdimm(G) ≤ k" is is fixed-parameter tractable when parameterized by k and m for (∞, 1)-polar graphs. Moreover, the class of (∞, 1)-polar graphs with kdimm(G) ≤ k is characterized by a finite list of forbidden induced subgraphs for every k, m ≥ 1.

Introduction

In this paper we consider finite undirected graphs without loops and multiple edges. The vertex and the edge sets of a graph (hypergraph) G are denoted by V (G) and E(G) respectively. N (v) = N G (v) is the neighborhood of a vertex v in G and deg(v) is the degree of v. Let G(X) denote the subgraph of G induced by a set X ⊆ V (G) and ecc G (v) is the eccentricity of a vertex v ∈ V (G).

A Krausz partition of a graph G is a decomposition of G into cliques, which are called clusters of the partition, such that every edge of G belongs to exactly one cluster. If every vertex of G belongs to at most k clusters, then the partition is called Krausz k-partition. The Krausz dimension kdim(G) of the graph G is a minimal k such that G has Krausz k-partition.

Krausz k-partitions are closely connected with the representation of a graph as an intersection graph of a hypergraph. The intersection graph L(H) of a hypergraph H = (V (H), E(H)) is defined as follows:

1. the vertices of L(H) are in a bijective correspondence with the edges of H; 2. two vertices are adjacent in L(H) if and only if the corresponding edges have a nonempty intersection.

Hypergraph H is called linear if any two of its edges have at most one common vertex; k-uniform if every edge contains k vertices.

The multiplicity of the pair of vertices u, v of the hypergraph H is the number m(u, v) = |{E ∈ E(H) : u, v ∈ E}|; the multiplicity m(H) of the hypergraph H is the maximum multiplicity of the pairs of its vertices. So, linear hypergraphs are the hypergraphs with the multiplicity 1.

Denote by H * the dual hypergraph of H and by H [START_REF] Beineke | The Krausz dimension of a graph[END_REF] the 2-section of H, i.e., the simple graph obtained from H by the transformation of each edge into a clique. It follows immediately from the definition that L(H) = (H * ) [START_REF] Beineke | The Krausz dimension of a graph[END_REF] .

(1)

First this relation was implicitly formulated by C. Berge in [START_REF] Berge | Combinatorics of Finite Sets[END_REF]. [START_REF] Beineke | Derived graphs and digraphs[END_REF] implies that a graph G has Krausz k-partition if and only if it is an intersection graph of linear k-uniform hypergraph.

A graph G is called polar [START_REF] De Werra | Polarity of chordal graphs[END_REF]21] if there exists a partition of its vertex set

V (G) = A ∪ B, A ∩ B = ∅ (2)
such that all connected components of the graphs G(A) and G(B) are complete graphs. The partition (A, B) is called bipartition. If, in addition, α and β are fixed integers and the orders of connected components of the graphs G(A) and G(B) are at most α and β respectively, then the polar graph G with bipartition (2) is called (α, β)-polar [START_REF] Zh | About recognizing (α, β) classes of polar graphs[END_REF]. Given a polar graph G with bipartition (2), if the order of connected components of the graph G(A) (the graph G(B)) is not restricted above, then the parameter α (respectively β) is supposed to be equal ∞. Thus an arbitrary polar graph is (∞, ∞)-polar, and (1, 1)polar graphs are exactly well-known split graphs.

Denote by KDIM (k) the problem of determining whether kdim(G) ≤ k and by KDIM the problem of finding the Krausz dimension.

Graphs with Krausz dimension at most 2 are exactly line graphs. The class of line graphs has been studied for a long time. It is characterized by a finite list of forbidden induced subgraphs [START_REF] Beineke | Derived graphs and digraphs[END_REF], efficient algorithms for solving the problem KDIM (2) and constructing the corresponding Krausz 2-partition are also known [START_REF] Degiorgi | A dynamic algorithm for line graph recognition[END_REF][START_REF] Lehot | An optimal algorithm to detect a line graph and output its root graph[END_REF][START_REF] Naor | An efficient reconstruction of a graph from its line graph in parallel[END_REF][START_REF] Roussopoulos | A max {m,n} algorithm for determining the graph H from its line graph G[END_REF].

The situation changes radically if one takes k = 3 instead of k = 2 : the problem KDIM (k) is NP-complete for every fixed k ≥ 3 [START_REF] Hliněný | Computational complexity of the Krausz dimension of graphs[END_REF]. The case k = 3 was studied in the different papers [START_REF] Jacobson | Recognizing intersection graphs of linear uniform hypergraphs[END_REF][START_REF] Yu | Line graphs of linear 3-uniform hypergraphs[END_REF][START_REF] Naik | Intersection graphs of k-uniform linear hypergraphs[END_REF][START_REF] Naik | Intersection graphs of k-uniform linear hypergraphs[END_REF][START_REF] Skums | Edge intersection graphs of linear 3-uniform hypergraphs[END_REF], and several graph classes, where the problem KDIM (3) is polynomially solvable or remains NP-complete, were found.

In [START_REF] Hliněný | Computational complexity of the Krausz dimension of graphs[END_REF] P. Hlineny and J. Kratochvil studied the computational complexity of the Krausz dimension in detail. Besides other results, the following findings were obtained in their paper:

R1) The problem KDIM is polynomially solvable for graphs with bounded treewidth. In particular, it is polynomially solvable for chordal graphs with bounded clique size.

R2) For the whole class of chordal graphs, the problem KDIM (k) is NP-complete for every k ≥ 6.

R3

) For every fixed k the problem KDIM (k) is polynomially solvable in the class of split graphs. Note, that this result was independently obtained in [START_REF] Yu | Split intersection graphs of hypergraphs with bounded rank[END_REF].

Note, that the study of Krausz dimension of split graphs were motivated by results of L. Beineke and I. Broere [START_REF] Beineke | The Krausz dimension of a graph[END_REF], who studied the Krausz dimension of complete graph without one edge, which appeared to be non-trivial problem.

Based on their results, P. Hlineny and J. Kratochvil posed the following open problems: P1) decide the complexity of KDIM (k) restricted to chordal graphs for k = 3, 4, 5;

P2) decide the complexity of KDIM for split graphs and complements of bipartite graphs.

In this paper we solve Problem P2 and partially solve Problem P1. In Section 2 we prove that the problem KDIM (3) is polynomially solvable in the class of chordal graphs. In Section 3 we show that the problem KDIM is NP-hard for both classes of split graphs and complements of bipartite graphs.

In Section 4 we consider a natural generalization of the Krausz dimension. A Krausz (k, m)-partition of a graph G is a decomposition of G into cliques, which are called clusters of the partition, such that any vertex belongs to at most k clusters, and any two clusters have at most m vertices in common. As shown above, the relation (1) implies the following statement: k the class of graphs with a Krausz (k, m)partition. It was proved in [START_REF] Levin | Line Hypergraphs[END_REF] that the class L m 3 could not be characterized by a finite set of forbidden induced subgraphs for every m ≥ 2, but the complexity of the problem KDIM m for an arbitrary m has not been established yet. We prove that the problem KDIM m is NP-hard for every m ≥ 1.

The class L m k is hereditary, i.e., closed with respect to deleting the vertices. Therefore it can be characterized in terms of forbidden induced subgraphs. We prove that for every fixed integers m, k such finite characterization of the class exists when restricted to (∞, 1)-polar graphs. In particular, it follows that the problem KDIM m (k) is fixed-parameter tractable when parameterized by k and m. It is the strong generalization of the result R3. Note also, that the class of (∞, 1)-polar graphs could be recognized in polynomial time [START_REF] Zh | About recognizing (α, β) classes of polar graphs[END_REF].

Krausz 3-partitions of chordal graphs

Let F be a family of cliques of graph G. The cliques from F are called clusters of F. Denote by l F (v) the number of clusters from F covering the vertex v and by C(v 1 , . . . , v r ) the cluster containing vertices v 1 , . . . , v r .

A maximal clique with at least k 2 -k + 2 vertices is called a k-large clique. For such cliques the following statement holds:

Lemma 2 ([9, 10, 17]) Any k-large clique of a graph G belongs to every Krausz k-partition of G.
Further in this section 3-large clique will be called simply large clique. Let G be a graph with kdim(G) ≤ 3 and Q be some its Krausz 3-partition. Any subset F ⊆ Q is called a fragment of the Krausz 3-partition Q or simply a fragment.

Let F be some fragment of Krausz 3-partition Q and H be the subgraph of G obtained by deleting edges covered by F . Further we will use the notation H = G -E(F ). The set F could be empty. Fix some vertex a ∈ V (H) and positive integer k. Denote by B k [a] the kth neighborhood of a in H, i.e. the set of vertices at distance at most k from a. In particular,

N (a) = B 1 [a] \ {a} denote the set of neighbors of a. A family of cliques F k (a) in H is called (a, k)-local fragment or simply a local fragment, if 1. every edge with at least one end in B k [a] is covered by some cluster of F k (a), 2. every vertex v ∈ B k [a] belongs to at most 3 -l F (v) clusters of F k (a), 3. every two clusters of F k (a) have at most one common vertex. A clique C of H is called special if C is a cluster of every (a, k)-local
fragment for some a and k. In particular, by Lemma 2 large cliques are special.

The following statement is evident.

Lemma 3 Let G be a graph with a Krausz 3-partition Q, F be a fragment of Q and H = G -E(F ).
Then the following propositions hold:

1. If deg(v) ≥ 19 for some vertex v ∈ V (G), then v is contained in some large clique. 2. If l F (v) = 2, then C = N H (v) ∪ {v} is a special clique. 3. If v ∈ B k [a] is adjacent to at least 4 -l F (v) vertices of the cluster C of some local fragment F k (a), then v ∈ C.
4. For every a ∈ V (H) and every k there exists at least one (a, k)-local fragment;

5) If the clique C is special, then F ∪ {C} is a fragment.

Proof:

1. If v is contained in clusters C 1 , C 2 , C 3 ∈ Q, then |C 1 | + |C 2 | + |C 3 | = deg(v) + 3 ≥ 22, which
implies, that at least one of the clusters C 1 , C 2 , C 3 has more than 7 vertices.

2. If F k (a) is a local fragment, then by the definition v belongs to at most one cluster

C ∈ F k (a). Therefore all neighbors of v in H belong to C, i.e. C = N H (v) ∪ {v}. 3. If v ∈ B k [a] is adjacent to vertices v 1 , ..., v 4-l F (v) ∈ C ∈ F k (a), but v ∈ C, then the edges vv 1 , . . . , vv 4-l F (v) should be covered by different clusters of F k (a). It contradicts (2).

The family of cliques

X = {C ∈ Q \ F : C ∩ B k [a] = ∅} is a local fragment.
5. Let X is the same as in the proof of 4). Since C is special, C ∈ X and therefore

C ∈ Q \ F . 2
Lemma 4 Let G be a chordal graph and S be its cycle with length at least 4. Then for every two consecutive vertices of S at least one of them belongs to some chord.

Proof: Let S = (a 1 , . . . , a k ), a i a i+1 ∈ E(G), indices are taken modulo k. The statement of lemma is obvious, if k = 4. Let k ≥ 5. Without lost of generality consider two adjacent vertices a k , a 1 of S.

If the statement of lemma is not true, then one can choose the chord a p a q , 1 < p < q < k such, that (p -1) + (k -q) is minimal. But then (a 1 , . . . , a p , a q , . . . , a k ) is a chordless cycle. 2

Denote by lc(H) the length of a longest induced cycle of the graph H.

Lemma 5 Let G be a chordal graph with a Krausz 3-partition Q, F be a fragment of Q and H = G -E(F ). Let further there be no (a, 2)-local fragments, which contain special cliques in H. Then lc(H) ≤ 6.

Proof: Suppose the contrary, i.e., let a 1 , . . . , a k form the induced cycle

S ∼ = C k in H, k ≥ 7, a i a i+1 ∈ E(H), indices are taken modulo k.
Since each a i has two nonadjacent neighbors in H, in every local fragment with center in a i it is covered by at least 2 clusters. It implies l F (a i ) ≤ 1 for every i = 1, . . . , k.

As G is a chordal graph, there exist chords of the cycle S covered by the fragment F . As l F (a i ) ≤ 1, for every vertex a i chords incident to this vertex are covered by exactly one cluster of F . It implies that no pair of chords has the form {a i a j , a i a j+1 }, since in this case the vertices a i , a j , a j+1 are covered by one cluster of F and thus the edge a j a j+1 should be covered by F .

Assume without loss of generality that a chord of S contains a 1 . Let us show that all chords of S are covered by the cluster C chord ⊇ {a 1 , a 3 , . . . , a k-1 }. Indeed, suppose that some chords of S are covered by the cluster

C ⊇ {a i1 , . . . , a ir }, i 1 < i 2 < . . . < i r , i 1 = 1, C = C chord . Then there exists 1 ≤ p < r such that i p+1 -i p ≥ 3. So, (a ip , a ip+1 , . . . , a ip+1-1 , a ip+1
) is a cycle of length at least 4, in which at least one of the vertices a ip , a ip+1 , say a ip , belongs to some chord according to Lemma 4. That chord should be covered by a cluster C ∈ F , C = C. So, we have l F (a ip ) ≥ 2, the contradiction.

In particular, this proposition implies the following:

1. k is even; 2. for any odd i and even j such that a i a j is not the edge of S, the vertices a i and a j are nonadjacent in G. It follows from the fact, that otherwise l F (a i ) ≥ 2.

Since there are no special cliques in H there exist two different local fragments

F 2 (a 1 ) ⊇ {C(a 1 , a 2 ), C(a 1 , a k )} and F 2 (a 1 ) ⊇ {C (a 1 , a 2 ), C (a 1 , a k )}, such that without loss of generality C(a 1 , a 2 ) \ C (a 1 , a 2 ) = ∅. Let v ∈ C(a 1 , a 2 ) \ C (a 1 , a 2 ). Then v ∈ C (a 1 , a k ) and therefore a 1 v, a 2 v, a k v ∈ E(H). The vertices a 2 , v, a k , a k-1 , a 3 form a cycle in G. It should have at least 2 chords. Since a 2 a k-1 , a 3 a k ∈ E(G), there are edges va 3 , va k-1 ∈ E(G). The edges va 3 , va k-1 are not covered by F , because oth- erwise v ∈ C chord and thus {a 1 , v} ⊆ C chord ∩ C(a 1 , a 2 ) contradicting the definition of H. Hence va 3 , va k-1 ∈ E(H). a 3 ∈ B 2 [a 1 ],
therefore by the definition of local fragment all edges of H adjacent to a 3 are covered by 1). Note that since k ≥ 7, we have a 4 a k-1 ∈ E(H).

F 2 (a 1 ). It implies that F 2 (a 1 ) C(a 3 , a 2 ), C(a 3 , a 4 ). Since v ∈ C(a 1 , a 2 ) we have v ∈ C(a 3 , a 4 ). So, va 4 ∈ E(H) (see Figure
Recall that the vertex v in the local fragment F 2 (a 1 ) is covered by the cluster C (v, a 1 , a k ). All other edges of H incident to v should be covered by at most two clusters of F 2 (a 1 ). But this is impossible since the vertices a 2 , a 4 , a k-1 are pairwise nonadjacent. This contradiction proves Lemma 5.

2

a 1 v a 3 a 4 a k a k-1 a 2 Figure 1:
The considerations above suggest the following algorithm which reduces the problem of recognition chordal graphs with Krausz dimension at most 3 to the same problem for graphs with bounded maximum degree and maximum induced cycle length.

Algorithm 1

Input: chordal graph G.

Output: One of the following: 1) graph H * with ∆(H * ) ≤ 18 and lc(H * ) ≤ 6 such that kdim(G) ≤ 3 if and only if kdim(H * ) ≤ 3;

2) the answer "kdim(G) > 3". begin

F := ∅; H := G; isContinue := true; while (isContinue = true) if there exists a vertex v ∈ V (H) such that l F (v) = 2 C := N (v) ∪ {v}; if C is a clique F := F ∪ {C}; continue
v ∈ V (H) with l F (v) = 1; end. Theorem 6 ([4]) Let lc(H * ) ≤ s + 2, ∆(H * ) ≤ ∆. Then treewidth(H * ) ≤ ∆(∆ -1) s-1 .
Theorem 7 The problem KDIM (3) is polynomially solvable for chordal graph.

Proof: Let us first prove the correctness of Algorithm 1. Once the "while" loop of Algorithm 1 is completed, we obtain the graph H and the set of cliques F . By the construction F contains only special cliques. Therefore if the Krausz 3-partition of G exists then it has the form F ∪ R, where R is a clique partition of H such that every vertex v ∈ V (H) belongs to at most 3 -l F (v) clusters of R and every edge of H belongs to exactly one cluster of R. By the construction of Algorithm 1 l F (v) ∈ {0, 1} for every non-isolated vertex v ∈ V (H). Therefore R is a clique partition of H with required properties if and only if R ∪ {vp v : l F (v) = 1} is a Krausz 3-partition of H * . Now we will show that the Algorithm 1 is polynomial. Indeed, the procedure of finding large clique which contains the fixed vertex v ∈ V (H) has the complexity O(m). We start to generate all possible (v, e)-local fragments for a vertex v ∈ V (H) only when deg(v) ≤ 18. This implies |B e [v]| ≤ const and thus the complexity of this procedure is constant. The outer loop of Algorithm 1 is performed at most m times.

After performing the Algorithm 1, we obtain the graph H * with bounded maximum degree and the length of the longest induced cycle. By Theorem 6 H * has bounded treewidth. For such a graph the problem of determining its Krausz dimension is polynomially solvable [START_REF] Hliněný | Computational complexity of the Krausz dimension of graphs[END_REF]. 2

Krausz dimension of split graphs and complements of bipartite graphs

Theorem 8 The problem KDIM is NP-hard in the class of split graphs.

Proof: We will reduce the problem KDIM for general graphs to the problem KDIM for split graphs.

Let G be a connected graph with n vertices and m edges and k ≤ n -2 be an integer. Modify G by adding additional vertices and edges as follows:

1. For every u, v ∈ V (G) such that uv ∈ E(G), u = v add vertices x uv , y uv and edges uv, x uv u,

x uv v, y uv u, y uv v, x uv y uv . Let X = {x uv : uv ∈ E(G), u = v}, |X| = n 2 -m. 2. For every u, v, w ∈ V (G) such that uv ∈ E(G) and every w ∈ V (G) \ {u, v} add a vertex y uvw and edges x uv w, x uv y uvw , wy uvw ;

3. For every two vertices x uv , x sw ∈ X add a vertex z uvsw and edges x uv z uvsw , x sw z uvsw , x uv x sw ;

4. For every v ∈ V (G) add n -2 -k vertices r v,1 , ..., r v,n-2-k and edges vr v,1 , ..., vr v,n-2-k .
Let H be obtained graph (see an example of graph H for the graph G = K 1 + P 3 on Figure 2). Note, that A = V (G) ∪ X and B = V (H) \ A is a clique and a stable set in H, respectively. So, H is a split graph. We will show, that G has Krausz k-partition if and only if H has Krausz k -partition, where Let Q uv ⊆ Q be the set of clusters containing x uv . N uv is a stable set, and

k = n 2 + n -m -2. Suppose that Q is Krausz k -partition of H. For every u, v ∈ V (G), uv ∈ E(G) consider a set N uv = N (x uv ) ∩ B = {y uv } ∪ {y uvw : w ∈ V (G) \ {u, v}} ∪ {z uvsw : x sw ∈ X \ {x uv }} (3)
|N uv | = 1 + (n -2) + ( n 2 - m -1) = k .
Therefore every cluster of Q uv contains exactly one vertex from N uv , i.e.

Q uv = {C(y uv , x uv )}∪{C(y uvw , x uv ) : w ∈ V (G)\{u, v}}∪{C(z uvsw , x uv ) : x sw ∈ X \{x uv }} (4)
Every vertex of H, which is adjacent to x uv , belongs to one of those clusters. For every vertex from N (x uv ) \ N uv = A \ {x uv } we have the following.

1. The only vertex from N uv , which is adjacent to u and v, is y uv . Moreover, N (y uv ) = {u, v, x uv }.

Therefore C(y uv , x uv ) = {u, v, x uv , y uv }.

2. The only vertex from N uv , which is adjacent to w ∈ V (G)\{u, v}, is y uvw . Moreover, N (y uvw ) = {w, x uv }. Therefore C(y uvw , x uv ) = {w, x uv , y uvw }.

3. The only vertex from N uv , which is adjacent to x sw ∈ X \{x uv }, is z uvsw . Moreover, N (z uvsw ) = {x uv , x sw }. Therefore C(z uvsw , x uv ) = {x uv , x sw , z uvsw }.

For every v ∈ V (G) Krausz k -partition Q contains clusters {v, r v,i }, i = 1, ..., n -2 -k. So, Q contains a fragment Q = {Q uv : x uv ∈ X} ∪ {{v, r v,i } : v ∈ V (G), i = 1, ..., n -2 -k}. (5)
For every v ∈ V (G) let Q (v) be the set of clusters of Q which contain v. We have

Q (v) ={{v, r v,i } : i = 1, ..., n -2 -k} ∪ {{u, v, x uv , y uv } : u ∈ V (G), uv ∈ E(G)}∪ ∪ {{x sw , y swv , v} : s, w ∈ V (G) \ {v}, sw ∈ E(G)}} (6)
So,

|Q (v)| = n -2 -k + ( n 2 -m) = k -k (7)
The graph obtained from H by deleting edges covered by Q and isolated vertices is exactly the graph G.

Consider the fragment Q = Q \ Q . By (7) Q is Krausz k-covering of G. Conversely, it is easy to see, that if Q is Krausz k-covering of G, then Q ∪ Q is Krausz k -covering of H. v v 1 b c a v 2 v q -1 X Y Z
Figure 3:

Let now Q be Krausz (2q -1, m)-partition of G. Denote by Q(v) the set of clusters of Q, which contain the vertex v. Since the vertices v i , i = 1, . . . , q -1, have degree 1, there exist q -1 clusters from Q(v) of the form {v, v i }, i = 1, . . . , q -1. Let C 1 , . . . , C p be the remaining clusters from Q(v), p ≤ q. Then (C 1 ∪ . . . ∪ C p ) \ {v} = X ∪ Y ∪ Z. Since X, Y , Z are stable sets of G, we have |C i | ≤ 4, i = 1, . . . , p. As |X ∪ Y ∪ Z| = 3q, we have p = q, |C i | = 4, C i ∩ C j = {v}, i, j = 1, . . . , p, i = j. Let C i = {a i , b i , c i , v : a i ∈ X, b i ∈ Y, c i ∈ Z}, i = 1, . . . , q.
The property (*) implies that M = {(a i , b i , c i ) : i = 1, . . . , q} ⊆ M and, by the consideration above, M is the 3-dimensional matching.

2

Now we turn to the complexity of the recognition problem KDIM m (k) in the class of (∞, 1)-polar graphs.

A maximal clique with at least f (k, m) = m(k 2 -k + 1) + 1 vertices is called a (k, m)-large clique.

In [START_REF] Yu | Finite characterizability of intersection graphs of hypergraphs with bounded rank and multiplicity in the class of split graphs[END_REF] the following two statements were proved. Since they were published only in Russian in a journal that is of difficult access for general readers, we repeat their proofs here. Consider an arbitrary vertex v of the clique C. Let, without loss of generality, it belong to the clusters B 1 , B 2 , . . . , B s of B, s ≤ t. We show that |B 1 ∪ B 2 ∪ . . . ∪ B s | ≤ mk + (s -1)m(k -1). The following equality is obvious

|B 1 ∪ B 2 ∪ . . . ∪ B s | = |B 1 | + |B 2 \ B 1 | + |B 3 \ (B 1 ∪ B 2 )| + . . . + |B s \ (B 1 ∪ B 2 . . . ∪ B s-1 )|. (10) If B 1 \ B 2 = ∅, (B 1 ∪ B 2 ) \ B 3 = ∅, . . . , (B 1 ∪ B 2 ∪ . . . ∪ B s-1 ) \ B s = ∅,
then by the statement proved above, each term in the right part of the equality [START_REF] Jacobson | Recognizing intersection graphs of linear uniform hypergraphs[END_REF], starting from the second, does not exceed m(k -1). Hence we have

|B 1 ∪ B 2 ∪ . . . ∪ B s | ≤ mk + (s -1)m(k -1)
. Let, on the contrary, i ∈ {2, . . . , s} be the maximal number such that (B 1 ∪ . . .

∪ B i-1 ) \ B i = ∅. Then B 1 ⊆ B i , B 2 ⊆ B i , . . . , B i-1 ⊆ B i ,
and the sum of the first i terms in the right part of ( 10) is equal to

|B 1 ∪ B 2 ∪ . . . ∪ B i | = |B i | ≤ mk.
Each of the other terms does not exceed m(k -1) by the maximality of i. Hence

|B 1 ∪ B 2 ∪ . . . ∪ B s | ≤ mk + (s -i)m(k -1) < mk + (s -1)m(k -1).
So, in any case we obtain that the inequality

|B 1 ∪ B 2 ∪ . . . ∪ B s | ≤ mk + (s -1)m(k -1) holds. Taking into account that C = B 1 ∪ B 2 ∪ . . . ∪ B s and s ≤ k, we have |C| ≤ mk + (k -1)m(k -1) = m(k 2 -k + 1) < f (k, m).
The obtained contradiction proves the lemma.

2

Theorem 12 For every fixed k, m ≥ 1, there exists a finite set F 0 of forbidden induced subgraphs such that a split graph G belongs to the class L m k if and only if no induced subgraph of G is isomorphic to an element of F 0 .

Proof: Denote by R p the graph obtained from the complete graph H ∼ = K f (k,m) by adding a new vertex and connecting it with exactly p vertices of H. Put F 0 = {R p : km + 1 ≤ p ≤ f (k, m) -1} ∪ {K 1,k+1 }. Using Theorem 11 one can immediately verify that no graph from F 0 belongs to L m k . Let, without loss of generality, G be a connected graph, and V (G) = C ∪ S be a bipartition of V (G) into clique C and stable set S such that C is a maximal clique. Let also no induced subgraph of G be isomorphic to an element of F 0 . Put S = {v 1 , . . . , v s }. Consider two cases:

1) |C| > (km -1)k + 1.

In this case we have

|C| ≥ (km -1)k + 2 = mk 2 -(k -1) + 1 ≥ mk 2 -m(k -1) + 1 = f (k, m). Then, since no induced subgraph of G is isomorphic to a graph R p , km + 1 ≤ p ≤ f (k, m) -1,
k i=1 N (v i ), then | k i=1 N (v i )| ≤ k i=1 (deg(v i ) -1) + 1 ≤ (km -1)k + 1 < ϕ(G).
Hence, there exists a vertex u from C, which is not adjacent to any vertex from v 1 , . . . , v k . But then G(u, u , v 1 , . . . , v k ) ∼ = K 1,k+1 , a contradiction. Now we can construct a Krausz (k, m)-partition of G. Since deg(v i ) ≤ km for any i = 1, 2, . . . , s, then there exists a partition N (

v i ) = C i1 ∪ . . . ∪ C is i , where C ij ∩ C i l = ∅, j, l ∈ {1, . . . , s i }, j = l, |C ij | ≤ m, s i ≤ k. Obviously, the list of cliques {C ij ∪ {v i } : i = 1, s, j = 1, s i } together with the clique C is a Krausz (k, m)-partition of graph G. 2) |C| ≤ (km -1)k + 1. Since G contains no induced K 1,k+1 , we have |N (u) ∩ S| ≤ k for any vertex u from C. Therefore, as G is connected, |G| = |C|+|S| ≤ |C|+ u∈C |N (u)∩S| ≤ ((km-1)k+1)+((km-1)k+1)k = ((km-1)k+1)(k+1),
i. e., the order of graph G is bounded above by a value, depending on k and m. Add to the list F 0 all such split graphs H, that H ∈ L m k and |H| ≤ ((km -1)k + 1)(k + 1). Obviously, the constructed in the cases 1) and 2) finite list F 0 is a required list of forbidden induced subgraphs.

2

Since K 1,k+1 ∈ L m k , the heredity of L m k immediately implies Lemma 13 A bipartite graph G belongs to the class L m k if and only if no induced subgraph of G is isomorphic to K 1,k+1 . Theorem 14 For every fixed k, m ≥ 1, there exists a finite set F of forbidden induced subgraphs such that an (∞, 1)-polar graph G belongs to the class L m k if and only if no induced subgraph of G is isomorphic to an element of F.

Proof: Without loss of generality, we can suppose that (∞, 1)-polar graph G is connected. Let G have bipartition (A, B); A i , i = 1, 2, . . . , t, be the vertex sets of connected components of G(A); F 0 be the set of split graphs from Theorem 12. Denote by F 1 the set of (∞, 1)-polar graphs which do not belong to the class L m k and have order at most (k + 1)k(f (k, m) -1). Put F = F 0 ∪ F 1 ∪ {K 1,k+1 , K f (k,m)+1 -e}, where K f (k,m)+1 -e is the graph obtained from the complete graph K f (k,m)+1 after deleting an edge. The set F is finite, since F 0 and F 1 are finite. According to Theorem 11, there is no Krausz (k, m)-partition for K f (k,m)+1 -e. Therefore, K f (k,m)+1e ∈ L m k . Thus, F ∩ L m k = ∅. The necessity of the statement follows from the heredity of the class L m k . Now let G contain no induced subgraph isomorphic to an element from F. If G(A) is complete, then G is a split graph and by Theorem 12 G ∈ L m k . If G(A) is empty, then G is a bipartite graph and by Lemma 13 G ∈ L m k . Now suppose that G(A) is neither complete nor empty graph. Then 2 ≤ t ≤ |A| -1. Since K 1,k+1 ∈ F, then |A i | ≤ k for any i = 1, 2, . . . , t. Now we will prove that since K f (k,m)+1 -e ∈ F, then t ≤ f (k, m)-1. Let, to the contrary, t ≥ f (k, m). As G(A) is not a complete graph, there exists an index i 0 ∈ {1, 2, . . . , t} such that |A i0 | ≥ 2. Consider the set S = {a 1 , a 2 , . . . , a i0-1 , a i0 , a i0 , a i0+1 , . . . , a t }, where a i ∈ A i for any i ∈ {1, 2, . . . , t} \ {i 0 } and a i0 , a i0 ∈ A i0 . Then G(S) contains K f (k,m)+1 -e as an induced subgraph, a contradiction. Therefore

Proposition 1 A

 1 graph G has Krausz (k, m)-partition if and only if it is the intersection graph of a k-uniform hypergraph with the multiplicity at most m. The m-Krausz dimension kdim m (G) of the graph G is the minimum k such that G has a Krausz (k, m)partition. The Krausz dimension in those terms is the 1-Krausz dimension. Denote by KDIM m the problem of determining the m-Krausz dimension of graph, by KDIM m (k) the problem of determining whether kdim m (G) ≤ k and by L m

  Figure 2:

Theorem 11

 11 Any (k, m)-large clique C of a graph G belongs to every Krausz (k, m)-partition of G. Proof: Let A be a Krausz (k, m)-partition of graph G, A 1 , A 2 , . . . , A t be those clusters of A which have common vertices with C. Assume that C ∈ A. Then the family B = (B 1 , B 2 , . . . , B t ), where B i = A i ∩ C, is a Krausz (k, m)-partition of the graph G(C), and by maximality of C B i = C for every i = 1, 2, . . . , t. Let us show that |B i | ≤ mk for any i = 1, 2, . . . , t. Consider a cluster of B, say B 1 , and a vertex u ∈ C \ B 1 . No edge of the form ux, where x ∈ B 1 , is contained in B 1 . Moreover, by the definition of Krausz (k, m)-partition each cluster of B different from B 1 contains at most m such edges. Taking into account that the vertex u belongs to at most k clusters of B, we obtain the inequality |B 1 | ≤ mk.Now we will prove that ifB i \ B j = ∅ for some clusters B j ∈ B, then |B j \ B i | ≤ m(k -1). Consider a vertex u ∈ B i \ B j . Any edge of the form ux, where x ∈ B j \ B i (if such one exists) is contained neither in B i , nor in B j . Besides, no cluster of B contains more than m of such edges by definition of Krausz (k, m)-partition. Taking into account that u belongs to at most k -1 clusters of B different from B i , we obtain the inequality |B j \ B i | ≤ m(k -1).

  i | ≤ k(f (k, m) -1).

  by adding a pendant edge vp v to every vertex

	), 2};
	if there exists a vertex v ∈ V (H) such that there are
	no (v, e)-local fragments
	the answer is "kdim(G) > 3"; stop;
	if there exists a special clique C
	F := F ∪ {C}; continue to the next iteration of the cycle;
	isContinue := f alse
	endwhile;
	construct a graph H

to the next iteration of the cycle; else the answer is "kdim(G) > 3"; stop; if there exists a vertex v ∈ V (H) with deg(v) ≥ 19 if v is contained in a clique C with |C| ≥ 8 extend C to a maximal clique; F := F ∪ {C}; continue to the next iteration of the cycle; else the answer is "kdim(G) > 3"; stop; For every non-isolated vertex v ∈ V (H) generate all (v, e)-local fragments, e = min{ecc H (v*

  we have deg(v i ) ≤ km for any i = 1, 2, . . . , s. Since G contains no induced K 1,k+1 , we have |N (u) ∩ S| ≤ k for any vertex u from C. Moreover, we prove that for any vertex u from C the inequality |N (u) ∩ S| ≤ k -1 holds. Assume this is not true. Let, without loss of generality, some vertex u from C be adjacent to the vertices v 1 , . . . , v k from S, k ≤ s. Since deg(v i ) ≤ km, i = 1, 2, . . . , k, and u ∈

Acknowledgements

This work was partially supported by Belarussian Republican Fund of Fundamental Research.

Corollary 9

The problem KDIM is NP-hard in the class of complements of bipartite graphs.

Proof: Let G be a split graph on n vertices, V (G) = A ∪ B be the partition of its vertex set into clique A and stable set B and k be the natural number. Build the graph H as follows:

1. For every a ∈ A add the new vertex x a and the edge ax a ;

3. Add all possible edges between vertices of B .

H is a complement of bipartite graph. Taking into account Lemma 2, it is easy to see that

m-Krausz dimension of graphs

We will start with proving the NP-hardness of the problem KDIM m .

Theorem 10

The problem KDIM m is NP-hard for every fixed m ≥ 1.

Proof: Let us reduce to the problem KDIM m the following special case of the 3-dimensional matching problem, which we will call Problem A:

The question: Does M contain a subset M ⊆ M such that |M | = q and every two elements of M does not have common coordinates? The subset M is called 3-dimensional matching.

It is known that Problem A is NP-complete [START_REF] Garey | Computers and Intractability. A Guide to the Theory of NP-completeness[END_REF]. Let X, Y , Z, M , |X| = |Y | = |Z| = q, be the input of the problem A. Let us reduce problem A to the problem of determining if kdim m (G) ≤ 2q -1. Construct the graph G as follows:

(see Figure 3). Let us show that M contains the 3-dimensional matching M if and only if there exists a Krausz (2q

Since |N (a) ∩ B| ≤ k for any vertex a ∈ A and G is connected, we have

It follows from the inclusion

Corollary 15 The problem KDIM m (k) is fixed parameter tractable in the class of (∞, 1)-polar graphs, when parameterized by k, m ≥ 1.

Proof: The proofs of Theorems 12, 14 and Lemma 13 imply the following algorithm of recognition whether a given (∞, 1)-polar graph belong to the class The complexity of the algorithm in lines 1-14 is O(n 2 ) at worst, where n = |V (G)|. Since the order of the graph G in line 15 is bounded above by value g(k, m) = max{((km -1)k + 1)(k + 1), (k + 1)k(f (k, m) -1)} the problem "kdim m (G) ≤ k" in this line could be solved in time O(h(k, m)), where h is some function.

So, the total complexity of Algorithm 2 is O(n 2 + h(k, m)). 2