domain: math info

text:
Flavia Bonomo
email: fbonomo@dc.uba.ar

Oliver Schaudt
email: schaudt@math.jussieu.fr

Maya Stein
email: mstein@dim.uchile.cl

Mario Valencia-Pabon

b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs *

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χ b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it admits a b-coloring with t colors, for every t = χ(G), . . . , χ b (G), and b-monotonic if χ b (H 1 ) ≥ χ b (H 2 ) for every induced subgraph H 1 of G, and every induced subgraph H 2 of H 1 .

We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following:

1. We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic.

2. We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at least a given threshold.

3. We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees.

Introduction

A b-coloring of a graph G by k colors is a proper coloring of the vertices of G such that every color class contains a vertex that is adjacent to all the other k -1 color classes. Such a vertex will be called a dominating vertex. It is easy to see that any proper coloring of a graph G with χ(G) many colors is a b-coloring (as usual, we denote by χ(G) the minimum number of colors needed for a proper coloring of the vertices of a graph).

The b-chromatic number of a graph G, denoted by χ b (G), is the maximum number k such that G admits a b-coloring with k colors. Clearly, χ b (G) ≤ ∆(G) + 1 where ∆(G) denotes the maximum degree of G. The b-chromatic number was introduced in [START_REF] Irving | The b-chromatic number of a graph[END_REF]. The motivation, similarly as the well known achromatic number (cf. e.g, [START_REF] Harary | The achromatic number of a graph[END_REF][START_REF] Bodlaender | Achromatic number is NP-complete for cographs and interval graphs[END_REF] and ref. therein), comes from algorithmic graph theory. Suppose one colors a given graph properly, but in an arbitrary way. After all vertices are colored, one would wish to perform some simple operations to reduce the number of colors. A simple operation consists in recoloring all the vertices in one color class with a possible different color. Obviously, such recoloring is impossible if each color class contains a dominating vertex. Hence, the b-chromatic number of the graph serves as the tight upper bound for the number of colors used by this coloring heuristic. From this point of view, both complexity results and polynomial time algorithms for particular graph families are interesting.

Assume that the vertices v 1 , v 2 , . . . , v n of a graph G are ordered such that d(v 1 ) ≥ d(v 2 ) ≥ . . . ≥ d(v n ), where d(x) denotes the degree of vertex x in G. Let m(G) := max{i : d(v i ) ≥ i -1} be the maximum number i such that G contains at least i vertices of degree ≥ i -1. It is clear that m(G) ≤ ∆(G) + 1. Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] showed that this parameter bounds the b-chromatic number:

Proposition 1. For every graph G, χ(G) ≤ χ b (G) ≤ m(G).
Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] also showed that determining χ b (G) is NPcomplete for general graphs, but polynomial-time solvable for trees. Kratochvíl, Tuza and Voigt [START_REF] Kratochvíl | On the b-chromatic number of a graph[END_REF] proved that the problem of determining if χ b (G) = m(G) is NP-complete even for connected bipartite graphs G with m(G) = ∆(G) + 1. A graph G is tight if it has exactly m(G) dense vertices (a vertex v of a graph G is dense if d(v) ≥ m(G) -1), each of which has degree exactly m(G) -1. Havet, Linhares-Sales and Sampaio [START_REF] Havet | b-coloring of tight graphs[END_REF] recently investigated the problem on tight graphs. They proved that the problem of determining if a tight graph G has χ b (G) = m(G) is NP-complete for bipartite graphs and ptolemaic graphs, but polynomial-time solvable for complements of bipartite graphs, split graphs and block graphs.

In last years, several related concepts concerning b-colorings of graphs have been studied in [START_REF] Faik | La b-continuité des b-colorations : complexité, propriétés structurelles et algorithmes[END_REF][START_REF] Havet | b-coloring of tight graphs[END_REF][START_REF] Hoàng | On the b-dominating coloring of graphs[END_REF][START_REF] Hoàng | On minimally bimperfect graphs[END_REF]12]. A graph G is defined to be b-continuous [START_REF] Faik | La b-continuité des b-colorations : complexité, propriétés structurelles et algorithmes[END_REF] if it admits a b-coloring with t colors, for every t = χ(G), . . . , χ b (G). In [12] (see also [START_REF] Faik | La b-continuité des b-colorations : complexité, propriétés structurelles et algorithmes[END_REF]) it is proved that chordal graphs and some planar graphs are b-continuous. A graph G is defined to be b-monotonic [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF] if χ b (H 1 ) ≥ χ b (H 2 ) for every induced subgraph H 1 of G, and every induced subgraph H 2 of H 1 . They proved that P 4 -sparse graphs (and, in particular, cographs) are bcontinuous and b-monotonic. Besides, they give a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes.

Our paper is organized as follows. In the next section, we characterize b-colorings of graphs with stability number two in terms of matchings with no augmenting paths of length one or three.

In Section 3, we prove that graphs with stability at most two are both b-continuous and b-monotonic.

In Section 4, we prove that computing the b-chromatic number of cobipartite graphs is an NP-complete problem.

Finally, in Section 5, first we describe a polynomial-time dynamic programming algorithm to compute the b-chromatic number of co-trees. Next, we extend our results to the family of tree-cographs by showing that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of graphs in this family and that these are also bcontinuous and b-monotonic.

b-colorings and matchings

The stability of a graph G is defined as the maximum cardinality of a subset of pairwise non-adjacent vertices in G. Given a graph G, we denote by G the complement graph of G, which is the graph on the same set of vertices as G that has an edge between two different vertices u and v if and only if u and v are non-adjacent in G. It is not difficult to see that G is a graph with stability one if and only if it is complete, and G is a graph with stability at most two if and only if G is a triangle-free graph. In this section, we will see that matchings in triangle-free graphs are very important when we deal with b-colorings of graphs with stability at most two.

Let M be a matching of a graph G. Denote by V (M ) the set of all vertices covered by M . An augmenting path for M is a path starting and ending outside V (M ) whose edges alternate between E(G) -M and M . Usually, M is called maximal if no further edge can be included in M . In other words, G does not contain an augmenting path of length one with respect to M . Following this terminology we call M strongly maximal if G does not contain augmenting paths of length one or three with respect to M . Trivially, maximum matchings are strongly maximal, and strongly maximal matchings are maximal. Our next lemma shows why strongly maximal matchings are important in our setting.

Lemma 2. Let G be a graph of stability at most two and let c be a proper coloring of G. Then c is a b-coloring if and only if the set

