1 Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamentode Computacion, Argentina. e-mail: [email protected]
2 Universidade Federal do Rio de Janeiro, Instituto de Matematica, NCE and COPPE,Brasil. e-mail: [email protected]
Abstract. A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family.We describe characterizations for biclique-Helly graphs, leading to polynomial time recog-nition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly,disk-Helly and neighborhood-Helly graphs.
Helly families of subsets have been studied in different contexts. In the scope ofgraph theory, this study has motivated the introduction of some classes of graphs,as clique-Helly graphs [6, 9, 10, 12, 19], disk-Helly graphs [2, 3], and neighborhood-Helly graphs [4]. These classes correspond to the cases where the families subject tothe Helly property are cliques, disks and neighborhoods, respectively.
Bicliques, in general, have been considered in some different contexts, e.g. [13,14, 16, 18].
In this work, we consider the graphs whose bicliques form a Helly family, thebiclique-Helly graphs. Besides the interest of examining bicliques in the scope ofthe Helly property, these graphs could be of interest in the study of retracts [11].In fact, retracts of bipartite graphs are related to neighborhood-Helly graphs [1]and the latter are related to biclique-Helly graphs in some different aspects. We alsomention that some optimization problems, as the edge modification problem, havebeen already studied for the class of biclique-Helly graphs [7].
We describe two characterizations for biclique-Helly graphs. Both of them leadto algorithms for recognizing biclique-Helly graphs, in polynomial-time complexity.Recall that a graph might have an exponential number of bicliques [15]. Therefore,
� Partially supported by UBACyT Grants X184, X127, X212, PICT ANPCyT Grant11-09112 and PID Conicet Grant, Argentina.
�� Partially supported by the Conselho Nacional de Desenvolvimento Cientıfico eTecnologico, CNPq, and Fundacao de Amparo a Pesquisa do Estado do Rio de Janeiro,FAPERJ, Brasil.
634 M. Groshaus, J.L. Szwarcfiter
the algorithm by Berge (see [4], [5], [19]) for recognizing Helly families would notrecognize biclique-Helly graphs within polynomial time. Finally, we relate the classof biclique-Helly graphs to those of clique-Helly graphs, disk-Helly graphs andneighborhood-Helly graphs.
Denote by G an undirected graph, V (G) and E(G) its vertex and edge sets,respectively. All graphs here considered are finite. A vertex v ∈ V (G) is universalwhen it is adjacent to every other vertex of G. Denote by N(v) the set of neighbors ofv ∈ V (G). Denote by P3 an induced path with three vertices, and by P3 its comple-ment. Write Ck for an induced cycle having k vertices. Say that a vertex v dominatesan edge e, when one of the extremes of e either coincides or is adjacent to v. When v
dominates every edge of G then v is an edge dominator of G. For S ⊆ V (G), denoteby G[S] the subgraph induced in G by S. Say that a subgraph H of G is isometric iffor any pair of vertices x, y of H , the distance between x, y in H is the same as in G.
A clique is a maximal subset of vertices inducing a complete subgraph. The diskDl(v) of v ∈ V (G) is the subset of vertices of G whose distance to v is less or equal tol. A biclique is a maximal subset B ⊆ V (G) inducing a complete bipartite subgraphin G. Write B = X ∪ Y for the corresponding bipartition, restricting to X, Y �= ∅.
Let A be a family of subgraphs of a graph G. Denote by GA = ∪H∈AH thesubgraph formed by the vertices and edges that are contained in the graphs of A.On the other hand, denote by G[A] the subgraph of G induced by ∪H∈AV (H).
We employ the following generalization of the concept of extended triangles [8,17]. Let S ⊆ V (G), |S| = 3. Denote by BS the family of bicliques of G that containat least two vertices of S.
The induced subgraph G[BS ] is called the extension of S. Clearly, GBSis a span-
ning subgraph of G[BS ].Let F be a family of subsets of some set. Say that F is intersecting when the sub-
sets of F pairwise intersect. On the other hand, when every intersecting subfamilyof F has a common element then F is a Helly family. A graph G is biclique-Helly(clique-Helly, neighborhood-Helly, disk-Helly) when its family of bicliques (cliques,neighborhoods, disks) is Helly.
The two characterizations of biclique-Helly graphs are formulated in Sections2 and 3, together with the corresponding recognition algorithms. The relationsbetween biclique-Helly graphs and the other mentioned classes are described inSection 3. In particular, in order to relate biclique-Helly and (open) neighborhood-Helly graphs, we employ a characterization of the latter class, which is also provedin Section 3. All the proposed characterizations are based on extensions.
2. A Characterization of Biclique-Helly Graphs
In this section, we describe a characterization for biclique-Helly graphs.The following lemmas are useful.
Lemma 1. Let G be a graph. Then G has neither triangles nor C5’s if and only if eachof the extensions in G is a bipartite graph.
Biclique-Helly Graphs 635
Fig. 1. Lemma 1
Proof. Let us suppose that S = {v0, v1, v2} is a subset of V (G) and examine G[BS ].If G[BS ] is empty, there is nothing to prove. Otherwise G[BS ] contains at least twovertices of S. First, discuss the case when there are only two vertices v1, v2 ∈ S inG[BS ]. Suppose v1, v2 are adjacent. Let X, Y be the subsets of neighbors and nonneighbors of v1 in G[BS ], respectively. By definition of G[BS ], any vertex of Y mustbe adjacent to v2. Because G has no triangles, both X, Y must be independent sets,meaning that G[BS ] is a bipartite graph. The second alternative is to assume thatv1, v2 are non adjacent. In this case, define X as to be the set of common neighborsof v1 and v2 in G[BS ], while Y is the subset formed by the remaining vertices of thisgraph. By a similar argument as above, we conclude that X ∪ Y is a bipartition ofG[BS ], as required.
We examine the situation where all vertices of S are in G[BS ]. The proof is byway of contradiction. Let us suppose that C is an odd cycle of length ≥ 7 of G[BS ],formed by the vertices x0, x1, . . . , x2k. Moreover, suppose that there is no odd cycleof length < |V (C)|. This implies that C is isometric. For each xi , let Bi be the bic-lique of BS that contains xi . Note that | Bi ∩ S |≥ 2 for any i. Thus, for each pairxi, xi′ of vertices of C there exists at least one vertex of S, denoted by vi,i′ , thatbelongs to both Bi and Bi′ . Moreover, if xixi′ ∈ E(C) then vi,i′ is adjacent preciselyto one of the vertices xi or xi′ , otherwise Bi ∪ Bi′ (and hence G itself) contains atriangle or a C5. Thus, each edge of C is dominated by some vertex of S. Withoutloss of generality, suppose that v0 dominates more than two edges of C. Since C
is isometric, this implies that v0 is adjacent to exactly two vertices of C, those twovertices being at distance 2 in C. Hence there exists a cycle C′ of the same size as C,that contains v0. Without loss of generality, suppose C′ = C and v0 = x0. It thenfollows from the isometry of C, that v3,4 �= v0. Denote v3,4 = v1.
From what precedes, it is easy to see that v2 is adjacent either to x3 or to x4. Inthe first case v2 and v1 are not adjacent and in the second case they are. In bothcases, v0 is therefore at distance ≥ 2of v2 and of v3. Let us now consider those twocases. �
Case 1. v2 is adjacent to x3:Hence v2 is not adjacent to v1. Consider B2k and note that x2k is at distance ≥ 2
of both v1 and v2 and at distance 1 of v0. Since in this case S is an independentset, the vertices of S ∩ B2k must belong to the same part of the bipartition of B2k.This implies that v0 /∈ V (B2k) and that both v1 and v2 are at distance 2 from x2k.Now, without loss of generality, suppose v1 ∈ B1. Observe that if x1v1 ∈ E(G) then
636 M. Groshaus, J.L. Szwarcfiter
the vertices x2k, x0, x1, v1, together with some vertex of B2k adjacent to x2k and v1,either contain a triangle or form an induced C5 in G. Thus x1v1 �∈ E(G). But in thiscase, x1, x2, x3, v1, together with a vertex of B2k adjacent to v1 and x1, leads to asimilar contradiction, as before.Case 2. v2 is adjacent to x4:
Hence v2 is also adjacent to v1. Again consider B2k. We claim that v2 is adjacentto x2k. Otherwise, both v1 and v2 are at distance ≥ 2 from x2k. It therefore followsfrom v1v2 ∈ E(G), that they can not both belong to B2k. Thus v0 ∈ V (B2k), which inturn implies that the other vertex vj of S, that belongs to B2k, being not adjacent tov0, is adjacent to x2k. Since we suppose that the claim is false, we must have vj = v1.This implies that the vertices x0, x1, x2, x3, v1 either form a C5 or contain a triangle,a contradiction. Thus, v2 is adjacent to x2k. Now consider B1. By a symmetricalargument, as in the preceding claim, we can show that v1 is adjacent to x1. Thus,v0, x1, v1, v2, x2k induce a C5, a contradiction. The proof is complete. �
Lemma 2. Let G be a biclique-Helly graph. Then G contains neither triangles norinduced C5’s.
Proof. By hypothesis, G is biclique-Helly. First, we show that G has no triangles.By contrary, assume that vertices v1, v2, v3 form a triangle and denote by ei theedge vivi+1(mod 3), 1 ≤ i ≤ 3. There exists some biclique Bi containing ei , for each i.Then {B1, B2, B3} constitutes a family of distinct intersecting bicliques. Because G isbiclique-Helly, there exists a vertex v common to B1, B2, B3. Clearly, v �= v1, v2, v3,as vi /∈ Bj if and only if j = i + 1(mod 3). It follows from v ∈ B1 that exactlyone between v1 and v2 is adjacent to v. Without loss of generality, suppose that v
is adjacent to v1 and not to v2. The latter implies v to be adjacent to v3, becausev ∈ B2. Consequently, v, v1, v3 form a triangle, meaning that v �∈ B3. That is, G
contains no vertex common to B1, B2, B3, contradicting G to be biclique-Helly.Next, we show that G has no C5’s. By contrary assume that G does contain
such a cycle. Extend each triple of successive vertices of this cycle to a biclique. Thisfamily is intersecting, so it has a common vertex v. Since G has no triangles, there isa pair of successive vertices in the cycle that are not adjacent to v. However, they liewith v in a biclique, a contradiction. Consequently, G does not contain C5’s. �
The following characterization of Helly families of subsets is employed in ourproposed characterization of biclique-Helly graphs.
Theorem 1 [4, 5]. Let F be a family of subsets Si of some set U . Then F is Helly if andonly if for every triple T of vertices of U , the intersection of the subsets Si satisfying|Si ∩ T | ≥ 2 is non empty.
Next, we prove our main theorem.
Theorem 2. A graph G is biclique-Helly if and only if G has no triangles and each ofits extensions has an edge dominator.
Biclique-Helly Graphs 637
Proof. By hypothesis, G is biclique-Helly, then by Lemma 2 it follows that G hasno triangles. Our aim is to prove that each non empty extension G[BS ] contains anedge dominator, for S ⊆ V (G), |S| = 3. Denote by BS the family of bicliques ofG that contain at least two vertices of S. Because G is biclique-Helly, there existssome vertex v common to all bicliques of BS . On the other hand, by Lemma 2, G
has neither triangles nor C5’s, we can apply Lemma 1 and conclude that G[BS ] isbipartite. Let X ∪ Y be a bipartition of it. Because GBS
is a spanning subgraph ofG[BS ], we know that GBS
is bipartite and X ∪ Y a bipartition of it. Without loss ofgenerality, let v ∈ X. We show that v is adjacent to all vertices of Y . Otherwise, ifw ∈ Y is not adjacent to v, because GBS
has no isolated vertices, there is an edge e
in GBSincident to w. Clearly, any biclique which contains the extreme vertices of e
does not contain v. The latter implies that v is not common to all bicliques of BS , acontradiction. Consequently, v is adjacent to all vertices of Y , meaning that v is anedge dominator of both GBS
and G[BS ]. The proof of necessity is complete.Conversely, let G be a graph with no triangles and for which every extension
contains an edge dominator. We prove that G is biclique-Helly. Let S ⊆ V (G),|S| = 3, and BS the collection of bicliques of G that contains at least two of thethe three vertices of S. Consider the extension G[BS ], relative to S. By hypothesis,G[BS ] has an edge dominator v. It is clear that if G[BS ] is bipartite, then v belongsto every biclique of GBS
. We show that G[BS ] is bipartite. Suppose it has an inducedodd cycle C2k+1. As v is an edge dominator and G has no triangles, v is adjacent tovertices v1, v3,..., v2k+1. But, also in this case a trangle arises, a contradiction. Thecase vi = v is similar.
As G[BS ] is bipartite, every biclique of GBSis also a biclique of G[BS ]. Conse-
quently, v is also contained in every biclique of GBS. Finally, every biclique of BS is
also a biclique of GBS. The latter implies that v is common to all bicliques of BS .
We conclude that for every subset S of three vertices, the family of bicliques ofG having at least two vertices of S contains a common vertex. By Theorem 1, thebicliques of G form a Helly family, thus, G is biclique-Helly. �
An algorithm for recognizing whether or not a given graph is biclique-Hellyfollows directly from Theorem 1. Given a graph G, for each S ⊆ V (G), |S| = 3, firstverify if S forms a triangle. In the affirmative case, answer NO and stop. Otherwise,construct V (G[BS ]) and G[BS ], and check if G[BS ] has an edge dominator. If theanswer is negative for some S, answer NO; otherwise answer YES.
The crucial step of the above algorithm is to construct the extension G[BS ],relative to S. We describe a method for it, based on the following observation.
Given a pair of vertices vi, vj ∈ V (G), there is a biclique of G containing vi, vj
and a third vertex vk, precisely when the following conditions hold:
(i) vivj ∈ E(G) and vk is adjacent to precisely one of vi or vj , or(ii) vivj �∈ E(G) and vk is adjacent to both vi, vj , or vk is non adjacent to both
vi, vj and there is a vertex vl adjacent to all vi, vj , vk.
We employ the following simplified notation, for the description of the algo-rithm. Write Ni to mean the set of neighbors of vi ∈ V (G) and Ni = V (G) \ Ni .For vi, vj ∈ V (G), write Nij = Ni ∩Nj , Nij = Ni ∩Nj and Ni ⊕Nj = (Ni ∪Nj) \(Ni ∩ Nj). Finally, for V ′ ⊆ V (G), let N(V ′) = ∪vi∈V ′Ni .
638 M. Groshaus, J.L. Szwarcfiter
Given S = {va, vb, vc} ⊆ V (G), the algorithm below constructs the vertex set ofthe extension G[BS ]. For simplicity, we write V ∗ with the meaning of V (G[BS ]).
First, define V ∗ = ∅. For each pair i, j ∈ {a, b, c}, i �= j , proceed as follows. Ifvivj ∈ E(G) then compute
V ∗ := V ∗ ∪ [Ni ⊕ Nj ],
otherwise compute
V ∗ := V ∗ ∪ Nij ∪ [N(Nij ) ∩ Nij ]
The correctness of the algorithm follows from the above observations (i) and (ii).All the computations of the algorithm can be easily performed in O(|V (G)|) time,except that of finding N(Nij ), which requires O|(E(G)|) time. Consequently, eachextension of G[BS ] can be constructed in O(|E(G)|) time, i.e. the overall complexityof the algorithm is O(|(V (G)|3|(E(G)|).
3. Biclique-Helly and Bichromatic Cliques
In this section, we formulate a second characterization for biclique-Helly graphs. Itis based on the idea of bichromatic cliques of a graph and leads to a weaker notionof clique-Helly graphs, the bichromatic-Helly graphs.
First we formulate a characterization for bichromatic-Helly graphs, which isemployed in that for biclique-Helly graphs.
Let G be a graph and U ∪W an arbitrary bipartition of its vertices. A clique C ofG is called bichromatic when it contains at least one vertex of each of the parts U andW . Say that G is bichromatic-Helly (relative to U, W ) when its bichromatic cliquesform a Helly family. Let T be a triangle of G and let CT be the set of bichromaticcliques of G that contain at least two vertices of the triangle T . Then the subgraphGCT
is called the bichromatic extension of T . Recall that GCTis a spanning subgraph
of G[CT ].The following proposition characterizes bichromatic-Helly graphs for general
bipartitions.
Theorem 3. Let G be a graph and U ∪ W a bipartition of its vertices and let CT bethe set of bichromatic cliques of G that contain at least two vertices of T . Then G isbichromatic-Helly if and only if for every triangle T , G[CT ] has a universal vertex.
Proof. Let G be a bichromatic-Helly graph and U ∪ W a bipartition of its vertices.Let T be a triangle of G and G[CT ] the bichromatic extension of T . We will showthat G[CT ] has a universal vertex. Observe that the cliques of CT pairwise intersect.By hypothesis, G is bichromatic-Helly. Then, there exists a vertex v belonging toevery clique of CT . It follows that v is a universal vertex of the subgraph GCT
. SinceGCT
is a spanning subgraph of G[CT ], it follows that G[CT ] has a universal vertex.
Biclique-Helly Graphs 639
Conversely, suppose that there exists a subfamily M of bichromatic cliques whichdoes not verify the Helly property. Consider M ′ = {M1, M2, · · · , Mk} ⊆ M a min-imal non Helly subfamily of M. Clearly k ≥ 3. By the minimality of M ′, there is avertex wi which belongs to every bichromatic clique of the subfamily M ′
i = M\{Mi}.Consider vertices w1, w2 and w3. They induce a triangle T in G.
Let CT be the subfamily of bichromatic cliques of G that contain at least twovertices of T and consider G[CT ]. By hypothesis, G[CT ] has a universal vertex v. Thismeans that v belongs to every bichromatic clique that contains at least two verticesof T , i.e., v belongs to every bichromatic clique of CT .
As M ′ ⊆ CT , v belongs to every bichromatic clique of M ′. �An algorithm for recognizing whether or not a given graph is bichromatic-Helly
follows directly from Theorem 3. Let G be a graph with bipartition U ∪W . For everytriangle T , construct G[CT ] and check if it has a universal vertex. If the answer isnegative for some T , answer NO; otherwise answer YES. The algorithm terminateswithin O(|V (G)|3|E(G)|) steps.
Next we fomulate the characterization for biclique-Helly graphs, based onbichromatic-Helly graphs.
Given a graph G, with vertices vi ∈ V (G), denote by H(G) the graph obtainedfrom G, by the following construction. For each vi ∈ V (G), define a pair of distinctvertices ui and wi in H(G). The edges of H(G) are as follows: ui, uj and wi, wj
are adjacent precisely when vi, vj are not, while ui, wj are adjacent when vi, vj arealso adjacent. Denote U = ∪ui and W = ∪wi . The bipartition U ∪ W is calledthe canonical bipartition of H(G). Let B be a biclique of G, with bipartition A ∪ B.Denote by UA, UB and WA, WB the subsets of U and W , corresponding to the setsA, B ⊆ V (G), respectively. Observe that UA ∪ WB and UB ∪ WA are cliques of H .Furthermore, these cliques are disjoint and the following lemma holds.
Lemma 3. Let G be a graph and U ∪ W the canonical bipartition of G. Then there isa 1-2 correspondence between the bicliques of G and the bichromatic cliques of H(G),such that each biclique B of G, with bipartition A∪B corresponds to the pair of disjointbichromatic cliques UA ∪ WB and UB ∪ WA of H(G), and conversely.
Next, we formulate the charactereization of biclique-Helly graphs, in terms ofbichromatic cliques.
Theorem 4. A graph G is biclique-Helly if and only if
1. G contains neither triangles nor induced C5’s.2. The graph H(G) is bichromatic-Helly, relative to its canonical bipartition.
Proof. Let G be a graph, and U ∪ W the canonical bipartition of H(G). SupposeG is biclique-Helly. Then Condition 1 holds because of Lemma 2. The followingobservation is useful for proving Condition 2.
Remark 1. Let ui ∈ U and wi ∈ W be the pair of vertices of H(G), correspondingto vi ∈ V (G). Then no vertex of H(G) is adjacent to both ui and wi .
640 M. Groshaus, J.L. Szwarcfiter
The reason why the above assertion is true is simple. Suppose uj ∈ U is adjacentto ui ∈ U in H(G). Then vi, vj are not adjacent in G. The latter implies wi, uj notadjacent in H(G). Similarly, wj ∈ W adjacent to ui implies wj not adjacent to wi .Consequently, Observation 1 is true.
Denote by C a family of intersecting bichromatic cliques of H(G). Let B be thefamily of bicliques of G, corresponding to C. Observe that this is a 1-1 correspon-dence, because the pair of cliques of H(G) which correspond to the same bicliqueof G are disjoint. Since G is biclique-Helly, the bicliques of G contain a commonvertex vi ∈ V (G). Let Bj be the biclique of B corresponding to the bichromaticclique Cj ∈ C. Because vi ∈ B1, it follows ui ∈ C1 or wi ∈ C1. Without loss ofgenerality, assume ui ∈ C1. We show that ui ∈ Cj , also for clique Cj ∈ C, j �= 1.Suppose the contrary and let ui �∈ Cj . Because vi ∈ Bj , it follows wi ∈ Cj . Ifwi ∈ C1 then ui and wi must be adjacent, which can not occur. Then ui ∈ C1 \ Cj
and wi ∈ Cj \ C1. Because C1 and Cj intersect, there must be some vertex of H(G)
belonging to C1 ∩Cj . Such a vertex would have to be simultaneously adjacent to ui
and wi , which contradicts Observation 1. Consequently, Cj contains ui , implyingthat H(G) is indeed bichromatic-Helly.
Conversely, by hypothesis Conditions 1 and 2 are true for some graph G. Weshow that G is biclique-Helly. Let B be an intersecting family of bicliques of G. Weconstruct a family C of bichromatic cliques of H(G). Each Bi ∈ B corresponds inH(G) to a pair of disjoint bichromatic cliques C′
i and C′′i . We choose Ci ∈ C as to
be C′i or C′′
i , according to the following rule. Arbitrarily, choose C1 = C′1. Note that
since B1 and Bi intersect, C1 must intersect C′i or C′′
i . Then, for i > 1, if C1 andC′
i intersect then choose Ci = C′i , and otherwise Ci = C′′
i . First, we show that C,as above obtained, is an intersecting family. Let Ci, Cj ∈ C. If i = 1 then C1 inter-sects any Cj , by construction. Let i, j �= 1. Since Bi and Bj intersect there existsvs ∈ Bi ∩ Bj . Then Ci contains us or ws . Without loss of generality, let us ∈ Ci .We will show that us ∈ Cj , meaning that Ci and Cj intersect. Suppose the contrary,us �∈ Cj . Then ws ∈ Cj . Consider the following alternatives for locating C1 ∩ Ci
and C1 ∩ Cj .
Case 1. C1 ∩ Ci ∩ U �= ∅ and C1 ∩ Cj ∩ U �= ∅Let ui ∈ C1 ∩ Ci ∩ U and uj ∈ C1 ∩ Cj ∩ U . If ui = us then C1 also contains
us , implying that uj is adjacent to us , because us, uj ∈ C1. Since ws ∈ Cj , uj isalso adjacent to ws , contradicting Observation 1. Consequently, ui �= us . Similarly,uj �= us . Then ui, uj , us are distinct. Since us, ui ∈ Ci , vs and vi are not adjacentin G. On the other hand, because ws, uj ∈ Cj , vs and vj are adjacent. Finally, vi
and vj are not adjacent, because ui, uj ∈ C1. Since vi, vj ∈ B1, there exists vp ∈ B1adjacent to both vi, vj . If vp, vs are adjacent then vp, vj , vs form a triangle, whichcontradicts Condition 1. Then vp, vs are not adjacent. Because vi, vs ∈ Bi , thereexists a vertex vq ∈ Bi , simultaneously adjacent to vi and vs . We conclude that vq isnot adjacent neither to vp nor vj , otherwise G would contain a triangle. Howeverin this situation, the vertices vi, vj , vs, vp, vq induce a C5 in G, not possible.
Case 2. C1 ∩ Ci ∩ U �= ∅ and C1 ∩ Cj ∩ W �= ∅Let ui ∈ C1 ∩Ci ∩U and wj ∈ C1 ∩Cj ∩W . Similarly as in Case 1, we know that
vi and vs are not adjacent. Because ws, wj ∈ Cj , vs and vj are also not adjacent, and
Biclique-Helly Graphs 641
ui, wj ∈ C1 implies vi, vj to be adjacent. Since vs, vi ∈ Bi , there exists some vertexvp ∈ Bi adjacent to vs and vi . We know that vp, vj are not adjacent, otherwise G
would contain a triangle. Also, because vs, vj ∈ Bj , there exists vq ∈ Bj , adjacentto vs, vj . If vp, vq or vq, vi are adjacent then G contains a triangle, otherwise thevertices vi, vj , vs, vp, vq induce a C5, which is forbidden by Condition 1. ThereforeCase 2 can also not occur.
Case 3. C1 ∩ Ci ∩ W �= ∅ and C1 ∩ Cj ∩ U �= ∅With the similar arguments as in Case 1, we conclude that Case 3 can not occur.The alternative C1∩Ci ∩W �= ∅ and C1∩Cj ∩W �= ∅ is equivalent to Case 1. The
conclusion is that Ci and Cj intersect, meaning that C is an intersecting family. ByCondition 2, H(G) is bichromatic-Helly. Then H(G) contains a vertex common toall cliques of C. Such a vertex corresponds in G to a vertex common to all bicliquesof B. Therefore G is biclique-Helly. �
An algorithm for recognizing whether or not a given graph is biclique-Hellyfollows directly from Theorem 4. Given a graph G, first verify if G has triangles orC5
′s. This requires O(|V (G)|3|E(G)|) time. Then construct the graph H(G), whichcan be done in O(|V (G)|2) time. Run the previous algorithm of this section, forrecognizing bichromatic-Helly graphs applied to the graph H(G). The algorithmterminates within O(|V (G)|5) steps.
4. Relations to Other Classes
In this section, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.
Proposition 1. If G is biclique-Helly then G is clique-Helly
Proof. Biclique-Helly graphs do not contain triangles and so they are clique-Helly.�
Next consider disk-Helly graphs.
Proposition 2. Let G be a disk-Helly graph with no triangles. Then G is biclique-Helly.
Proof. First, we will prove that if G is disk-Helly and has no triangles, then it isC5 − f ree. By contrary assume that the vertices v1, . . . , v5 form a C5. Considerthe disks D1(v2), D1(v3) and D1(v5). Since these disks are a Helly family, there is avertex v adjacent to v2, v3, v5. Then v forms a triangle with v2 and v3, contradictingthe hypothesis. Now we will prove that the family of bicliques of G is Helly. LetB = {B1, . . . , Bk} be an intersecting family of bicliques. For each vertex v of eachbiclique Bj of B, consider the disk D2(v). Observe that if v ∈ Bj , the vertices ofBj are included in the set of vertices of D2(v). Consequently, the family of disks{D2(v) | v ∈ ∪Bj } is also intersecting. As G is disk-Helly, there is a vertex z whichbelongs to every D2(v). We are going to prove that z belongs to every biclique Bi of
642 M. Groshaus, J.L. Szwarcfiter
B. Let Xi , Yi be the bipartition of the vertices of Bi into independent sets. Suppose z
does not belong to Bi . As G has no triangles, z can not be adjacent simultaneouslyto a vertex of Xi and a vertex of Yi . Then, we can assume that Xi ∪ {z} is an inde-pendent set. Then there is a vertex w ∈ Yi which is not adjacent to z. As z ∈ D2(w),there exists a vertex z′ adjacent to z and w. Let v be a vertex of Xi . If z′ is adjacentto v then z′, v, w forms a triangle contradicting the hypothesis. As z ∈ D2(v), thereis a vertex z′′ adjacent to z and v. Because of the triangle-free assumption, z′′ istherefore neither adjacent to w nor to z′. Thus, the vertices v, w, z′, z, z′′ induce aC5 or contain a triangle as an induced subgraph which is an absurd. Then, z belongsto Bi for 1 ≤ i ≤ k. �
Finally, consider the class of neighborhood-Helly graphs. We describe a char-acterization of this class of graphs, in terms of extensions. It will be useful for ourpurpose of relating it to biclique-Helly graphs. Start with the following lemma.
Lemma 4. Let G be a neighborhood-Helly graph. Then G has no triangles.
Proof. Let G be a graph and T be a triangle of G, with vertices v1, v2 and v3. WriteNi to mean the set of neighbors of vi ∈ V (G). Consider the family of neighborhoodsW = {N1, N2, N3}. Since W is an intersecting family and since vj ∈ Nj , there existsa vertex v4 in G that is adjacent to v1, v2 and v3. Now consider the intersectingfamily W4 = W ∪ {N4}. As vj /∈ Nj , there exists a vertex v5 �= vj , j = {1, 2, 3, 4},adjacent to v1, v2, v3 and v4. Following this procedure, we can construct the familyWi = W ∪ {Ni} of intersecting neighborhoods and assure the existence of a ver-tex vi+1 �= vj , adjacent to vj for 1 ≤ j ≤ i. However, G is finite, leading to acontradiction. Then G can not have triangles. �
Let S be an independent set of G, |S| = 3, and G[BS ] its extension. Denote byV2(S) ⊆ V (G[BS ]) the subset of vertices which are adjacent to at least two verticesof S.
Theorem 5. A graph G is neighborhood-Helly if and only if G has no triangles and forevery independent set S of size 3, V (G[BS ]) contains a vertex adjacent to all verticesof V2(S).
Proof. Let S = {v1, v2, v3} be a set of pairwise non adjacent vertices and G[BS ]its extension. Consider V2(S). If V2(S) = ∅, there is nothing to show. Otherwise,it is clear that the family of neighborhoods of vertices of V2(S) is intersecting. Byhypothesis, there is a vertex w which belongs to every neighborhood of the fam-ily. Moreover, since G is triangle-free, for any s ∈ V2(S), the vertices vertices w, s,together with the two vertices of S adjacent to s are included in some biclique ofBS . Thus, w ∈ V (G[BS ]), and is adjacent to all vertices of V2(S), as required.
Conversely, let G be a graph satisfying the hypothesis. By way of contradic-tion, assume that G is not neighborhood-Helly. For vi ∈ V (G), denote by Ni theneighborhood of vi . Let N = {N1, N2,...,Nl}, l ≥ 3, be a minimal subfamily ofneighborhoods of G which is not Helly. Then for each i = 1, ..., l, N \{Ni} is a Helly
Biclique-Helly Graphs 643
A B C D
Fig. 2. Graphs A, B, C, D
family, and therefore has a non empty intersection. Fix wi ∈ ∩j �=iNj . We claim thatvi �= wj , 1 ≤ i, j ≤ l. Clearly, if i �= j the claim holds because wi ∈ Nj and vj /∈ Nj .Examine the alternative, vi = wi . It implies that vi is adjacent to vk for any k �= i.Moreover, such a k must exist because l ≥ 3. Since Ni and Nk intersect, there existsa vertex w which forms a triangle with vi and vk, a contradiction. Consequently,wi �= vj . Furthermore, wi, wj must be distinct, for i �= j . Finally, we assert thatwi, wj are non adjacent. Otherwise, if wi, wj are adjacent, consider any vk, k �= i, j .By the above claim, vk �= wi, wj . Since wi, wj ∈ Nk, it follows that wi, wj , vk forma triangle, a contradiction. Then S = {w1, w2, w3} is an independent set. Considerthe extension G[BS ]. Observe that every Ni contains at least two of the vertices ofS. Thus, vi is adjacent to at least two vertices of S and then belongs to V2(S). Byhypothesis, there is a vertex w adjacent to every vertex of V2(S). Then, w belongsto Ni for 1 ≤ i ≤ l, a contradiction. �
Theorem 6. Let A, B, C and D be the graphs of Figure 2. Let G be a neighborhood-Helly graph, with no C5’s, and such that every induced subgraph A of it extends to oneof the subgraphs B, C or D. Then G is biclique-Helly.
Proof. By Lemma 4, G has no triangles. By Theorem 2, we only have to prove thateach non empty extension has an edge dominator. Let S ⊆ V (G), |S| = 3, andG[BS ] the extension of S. By Lemma 1, G[BS ] is a bipartite graph. In the case wherethere are only two vertices of S in V (G[BS ]), clearly the theorem follows.
Discuss the case where S ⊆ V (G[BS ]). First, suppose that S is an independentset. By Theorem 5 there exists a vertex v in V (G[BS ]) adjacent to every vertex ofV2(S). As G[BS ] is a bipartite graph, it follows that v is an edge dominator of G[BS ],as required.
Consider the case when the subset S = {v1, v2, v3} induces a P3, with v1, v2 nonadjacent. Let X and Y be the bipartiton of G[BS ], v1, v2 ∈ X. In the case |X| = 2,it is clear that v3 is an edge dominator of G[BS ]. We analyze the case |X| ≥ 3. Firstwe prove that the family {N(v), v ∈ X} is intersecting. Observe that for any w ∈ X,either w is adjacent to v3 or there is a biclique containing v1, v2, w. Consequently,N(w) ∩ N(v1) �= ∅ and N(w) ∩ N(v2) �= ∅. To complete the proof of our assertion,we show below that N(w1) ∩ N(w2) �= ∅, for any w1, w2 ∈ X \ {v1, v2}.
Assume the contrary, and suppose that there are two vertices, w1, w2 ∈ X \{v1, v2} with no common neighbor. By definition of G[BS ], there exist verticesvw1 , vw2 ∈ Y , vw1 �= vw2 adjacent to w1 and w2 respectively, and both adjacentto v1 and v2. As w1 and w2 have no common neighbor, vertices w1, vw1 , v1, vw2 , v2
644 M. Groshaus, J.L. Szwarcfiter
induce the graph A which does not extend to any of the graphs B, C or D, whatleads to a contradiction. Then {N(v), v ∈ X} is an intersecting family. As G is neigh-borhood-Helly, there is a vertex v adjacent to every vertex w ∈ X, v ∈ V (G[BS ]).Then, v is an edge dominator in G[BS ]. By Theorem 2, G is biclique-Helly.
Examine the case where S induces the complement of a P3 in G. Similarly asin Lemma 1, by applying the definition of G[BS ], we conclude that G contains atriangle or a C5, contradicting the hypothesis. Finally, the case where S induces atriangle also does not occur, completing the proof. �
Theorem 7. Let G be a graph having no subgraph isomorphic to the graph C of Figure2. If G is biclique-Helly then it is also neighborhood-Helly.
Proof. By Theorem 5, we only have to prove that for every independent set of threevertices S = {v1, v2, v3}, its extension G[BS ] has a vertex v adjacent to V2(S). Recallthat as G is biclique Helly, by Lemma 1, G[BS ] is a bipartite graph. Let X, Y be abipartition of vertices of G[BS ], S ⊆ X. Suppose there is no edge dominator in X. ByTheorem 2, since G is biclique-Helly, G[BS ] has an edge dominator w. Then w ∈ Y .As none of vertices vi, i = 1, 2, 3 are edge dominators, there exist distinct verticesw1, w2, w3 ∈ Y with vi adjacent to wj precisely when i �= j , for i, j = 1, 2, 3.Then, the vertices v1, w3, v2, w1, v3, w2, w induce the graph C of Figure 2, absurd.Consequently, G[BS ] has an edge dominator in X. �
Acknowledgements. To the referee for the careful reading and for providing valuable sugges-tions which improved the paper. In particular, he suggested the present version of the proofof Lemma 1, which is shorter and more elegant than the authors’ previous proof.
References
1. Bandelt, H.-J., Farber, M., Hell, P.: Absolute reflexive retracts and absolute bipartitegraphs. Discrete Applied Mathematics 44, 9–20 (1993)
2. Bandelt, H.-J., Pesch, E.: Dismantling absolute retracts of reflexive graphs. European J.Combinatorics 10, 211–220 (1989)
3. Bandelt, H.-J., Prisner, E.: Clique graphs and Helly graphs. J. Combin Theory B 51,34–45 (1991)
4. Berge, C.: Hypergraphs. North Holland Mathematical Library, vol.45, Elsevier SciencePublishers B.V., Amsterdam, 1989
5. Berge, C., Duchet, P.: A generalization of Gilmore’s theorem. In: Fiedler, M. (ed.) RecentAdvances in Graph Theory. Acad. Praha, Prague pp 49–55 (1975)
6. Bondy, A., Duran, G., Lin, M., Szwarcfiter, J.: Self-clique graphs and matrix permuta-tions. Journal of Graph Theory 44, 178–192 (2003)
