Chordal graphs and join spaces

A join space is an abstract model for partially ordered linear, spherical and projective geometries. A characterization for chordal graphs which are join spaces is given: a chordal graph is a join space if and only if it does not contain one of the two forbidden graphs as an induced subgraph.     

Chordal bipartite graphs and crowns

We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free.     

Chordal graphs,interval graphs,and wqo

Let precedes, equal to be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by precedes, equal to. On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by precedes, equal to. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 105–114, 1998     

Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

Subspace intersection graphs

Given a set R of affine subspaces in R^d of dimension e, its intersection graph G has a vertex for each subspace, and two vertices are adjacent in G if and only if their corresponding subspaces intersect. For each pair of positive integers d and e we obtain the class of (d,e)-subspace intersection graphs. We classify the classes of (d,e)-subspace intersection graphs by containment, for e=1 or e=d−1 or d≤4.     

Modular intersection graphs

A graphG = (V, E) is a modular intersection graph on a finite setU if there is a family of subsetsS = {S _xx V} ofU and positive integerst < m such thatxy is an edge ofG if and only if |S _x S_y| (modm) t. Modular representations of various classes of graphs and studied as well as some related parameters.Research supported by Grant N00014-89-J-1643 from the Office of Naval Research.     

Perfect matchings in random intersection graphs

Let W ₁,??,W _n be independent random subsets of [m]={1,??,m}. Assuming that each W _i is uniformly distributed in the class of d-subsets of?[m] we study the uniform random intersection graph G _s (n,m,d) on the vertex set {W ₁,??W _n }, defined by the adjacency relation: W _i ??W _j whenever |W _i ??W _j |?Rs. For even?n we show that as n,m???? the edge density threshold for the property that G _s (n,m,d) contains a perfect matching is asymptotically the same as that for G _s (n,m,d) being connected.     

From moment graphs to intersection cohomology

We describe a method of computing equivariant and ordinary intersection cohomology of certain varieties with actions of algebraic tori, in terms of structure of the zero- and one-dimensional orbits. The class of varieties to which our formula applies includes Schubert varieties in flag varieties and affine flag varieties. We also prove a monotonicity result on local intersection cohomology stalks. Received: 9 November 2000 / Published online: 24 September 2001     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

General results on tolerance intersection graphs

In this paper, general results are presented that are related to ?-tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ?-tolerance intersection graphs for all ?, yet for “nice” ?, almost no graphs are ?-tolerance interval graphs. Additional results about representation of trees are given.     

Connectivity of intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary.     

Simultaneous intersection representation of pairs of graphs

We characterize the pairs (G₁, G₂) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G₁ is the intersection graph of the subsets and G₂ is the intersection graph of their complements. We also consider several special cases and explore bounds on the size of the universal set. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 171–190, 1999     

On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs.     

Triple intersection numbers for the Paley graphs

We give a tight bound for the triple intersection numbers of Paley graphs. In particular, we show that any three vertices have a common neighbor in Paley graphs of order larger than 25.