M = {uv : u, v ∈ V, u = v and c(u) = c(v)} is a strongly maximal matching in G. Moreover, the number of colors c uses is |V (G)| -|M |.
Proof. First, observe that M is a (possibly empty) matching of G because G has stability at most two. Now, suppose that G contains an augmenting path P of length 1 or 3 for M . If P consists of only one edge uv, then in G, the vertices u and v are non-adjacent, and each makes up a singleton color class. Thus c is not a b-coloring. If P has three edges, say x -u -v -y, then for each of the endvertices of its middle edge uv there is a singleton color class with no vertex adjacent to it in G. In fact, {u, v}, {x} and {y} correspond to three different color classes in the coloring c, but there is no vertex in {u, v} adjacent to both vertices x and y. So the color class {u, v} witnesses the fact that c is not a b-coloring.

Next, suppose that c is not a b-coloring. Note that, as G has stability at most two, every vertex of G is adjacent (in G) to at least one vertex of any given color class of size 2. So, the witness for c not being a bcoloring is one of the following two: either it is a singleton color class whose vertex is non-adjacent to another singleton color class, or it is a color class {u, v} of size two, such that u is non-adjacent to some singleton color class, and v is non-adjacent to a different singleton color class. Clearly, the first situation corresponds to an augmenting path of M on one edge, and the second situation corresponds to an augmenting path of M on three edges.

Observe that coloring c from Lemma 2 is a maximum (minimum) bcoloring of G if and only if M is a minimum (maximum) strongly maximal matching of G.

b-continuity and b-monotonicity of graphs with stability at most two

In order to prove the b-continuity of graphs with stability at most two, we need the following result. Proof. Let P = (x 1 , x 2 , . . . , x k ). By basic results from matching theory, the only thing we need to prove is that M is again strongly maximal. Since the maximality of M is clear, suppose for contradiction that there is an augmenting path of length 3, say Q = (u, v, w, x). Necessarily vw is an edge of M \ M , and thus w.l.o.g. there is some i ∈ {1, 2, . . . , k -1} with v = x i and w = x i+1 . Moreover, u, x / ∈ V (M ). Thus both paths (x 1 , x 2 , . . . , x i , u) and (x, x i+1 , x i+2 , . . . , x k ) are augmenting paths for M and at least one of these paths is shorter than P . This is a contradiction to the choice of P . By Lemma 2, any b-coloring using k > χ(G) colors of a graph G of stability at most two corresponds to a strongly maximal matching M that is not maximum. By Berge's lemma [START_REF] Berge | Two theorems in Graph Theory[END_REF], there is an augmenting path for M . Using Lemma 3 we obtain a strongly maximal matching M of cardinality |M | + 1, which, again by Lemma 2, corresponds to a b-coloring with k -1 colors. Repeatedly applying this argument gives the following result. Given a maximum b-coloring of a graph G of stability at most two, we can thus find b-colorings for all values between χ(G) and χ b (G). Moreover, we can do this in polynomial time, provided we can find a minimum length augmenting path for a given matching in polynomial time. This is the aim of the following lemma that can be derived by a slight modification of Edmonds' blossom algorithm [START_REF] Edmonds | Paths, trees and flowers[END_REF].

Lemma 5. Let M be a matching in a graph G. Then, a minimum length augmenting path P in G with respect to M can be computed in polynomial time.

Lemma 5 together with the proof of Theorem 4 implies that given a graph G of stability at most two, and a b-coloring of G using k > χ(G) colors, we can compute in polynomial time a b-coloring for G with k -1 colors. Notice that the converse is not necessarily true, i.e., if we have a b-coloring of G using k < χ b (G) colors, we do not know how to compute in polynomial time a b-coloring for G with k + 1 colors. Indeed, we will prove in the next section that the problem of computing the b-chromatic number of a graph with stability at most two is NP-complete, even when restricted to the smaller class of co-bipartite graphs.

We now turn to the b-monotonicity of graphs of stability at most two. Theorem 6. Graphs of stability at most two are b-monotonic.

Proof. The class of graphs of stability at most two is closed under taking induced subgraphs. Thus we only have to prove that χ b is monotonously decreasing under the deletion of a vertex. In view of Lemma 2, it is sufficient to show that given a graph G of stability 2 and some vertex v ∈ V (G) the following holds: If there is a strongly maximal matching of G -v of size k, then there is a strongly maximal matching of G of size at most k + 1. This implies

χ b (G) ≥ χ b (G -v).
Let M be a strongly maximal matching of G -v. We now consider M as a matching of G. If M is a strongly maximal matching of G, we are done. So we assume that M is not strongly maximal, and thus there is an augmenting path P of length at most 3. We may choose P of minimum length among all augmenting paths of M in G. Note that P meets v, say P starts in v.

We assume first that P is of length 1, that is, v has an unmatched neighbor in G, say u. We claim the matching M = M ∪{uv} is strongly maximal, in which case we are done. Indeed, otherwise there is an augmenting path of length 3 for M , and uv is the central edge of this path. So, there is a neighbor of u, say w, that is not matched by M . In particular, v = w. Thus uw is disjoint from M , contradicting the maximality of M in G -v. This proves our claim. Now assume that P is of length 3, say

P = (v, u, w, x). Let M = (M \ {uw}) ∪ {vu, wx}. Suppose that M is not strongly maximal in G.
Then there is an augmenting path of length 3, with central edge either vu or wx. In either case, x or v has a neighbor in G that is unmatched by M and thus also by M , a contradiction either to the maximality of M in G -v or to the minimality of P . This completes the proof.

NP-hardness result for co-bipartite graphs

As mentioned in Section 1, Havet, Linhares-Sales and Sampaio [START_REF] Havet | b-coloring of tight graphs[END_REF] proved that the problem of determining if a tight co-bipartite graph G has χ b (G) = m(G) is polynomial-time solvable. However, the computational complexity of χ b in the class of co-bipartite graphs is left open. In the next theorem, we prove that b-coloring general co-bipartite graphs is a hard problem.

Theorem 7. Given a co-bipartite graph G and a natural number k, it is NP-complete to decide whether G admits a b-coloring with at least k colors.

Proof. By Lemma 2, it suffices to prove that it is NP-complete to decide whether a bipartite graph G admits a strongly maximal matching containing at most k edges, when G and k are given input.

Our reduction is from the minimum maximal matching problem which is to decide whether a given graph admits a maximal matching of at most k edges, for given k. This problem is NP-complete even if the instances are restricted to bipartite graphs, as shown by Yannakakis and Gavril [START_REF] Yannakakis | Edge dominating sets in graphs[END_REF].

Given a bipartite graph G with m edges, we define a new graph H G as follows. For each edge uv ∈ E(G) we introduce a set of new vertices

X uv = {x 1 uv , x 2 uv , x 3 uv , x 4 uv , x 1 vu , x 2 vu , x 3 vu , x 4
vu } and edges

F uv = {ux 1 uv , x 1 uv x 2 uv , x 2 uv x 3 uv , x 3 uv x 4 uv , x 1 uv x 1 vu , x 1 vu x 2 vu , x 2 vu x 3 vu , x 3 vu x 4 vu , vx 1 vu }. Note that X uv = X vu and F uv = F vu . Then H G is defined by V (H G ) = V (G) ∪ uv∈E(G) X uv , E(H G ) = uv∈E(G) F uv .
Clearly H G can be computed in polynomial time. Moreover, H G is bipartite since G is. For each edge uv ∈ E(G), we define the following auxiliary sets of edges in H G :

F ∈ uv = {ux 1 uv , x 2 uv x 3 uv , x 2 vu x 3 vu , vx 1 vu } and F / ∈ uv = {x 1 uv x 1 vu , x 2 uv x 3 uv , x 2 vu x 3 vu } We claim

the following:

Claim 8. There exists a minimum strongly maximal matching M of H G such that

x 3 uv x 4 uv / ∈ M for each edge uv ∈ E(G).
Moreover, M can be obtained from any minimum strongly maximal matching of H G in polynomial time.

In order to prove this claim, we proceed by contradiction. Assume that every minimum strongly maximal matching of H G contains at least an edge x 3 uv x 4 uv for some edge uv ∈ E(G), and let M be a minimum strongly maximal matching of H G having a minimum number of edges of the form x 3 uv x 4 uv . Note that the choice of M implies that for every edge uv ∈ E(G) we have that

(i) x 3 uv x 4 uv ∈ M if and only if x 1 uv x 2 uv ∈ M . If x 1 uv x 2 uv ∈ M then x 3 uv x 4 uv ∈ M , otherwise, M is not maximal. If x 3 uv x 4 uv ∈ M then x 1 uv x 2 uv ∈ M , otherwise, we could replace x 3 uv x 4
uv by x 2 uv x 3 uv in M (the resulting matching is strongly maximal as M is so), contradicting the choice of M .

(ii) If the edges x 3 uv x 4 uv and x 1 uv x 2 uv are in M , then we have that vertices u and x 1 vu are each matched by M . Otherwise, if u is unmatched, we can replace x 1 uv x 2 uv , x 3 uv x 4 uv ∈ M with the edges x 2 uv x 3 uv , ux 1 uv . This again yields a strongly maximal matching (since u has no neighbors unmatched by M ), contradicting the choice of M . We can use the same argument in the case x 1 vu is unmatched. This is also some of the steps in order to transform any minimum strongly maximal matching into the desired one. Now, let uv be and edge in the graph G such that x 3 uv x 4 uv ∈ M . By (i) and (ii), we can deduce that |M ∩ F uv | = 4. Consider the matching

M := (M \ F uv ) ∪ F / ∈ uv
We claim that M is strongly maximal. As M is smaller than M , we thus obtain the desired contradiction.

So assume M is not strongly maximal. Then, as u is matched, there is an augmenting path P of length 1 or 3 starting at v. Now, observe that all neighbors of v are of the form x 1 vw (for some w ∈ V (G)), and thus, as neither

x 1 vw x 2 vw nor x 1 vw x 2 vw x 3 vw x 4
vw is an augmenting path for the strongly maximal matching M , all neighbors of v are matched by M .

So, P has length 3, and it is easy to see that P has to end in some (unmatched) vertex w ∈ V (G) \ {u, v} (by the maximality of M , every vertex x 3 wz is matched by M , and by the choice of M , every vertex x 2 wz is matched by M ). By (i) and (ii), we know that

F vw ∩ M = F / ∈ vw . Consider the matching ( M \ F / ∈ vw ) ∪ F ∈ vw .
This matching is clearly strongly maximal, and has fewer edges of the form x 3 uv x 4 uv , contradicting the choice of M . (And this is the remaining step in order to transform any minimum strongly maximal matching into the desired one.) This ends the proof of Claim 8. Therefore, by Claim 8, we have that there is a minimum strongly maximal M in H G that verifies either

F uv ∩ M = F ∈ uv or F uv ∩ M = F / ∈ uv for each edge uv ∈ E(G).
Next we show that if M is a minimum maximal matching of G and M is a minimum strongly maximal matching of H G , |M | = |M | -3m. As explained above, this completes the proof.

Let M be a minimum maximal matching of G. Using the auxiliary sets F ∈ uv and F / ∈ uv , we define a strongly maximal matching M of H G by

M = uv∈M F ∈ uv ∪ uv / ∈M F / ∈ uv .
Note that |M | = |M | + 3m. Now, let M be a minimum strongly maximal matching of H G that verifies either

F uv ∩ M = F ∈ uv or F uv ∩ M = F / ∈ uv for each edge uv ∈ E(G)
. We define a maximal matching M of G by setting

M = {uv : uv ∈ E(G), F uv ∩ M = F ∈ uv }.
Clearly |M | = |M | -3m, which completes the proof. Proof. According to Lemma 2, the problem is equivalent to find a minimum strongly maximal matching (msmm) in a tree. We will do it for nontrivial trees by dynamic programming. In order to do so, we will define five functions F i (r, s), i = 1, . . . , 5, for a nontrivial tree T rs rooted at a leaf r with neighbor s. As we will apply them to the subtrees of a tree, we will assume that r can have neighbors outside T rs .

• F 1 (r, s): cardinality of a msmm of T rs such that r is unmatched, and ∞ if it does not exist.

• F 2 (r, s): cardinality of a msmm of T rs that uses the edge rs and such that s may or may not have an unmatched neighbor (this case will apply when r has no unmatched neighbor outside T rs ), and ∞ if it does not exist.

• F 3 (r, s): cardinality of a msmm of T rs that uses the edge rs and such that s cannot have an unmatched neighbor (this case will apply when r has already an unmatched neighbor outside T rs , so an unmatched neighbor of s will complete an augmenting path of length 3 in the whole tree), and ∞ if it does not exist.

• F 4 (r, s): cardinality of a msmm of T rs such that the vertex s is matched with some vertex different from r and the vertex r is considered as "already matched" (this case will apply when r is already matched with a vertex outside T rs ), and ∞ if it does not exist.

• F 5 (r, s): cardinality of a msmm of T rs such that the vertex s remains unmatched and the vertex r is considered as "already matched", and ∞ if it does not exist.

With these definitions, for the base case in which V (T rs ) = {r, s}, we have

• F 1 (r, s) = ∞ (if
r is unmatched and s has no further neighbors, the matching will never be maximal)

• F 2 (r, s) = 1 (precisely, the edge rs)

• F 3 (r, s) = 1 (precisely, the edge rs)

• F 4 (r, s) = ∞ (it is not feasible because s has no further neighbors)

• F 5 (r, s) = 0
For the case in which s has children v 1 , . . . , v k , we have

• F 1 (r, s) = min i=1,...,k {F 3 (s, v i )+ j=1,...,k;j =i min{F 4 (s, v j ), F 5 (s, v j )}}.
In order to obtain a maximal matching, we need to match s with some of its children, say v i . Since r will be unmatched, v i should not have an unmatched neighbor, in order to prevent an augmenting path of length 3. When considering the trees T sv j for j = i, the vertex s will have the status of "already matched". Furthermore, since we are already assuming that s has an unmatched neighbor, we do not need to care about the vertices v j being matched or not.

• F 2 (r, s) = 1 + i=1,...,k min{F 4 (s, v i ), F 5 (s, v i )}.
We will use the edge rs, and then when considering the trees T sv i for i = 1, . . . , k, the vertex s will have the status of "already matched". Furthermore, since s may or may not have an unmatched neighbor, we can take the minimum over F 4 and F 5 for each of the trees T sv i .

• F 3 (r, s) = 1 + i=1,...,k F 4 (s, v i ).
This case is similar to the previous one, but now the vertex s cannot have unmatched neighbors, so we will just consider F 4 for each of the trees T sv i .

• F 4 (r, s) = min{min i=1,...,k {F 2 (s, v i ) + j=1,...,k;j =i F 4 (s, v j )}, min i=1,...,k {F 3 (s, v i ) + j=1,...,k;j =i min{F 4 (s, v j ), F 5 (s, v j )}}} As in the first case, we need to match s with some of its children, say v i . But now, since r is assumed to be matched, s may or may not have an unmatched neighbor, depending on the matching status of the vertices v j with j = i. So we will take the minimum among allowing v i to have an unmatched neighbor and forcing v j , j = i, to be matched, or forbidding v i to have an unmatched neighbor and allowing v j , j = i, to be either matched or not.

• F 5 (r, s) = i=1,...,k F 1 (s, v i )
This last case is quite clear.

In this way, in order to obtain the cardinality of a minimum strongly maximal matching of a nontrivial tree T , we can root it at a leaf r whose neighbor is s and compute min{F 1 (r, s), F 2 (r, s)}. By keeping some extra information, we can also obtain in polynomial time the matching itself.

Tree-cographs

A graph is a tree-cograph if it can be constructed from trees by disjoint union and complement operations. Tree-cographs have been introduced by Tinhofer [START_REF] Tinhofer | Strong tree-cographs are Birkoff graphs[END_REF] as a generalization of trees and cographs.

Let

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs with V 1 ∩ V 2 = ∅. The union of G 1 and G 2 is the graph G 1 ∪ G 2 = (V 1 ∪ V 2 , E 1 ∪ E 2 ), and the join of G 1 and G 2 is the graph G 1 ∨ G 2 = (V 1 ∪ V 2 , E 1 ∪ E 2 ∪ V 1 × V 2 ). Note that G 1 ∨ G 2 = G 1 ∪ G 2 .
Tree-cographs can be recursively defined as follows: a graph G is a treecograph if and only if (i) G is a tree or a co-tree, or (ii) G is the union of two tree-cographs G 1 and G 2 , or (iii) G is the join of two tree-cographs G 1 and G 2 .

Notice that if (i) in the above definition is replaced by "G is a single vertex" then, the obtained graph is a cograph.

The notion of dominance sequence has been introduced in [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF] in order to compute the b-chromatic number of P 4 -sparse graphs and, in particular, cographs. Formally, given a graph G, the dominance sequence dom G ∈ Z N ≥ χ(G) , is defined such that dom G [t] is the maximum number of distinct color classes admitting dominant vertices in any coloring of G with t colors, for every t ≥ χ(G). The following results given in [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF] are very important in order to compute the b-chromatic number of graphs that can be decomposed recursively in modules via disjoint union or join operations.

Theorem 10 ([3]). Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs such that V 1 ∩ V 2 = ∅. If G = G 1 ∪ G 2 and t ≥ χ(G), then dom G [t] = min{t, dom G 1 [t] + dom G 2 [t]}. Theorem 11 ([3]). Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs such that V 1 ∩ V 2 = ∅. Let G = G 1 ∨ G 2 and χ(G) ≤ t ≤ |V (G)|. Let a = max{χ(G 1 ), t -|V (G 2 )|} and b = min{|V (G 1 )|, t -χ(G 2 )}. Then a ≤ b and dom G [t] = max a≤j≤b {dom G 1 [j] + dom G 2 [t -j]}.
In order to compute the dominance vector of a tree-cograph and its corresponding b-chromatic number, by Theorems 10 and 11, it is sufficient to compute the dominance vector for both trees and co-trees.

Dominance vector for trees

Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] have shown that the b-chromatic number of any tree T is equal to m(T ) -1 or m(T ), depending on the existence of a unique vertex in T called a pivot, defined as follows.

A vertex v of T is called dense if d(v) ≥ m(T ) -1. Call T pivoted if T has exactly m(T ) dense vertices, and contains a distinguished vertex v, called a pivot of T , such that: (1) v is not dense, (2) each dense vertex is adjacent either to v or to a dense vertex adjacent to v, and (3) every dense vertex adjacent to v and to another dense vertex has degree m(T ) -1.

Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] showed that a pivot is unique when it exists and that pivoted trees can be recognized in linear time. Moreover, they obtain the following result.

Theorem 12 ([11]). Let T be a tree. If T is pivoted then χ b (T ) = m(T )-1, otherwise χ b (T ) = m(T ). In both cases, a b-coloring of T with χ b (T ) colors can be obtained in linear time.

It is known that chordal graphs are b-continuous [12,[START_REF] Faik | La b-continuité des b-colorations : complexité, propriétés structurelles et algorithmes[END_REF] and thus trees are b-continuous as well. Therefore, we may derive the following result concerning the dominance vector for trees.

Lemma 13. Let T be a nontrivial tree with maximum degree ∆. Then, dom

T [i] = i, for 2 ≤ i ≤ χ b (T ). Moreover, dom T [i] = 0 for any i > ∆ + 1.
Moreover, it is not difficult to obtain a b-coloring of a tree T with i colors from one with i + 1 colors in polynomial time, for 2 ≤ i < χ b (T ). Lemma 14. Let T be a pivoted tree. Then, dom T [m(T )] = m(T ) -1.

Proof. By Theorem 12, if T is a pivoted tree, then χ b (T ) = m(T ) -1, so dom T [m(T )] ≤ m(T ) -1. Consider now the following coloring of T with m(T ) colors. Give color 1 to the pivot v of T . Since v is not dense, there are at least two dense vertices at distance 2 of v; give color 1 to one of them, say w. Now color the dense vertices using the m(T ) different colors and color their neighbors in such a way that the only dense vertex that is not dominant is the common neighbor to v and w. It is easy to extend this coloring to a proper coloring of T with m(T ) colors.

We now show how to compute the values dom T [i] and a coloring of T with i colors and dom T [i] dominant vertices in linear time, for m(T ) < i ≤ ∆ + 1. For this, we need the following definition. Let T be a tree of maximum degree ∆ and let i be an integer such that m(T ) < i ≤ ∆ + 1. We define m i (T ) as the number of vertices in T of degree at least i -1.

It is not difficult to see that for a tree T , dom

T [i] ≤ m i (T ) < i, for values of i with m(T ) < i ≤ ∆ + 1.
Lemma 15. Let T be a tree of maximum degree ∆ and let i be an integer with m(T ) < i ≤ ∆ + 1. Then, dom T [i] = m i (T ), and a coloring of T with i colors and m i (T ) dominant vertices can be computed in linear time.

Proof. For convenience, set k = m i (T ). As i ≤ ∆ + 1, we have k > 0. Let P be a path disjoint from T that contains the i -k + 3 ≥ 4 vertices x, y, v 1 , v 2 , . . . , v i-k , z in this order. We construct a tree T disjoint from T by taking P and pending i -3 leaves from each vertex v j , with 1 ≤ j ≤ i -k. Obtain T from T and T by adding an edge between x and some leaf h of T .

By construction, m i (T ) = i, and thus also m(T ) = i. Further, T contains the dense vertices v 1 , v 2 , . . . , v i-k of T , and T contains k dense vertices of T . So, as both x and y have degree 2 in T (and thus either both or none of them are dense), we see that T is not pivoted. Hence, Theorem 12 yields that χ b (T ) = m(T ) = i, and a b-coloring of T with i colors can be computed in linear time. Now, the dominant vertices in T are exactly the k vertices of degree at least i -1 in T and the i -k vertices v 1 , . . . , v i-k in T . Therefore, by removing the tree T from T we obtain the desired coloring of T with i colors and exactly k dominant vertices. Moreover, notice that the distance in T between a dense vertex in T and a dense vertex in T is at least equal to 4. Hence, by using Irving's and Manlove's algorithm [START_REF] Irving | The b-chromatic number of a graph[END_REF] for b-coloring T with i colors, we can forget the tree T and thus, the coloring of T with i colors and m i (T ) dominant vertices can be done in O(|V (T )|) time.

Dominance vector for co-trees

Let G be a graph and M be a matching of it. Let S 1 (G, M ) be the number of unmatched vertices that have at least an unmatched neighbor and S 2 (G, M ) be the number of edges of M that are the center of an augmenting path of length 3 for M . Now, let F (G, k) be the minimum of S 1 (G, M ) + S 2 (G, M ) over all the matchings M of G with |M | = k. Now, let G be a graph with stability at most two and consider a coloring of it. Let M be the matching of G corresponding to that coloring. The number of color classes without a dominant vertex is exactly

S 1 (G, M ) + S 2 (G, M ). So, for χ(G) ≤ i ≤ |V (G)|, dom G [i] = i -F (G, |V (G)| -i).
We will show how to compute F (T, k) for a tree T and a nonnegative integer k in polynomial time.

Theorem 16. If G is a co-tree, then dom G can be computed in polynomial time.

Proof. As we noticed above, if G is nontrivial, then the problem is equivalent to compute F (G, k), for χ(G) ≤ k ≤ |V (G)|. We will do it by dynamic programming. In order to do so, and in a similar way as in Theorem 9, we will define seven functions F i (r, s, k), i = 1, . . . , 7, for a nontrivial tree T rs rooted at a leaf r with neighbor s and a nonnegative integer k. As we will apply them to the subtrees of a tree, we will assume that r can have neighbors outside T rs . Nevertheless, we will count for S 2 just the edges of M ∩E(T rs ) and for S 1 the vertices of V (T rs ), with the exception of r when it is unmatched but has already an unmatched neighbor outside T rs , in order to avoid double counting.

For i = 1, . . . , 7, F i (r, s, k) will be the minimum of S 1 (T rs , M )+S 2 (T rs , M ) over all the matchings M with |M | = k such that:

• F 1 (r, s, k): r is unmatched and s is matched by M with some vertex different from r.

• F 2 (r, s, k): M uses the edge rs and r has no unmatched neighbor outside T rs .

• F 3 (r, s, k): M uses the edge rs and r has an unmatched neighbor outside T rs .

• F 4 (r, s, k): the vertex s is matched by M with some vertex different from r and the vertex r is already matched with a vertex outside T rs .

• F 5 (r, s, k): the vertex s remains unmatched and the vertex r is already matched with a vertex outside T rs .

• F 6 (r, s, k): r is unmatched, s remains unmatched, and r has no unmatched neighbor outside T rs .

• F 7 (r, s, k): r is unmatched, s remains unmatched, and r has an unmatched neighbor outside T rs (we will not count r for S 1 as we assume it is already counted).

In any case, the value will be ∞ if no such M does exist. With these definitions, for the base case in which V (T rs ) = {r, s}, we have

• F 1 (r, s, k) = ∞ (s has no further neighbors) • For i = 2, 3, F i (r, s, 1) = 0 (we define M = {rs}), F i (r, s, k) = ∞ for k = 1.
• F 4 (r, s, k) = ∞ (it is not feasible because s has no further neighbors)

• F 5 (r, s, 0) = 0, F 5 (r, s, k) = ∞ for k = 0. • F 6 (r, s, 0) = 2, F 6 (r, s, k) = ∞ for k = 0. • F 7 (r, s, 0) = 1, F 7 (r, s, k) = ∞ for k = 0.
For the case in which s has children v 1 , . . . , v , we have

• F 1 (r, s, 0) = ∞, F 1 (r, s, k) = min k 1 +•••+k =k min i=1,..., {F 3 (s, v i , k i ) + j=1,.
.., ;j =i min{F 4 (s, v j , k j ), F 5 (s, v j , k j )}} for k > 0.

We need to match s with some of its children, say v i . Since r will be unmatched, s will have an unmatched neighbor outside T sv i , and we do not need to distinguish about the vertices v j being matched or not in T sv j , for j = i. When considering the trees T sv j for j = i, the vertex s will have the status of "already matched".

• F 2 (r, s, 0) = ∞, F 2 (r, s, k) = min k 1 +•••+k =k-1 i=1,..., min{F 4 (s, v i , k i ), F 5 (s, v i , k i )} for k > 0.
We will use the edge rs, and then when considering the trees T sv i for i = 1, . . . , , the vertex s will have the status of "already matched" and we will use k -1 edges in total (thus for k = 0 it is not feasible). Furthermore, since r has no unmatched neighbor, we can take the minimum over F 4 and F 5 for each of the trees T sv i , and in none of the cases the edge rs will be the center of an augmenting path of length 3.

• F 3 (r, s, 0) = ∞, F 3 (r, s, k) = min k 1 +•••+k =k-1 min{ i=1,..., F 4 (s, v i , k i ), 1 + i=1,..., min{F 4 (s, v i , k i ), F 5 (s, v i , k i )}} for k > 0.
This case is similar to the previous one, but now, since r has an unmatched neighbor, we distinguish between the case in which we consider F 4 for each of the trees T sv i so that the edge rs will not be the center of an augmenting path of length 3, and the case in which we take the minimum over F 4 and F 5 for each of the trees T sv i and we allow the edge rs being the center of an augmenting path of length 3.

In that case we will assume indeed that the edge rs becomes the center of an augmenting path of length 3, because otherwise the minimum will be attained by the previous case.

• F 4 (r, s, 0) = ∞, F 4 (r, s, k) = min k 1 +•••+k =k min{ min i=1,..., {F 2 (s, v i , k i ) + j=1,..., ;j =i F 4 (s, v j , k j )}, min i=1,..., {F 3 (s, v i , k i )+ j=1,..., ;j =i min{F 4 (s, v j , k j ), F 5 (s, v j , k j )}}} for k > 0.
As in the first case, we need to match s with some of its children, say v i . But now, since r is assumed to be matched, s may or may not have an unmatched neighbor, depending on the matching status of the vertices v j with j = i. So we will take the minimum among allowing v i to have an unmatched neighbor and forcing v j , j = i, to be matched, or forbidding v i to have an unmatched neighbor and allowing v j , j = i, to be either matched or not.

• F 5 (r, s, k) = min k 1 +•••+k =k min{ i=1,..., F 1 (s, v i , k i ), min i=1,..., {F 6 (s, v i , k i ) + j=1,..., ;j =i F 1 (s, v j , k j )}, 1 + i=1,..., min{F 1 (s, v i , k i ), F 7 (s, v i , k i )}}
We will take the minimum over three cases: either all the v i will be matched, or exactly one of them will be unmatched, or at least two of them will be unmatched. In this last case we count s as an unmatched vertex with unmatched neighbor but we do not force explicitly two of the v i to be unmatched, because otherwise the minimum will be attained by one of the previous cases.

• F 6 (r, s, k) = 2 + min k 1 +•••+k =k i=1,..., min{F 1 (s, v i , k i ), F 7 (s, v i , k i )}
We are counting r and s as unmatched vertices with an unmatched neighbor.

• F 7 (r, s, k) = 1 + min k 1 +•••+k =k i=1,..., min{F 1 (s, v i , k i ), F 7 (s, v i , k i )}
We are counting just s as an unmatched vertex with unmatched neighbor, since r is assumed to be already counted.

Notice that as the values of the functions F i are bounded by the number of vertices of the corresponding tree, and k is also bounded by that number, taking the minimum over k 1 + • • • + k = k of some combination of these F i is equivalent to solve a polynomially bounded number of knapsack problems where both the weights and the utilities are polynomially bounded as well, so this can be done by dynamic programming in polynomial time [START_REF] Dantzig | Discrete-variable extremum problems[END_REF]. We can rewrite all the expressions for F 1 , . . . , F 7 as the minimum over a polynomial number of knapsack problems based on the precomputed functions for the corresponding subtrees of the tree.

In this way, in order to obtain F (T, k) for a nontrivial tree T , we can root it at a leaf r whose neighbor is s and compute min{F 1 (r, s, k), F 2 (r, s, k), F 6 (r, s, k)}. By keeping some extra information, we can also obtain in polynomial time the matching itself.

b-continuity and b-monotonicity of tree-cographs

The following result was proved for union and join of graphs.

Lemma 17. [3] Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs such that V 1 ∩ V 2 = ∅. If G 1 and G 2 are b-continuous, then G 1 ∪ G 2 and G 1 ∨ G 2 are b-continuous.
As a corollary of the lemma, Theorem 4, and the b-continuity of chordal graphs [12,[START_REF] Faik | La b-continuité des b-colorations : complexité, propriétés structurelles et algorithmes[END_REF], we have the following result.

Theorem 18. Tree-cographs are b-continuous.

Concerning the b-monotonicity, the following results are known for general graphs and for union and join of graphs. Lemma 19. [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF] Let G be a graph. The maximum value of dom G

[t] is at- tained in t = χ b (G). Lemma 20. [3] Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two graphs such that V 1 ∩V 2 = ∅, and let G = G 1 ∪G 2 . Assume that for every t ≥ χ(G i ) and every induced subgraph H of G i we have dom H [t] ≤ dom G i [t], for i = 1, 2. Then, for every t ≥ χ(G) and every induced subgraph H of G, dom H [t] ≤ dom G [t] holds. Lemma 21. [3] Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two b-continuous graphs such that V 1 ∩V 2 = ∅, and let G = G 1 ∨G 2 . Assume that for every t ≥ χ(G i ) and for every induced subgraph H of G i we have dom H [t] ≤ dom G i [t], for i = 1, 2. Then, for every t ≥ χ(G) and for every induced subgraph H of G, dom H [t] ≤ dom G [t] holds.
In order to prove the b-monotonicity of tree-cographs, we need the following two lemmas.

Lemma 22. Let T be a tree and H an induced subgraph of T . Then for every

t ≥ 2, dom H [t] ≤ dom T [t].
Proof. It is clear that it holds for t ≤ χ b (T ). If T is a pivoted tree, then either m(H) < m(T ) or the connected component of H containing the dense vertices is a pivoted tree as well. In any case, dom H [m(T )] ≤ dom T [m(T )]. For t > m(T ), let T j , j = 1, . . . , k, be the connected components of H. It is clear that j=1,...,k m t (T j ) ≤ m t (T ), so by Theorem 10, dom

H [t] ≤ dom T [t].
Lemma 23. Let G be a graph with stability at most two and H an induced subgraph of G. Then for every t ≥ χ(G), dom

H [t] ≤ dom G [t].
Proof. The class of graphs of stability at most two is closed under taking induced subgraphs. Thus we only have to prove that dom G [t] for a fixed t is monotonously decreasing under the deletion of a vertex. Let H Let M be a matching of H that realizes this minimum, and consider M as a matching of G. We need to find a matching M of G with |M | = |M |+1, which is always posible, since t > χ(G) and then |V (G)|-t is strictly smaller than the size of a maximum matching of G. If v has no unmatched neighbor but it is the end of an augmenting path of length 3 for M in G, say vxyw, let M = M \ {xy} ∪ {vx, yw}. There are no new unmatched vertices, so S 1 (G, M ) ≤ S 1 (H, M ) and no edge of M becomes the center of an augmenting path of length 3 for M in G. Neither does vx, since v had no unmatched neighbor. If yw is the center of an augmenting path of length 3 for M in G, then w was for M an unmatched vertex of H having an unmatched neighbor. In this case S 2 (G, M ) = S 2 (H, M ) + 1 but S 1 (G, M ) ≤ S 1 (H, M ) -1, so we are done.

= G -v for some vertex v of G. It is clear that dom H [t] ≤ dom G [t] for χ(G) ≤ t ≤ χ b (G) and for t > |V (H)| = |V (G)| -1. For |V (H)| ≥ t > χ b (G),
Finally, if v does not have an unmatched neighbor and it is not the end of an augmenting path of length 3 for M in G, i.e., S 1 (G, M ) = S 1 (H, M ) and S 2 (G, M ) = S 2 (H, M ), let P be a minimum length augmenting path in G with respect to M , and let M = (M \E(P ))∪(E(P )\M ). There are no new unmatched vertices, so S 1 (G, M ) ≤ S 1 (H, M ) and no edge of M becomes the center of an augmenting path of length 3 for M in G. If P is of length 1, then S 2 (G, M ) ≤ S 2 (H, M ) + 1 but S 1 (G, M ) ≤ S 1 (H, M ) -2, so we are done. If P is of length 3, we are eliminating an augmenting path of length 3 and no new edge becomes the center of an augmenting path of length 3, because otherwise there were couples of adjacent unmatched vertices and we are supposing P is of minimum length. Thus S 1 (G, M ) = S 1 (H, M ) = 0 and S 2 (G, M ) ≤ S 2 (H, M )-1, so we are done. If there were no augmenting paths of length 1 or 3, M is a strongly maximal matching of G and then |V (G)| -|V (H)| + t = t + 1 ≤ χ b (G), a contradiction because we were supposing t > χ b (G). So, we can conclude the following.

Theorem 24. Tree-cographs are b-monotonic.

Proof. As tree-cographs are hereditary, it is enough to prove that given a tree-cograph G, χ b (G) ≥ χ b (H), for every induced subgraph H of G. By the decomposition structure of tree-cographs [START_REF] Tinhofer | Strong tree-cographs are Birkoff graphs[END_REF] and Theorem 18, Lemmas 20, 21, 22, and 23, an induction argument shows that for every tree-cograph G, every t ≥ χ(G), and every induced subgraph H of G, dom H

Lemma 3 .

 3 Let M be a strongly maximal matching of a graph G and let P be a minimum length augmenting path in G with respect to M . Then, the matching M = (M \ E(P )) ∪ (E(P ) \ M ) is a strongly maximal matching of G, and |M | = |M | + 1.

Theorem 4 .

 4 Graphs of stability at most two are b-continuous.

Theorem 9 .

 9 In the class of co-trees, χ b can be computed in polynomial time.

  Note that it suffices to consider this sequence until t = |V (G)|, since dom G [t] = 0 for t > |V (G)|. Therefore, in the sequel we shall consider only the dominance vector (dom G [χ(G)], . . . , dom G [|V (G)|]). Notice that a graph G admits a b-coloring with t colors if and only if dom G [t] = t. Moreover, it is clear that dom G [χ(G)] = χ(G).

  as we observed before, since G and H have stability at most two, domG [t] = t -F (G, |V (G)| -t), and dom H [t] = t -F (H, |V (H)| -t), where F (X, k) stands for the minimum sum of the number of unmatched vertices that have at least an unmatched neighbor and the number of edges of M that are the center of an augmenting path of length 3 for M , over all the matchings M of a graphX with |M | = k. Then dom G [t] ≥ dom H [t] if and only if F (G, |V (G)| -t) = F (G, |V (H)| + 1 -t) ≤ F (H, |V (H)| -t).

  We will consider now three cases. If v has an unmatched neighbor w, then let M = M ∪ {vw}. In this way, S 1 (G, M ) ≤ S 1 (H, M ) and no edge of M becomes the center of an augmenting path of length 3 for M in G. Moreover, if vw is the center of an augmenting path of length 3 for M in G, then w was for M an unmatched vertex of H having an unmatched neighbor. In this case,S 2 (G, M ) = S 2 (H, M ) + 1 but S 1 (G, M ) ≤ S 1 (H, M ) -1. In any case, F (G, |V (G)| -t) ≤ S 1 (G, M ) + S 2 (G, M ) ≤ S 1 (H, M ) + S 2 (H, M ) = F (H, |V (H)| -t).

  [t] ≤ dom G [t]holds. Let G be a tree-cograph, and let H be an induced subgraph of G. Ifχ b (H) < χ(G), then χ b (H) < χ b (G). Otherwise, χ b (H) = dom H [χ b (H)] ≤ dom G [χ b (H)], and by Lemma 19 dom G [χ b (H)] ≤ dom G [χ b (G)] = χ b (G). Hence χ b (G) ≥ χ b (H).

Acknowledgement: We would like to thank the anonymous referees for their careful reading and suggestions that helped us to improve the paper.

* Partially supported by UBACyT Grant 20020100100980, CONICET PIP 112-200901-00178 and 11220120100450CO, and ANPCyT PICT 2012-1324 (Argentina) and MathAm-Sud Project 13MATH-07 (Argentina-Brazil-Chile-France). † Currently in "Délégation" at INRIA Nancy -Grand Est, 2013-2015.


Raphaël Gillard
email: raphaël.gillard@insa-rennes.fr

Benoît Le Lepvrier
email: benoit.le-lepvrier@insa-rennes.fr

Renaud Loison
email: renaud.loison@insa-rennes.fr

Guy A E Vandenbosch
email: guy.vandenbosch@esat.kuleuven.be

On-Going Progress of SoftLAB Benchmark in 2014

Keywords: antenna simulation, benchmark, software tools. I

This paper presents the last edition of SoftLAB, the EurAAP antenna software benchmark. In the 2013-2014 run, two antenna test-cases have been proposed for simulation. The first one is an updated version of the triple-frequency GSM antenna previously studied in 2009 and 2013. The second one is a large-bandwidth monopole antenna in a complex surrounding environment. The specific goal is to reach results of extreme high quality.

Introduction

SoftLAB (Software OnLine Antenna Benchmark) is now well-known in the community of people using or developing modelling tools for antenna simulation in Europe. Started by the Antenna Software Initiative within the Antenna Center of Excellence (ACE) in 2005, it is a benchmark for antenna software that is now run yearly, in strong connection with the EuCAP conference [START_REF] Vandenbosch | The Antenna Software Initiative (ASI): ACE results and EuRAAP continuation[END_REF][START_REF] Gillard | New results from the SoftLAB benchmark of antenna software[END_REF].

Each year, a new set of challenging antenna test-cases is proposed for simulation in fall. The process is totally open and people are invited to participate in and to produce simulation results before the end of the year using their own simulation tools (either in-house or commercial). These results are then published and discussed at the EuCAP conference, in spring of the next year.

A detailed description of the past benchmark test-cases and associated results can be found in www.antennesavce.org, the EurAAP (European Association on Antennas and Propagation) portal. It gathers more than 110 simulations from more than 30 contributors and covers 5 successive benchmark runs addressing a total of 21 test-cases. This really constitutes a wealthy data-base for anyone interested in antenna simulation, whatever the numerical method or the antenna technology. All the results are fully available and can be downloaded from the portal by anyone registered in the EurAAP association.

In 2013, the specific EuCAP session in Gothenburg was a real success with a huge participation and fruitful exchanges. In 2014, the results of run#6 will be presented at the EuCAP 2014 conference in The Hague, The Netherlands. This benchmark run consists of two different structures that are briefly presented in the next section.

II. The 2013-2014 run

A. First structure

The first antenna topology to be benchmarked is shown in Fig. 1. It is a GSM antenna with triple-frequency band operation and CPW feeding. This antenna has been benchmarked twice already. The results of the first run (in 2008-2009) are discussed in detail in [START_REF] Vasylchenko | Quality assessment of computational techniques and software tools for planar antenna analysis[END_REF] and for clarity depicted in Fig. 2. These results were obtained by users who used the commercial software in the best possible way. Most possible causes of discrepancy were already addressed and ruled out. Non-addressed issues were:

-modeling of the feed: idealized feeds were used, characteristic for each software, i.e. the real connector used in the measurements was not taken into account, and the idealized feeds may differ considerably between software tools, -non-optimal use of software tool: although errors were (most probably) ruled out by the checking of the input by the software vendors, a non-optimal use of a tool cannot be ruled out, and this may have implications on the accuracy.

--Fig. 1. First antenna topology, inspired by the World GSM Antenna.

The specific goal of the second benchmark in 2012-2013 was to rule out as much as possible these remaining issues. To that goal, the software vendors were invited to do the benchmarking themselves, since they are the masters of their own tool and can be expected to use it in the most optimal way. Also, since in [START_REF] Vasylchenko | Quality assessment of computational techniques and software tools for planar antenna analysis[END_REF] it was pointed out that the actual feeding structure, thus including the connector, may be crucial in explaining the major discrepancies, it was expected that the vendors would concentrate on this. The results were presented at EuCAP 2013 in Gothenburg [START_REF] Vandenbosch | Benchmarking of optimally used commercial software tools for challenging antenna topologies, part 1 & 2: The 2012 -2013 run[END_REF], [START_REF] Vandenbosch | Benchmarking of optimally used commercial software tools for challenging antenna topologies[END_REF] and the "best" results are given in Fig. 3. It is clearly seen that the agreement between the simulations is much better than in the 2008-2009 run, especially at the lower frequencies. The differences are mainly in the high frequency region. There the results are still a bit "scattered". There are serious discrepancies above the -10 dB threshold. From the presentations made by the six software vendors involved, it was clear that there were mainly three reasons for this discrepancy:

-the fact that complete and detailed information concerning the connector configuration, including its internal structure, was missing (most vendors made a "best guess" for the connector topology), -the fact that not always the exact position of this connector was taken into account, and -when comparing with measurements, the cable feeding the connector (only FEKO really took the cable into account). These three issues are all concerned with the feeding topology.

After a thorough discussion between the EuRAAP Software WG and the software vendors, it was decided to make sure that in the 2013-1014 run all tools would simulate exactly the same configuration. Five points were addressed in this discussion: a) The positioning of the feed was measured very accurately and added to the description files. This was just overlooked last year. b) The material used is FR4. However, it is known that there is a spread on the parameters of this material. KU Leuven has provided the best estimates (based on measurements) for these values to the software vendors. The goal is that they all use these values. c) Concerning the connector, although the drawing provided by the manufacturer gives all dimensions that could really affect the electromagnetic behavior and the measurements, KU Leuven has provided a "reference" connector set-up, based on the drawing so that all vendors can use the same structure here. d) KU Leuven has generated a "sat" file fully describing the complete structure. Such a sat file is a standardized file widely used in the area of 3D CAD tools. This means that for the vendors whose software can handle this type of file, it is guaranteed that the structure put into the software is exactly the same. e) Concerning the measurements, KU Leuven will draft a measurement protocol, which is submitted for approval to the vendors, and which can then be further upgraded if necessary.

It has to be emphasized that it is sincerely hoped that this benchmark would deliver results with an intrinsic quality never reached before. The results will be presented and discussed thoroughly at the yearly EuRAAP Software WG Convened or Special Session at EuCAP 2014 in The Hague, The Netherlands.

B. Second structure

The second studied structure consists of a surrounded wideband antenna mounted on a large metallic structure. Although canonical, this structure combines several classical issues that may be encountered when analyzing surrounded wide-band antennas mounted on large platforms (such as satellites or vehicles). Because it involves small details (for instance the transmitting antenna) and very large elements (the metallic platform), it is intended to assess software tools with advanced capabilities such as multiple-region or multiresolution features. A global view of the structure is given in Fig. 4. More precisely, the test-case combines a planar diamond antenna operating from 4 to 9.5 GHz (detailed view in Fig. 5), a block of dielectric material very close to the radiating element and a large ground plane (l=1728 mm; w=1584 mm) with a vertical metallic plate (h=1008mm). The benchmark will consist in calculating the far fields (both co-and cross-polar) produced by the whole structure in two cut-planes and for the complete bandwidth.

Several candidate methods have already been identified that are particularly well suited to address this type of problems. Among them, the hybridization of Iterative Physical Optics (IPO) with Dual-Grid Finite-Difference Time-Domain method (DG-FDTD) has been specially developed by IETR [START_REF] Lepvrier | Hybridization of the dual-grid fdtd with the physical optics to analyze antennas mounted on large and complex platforms[END_REF] to deal with surrounded antennas working over a large frequency bandwith. To do so, it combines a time-domain multilevel analysis of both the antenna and its closest environment (DG-FDTD simulation) with a high-frequency approach (IPO) for the more remote elements. Because most of the calculations are carried out in the time domain, it is particularly efficient for large bandwidth characterization. One important output of the benchmark will thus be to see if such dedicated tools outperform more general-purpose solvers (such as full-3D commercial tools) regarding simulation time. Also, the comparison of the agreement between methods will be essential to see if the used assumptions in hybridized approaches (or any other simplified approaches) are detrimental to the overall accuracy.

More generally, the compared performance of time-domain and frequency-domain methods, the advantage resulting from any advanced treatment or the effect of available degrees of freedom in the simulation process will be addressed.

At the moment this paper is submitted, a few results have already been uploaded that will be presented and discussed in the EuCAP2014 conference.

Fig. 2 .

 2 Fig. 2. Benchmark results in 2009: seven software tools and a measurement.The differences are remarkable and occur over the whole band analyzed. A detailed discussion is given in[START_REF] Vasylchenko | Quality assessment of computational techniques and software tools for planar antenna analysis[END_REF].

Fig. 3 .

 3 Fig. 3. Benchmark results in 2013: six software vendors, 9 tools, and 17 simulations. These results were presented during the Convened Session of the EuRAAP Working Group on Software [4], [5].

Fig. 4 .Fig. 5 .

 45 Fig. 4. Second antenna test-case