Disjoint clique cutsets in graphs without long holes

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

Associativity of crossed products by partial actions, enveloping actions and partial representations

Given a partial action of a group on an associative algebra , we consider the crossed product . Using the algebras of multipliers, we generalize a result of Exel (1997) on the associativity of obtained in the context of -algebras. In particular, we prove that is associative, provided that is semiprime. We also give a criterion for the existence of a global extension of a given partial action on an algebra, and use crossed products to study relations between partial actions of groups on algebras and partial representations. As an application we endow partial group algebras with a crossed product structure.

     

Decomposing large graphs with small graphs of high density

It is shown that for every positive integer h, and for every ϵ > 0, there are graphs H = )V_H E_H) with at least h vertices and with density at least 0.5 - ϵ with the following property: If G = (V_G, E_G) is any graph with minimum degree at least (1 + o(1)) and |E_H| divides |E_G|, then G has an H-decomposition. This result extends the results of [R. M. Wilson, Cong Numer XV (1925), 647–659] [T. Gustavsson, Ph.D. Thesis, U. Stockholm, 1991] [R. Yuster, Random Struc Algorith, 12 (1998), 237–251]. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 27–40, 1999     

Dyadic representations of graphs

A graph $G$ is dyadic provided it has a representation $v\to S_v$ from vertices $v$ of $G$ to subtrees $S_v$ of a host tree $T$ with maximum degree 3 such that $\left(i\right)$$v$ and $w$ are adjacent in $G$ if and only if $S_v$ and $S_w$ share at least three nodes and $\left(ii\right)$ each edge of $T$ is used by exactly two representing subtrees. We show that a connected graph is dyadic if and only if it can be constructed from edges and cycles by gluing vertices to vertices and edges to edges.     

Extending partial isomorphisms of graphs

Theorem Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism ₁,..., _n and ₁ ofR (in the sense of Baire category), (R,₁,..., _n ), (R,₁,..., _n ). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378.     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

Extending partial isometries of antipodal graphs

We prove EPPA (extension property for partial automorphisms) for all antipodal classes from Cherlin’s list of metrically homogeneous graphs, thereby answering a question of Aranda et al. This paper should be seen as the first application of a new general method for proving EPPA which can bypass the lack of automorphism-preserving completions. It is done by combining the recent strengthening of the Herwig–Lascar theorem by Hubička, Nešetřil and the author with the ideas of the proof of EPPA for two-graphs by Evans et al.     

Partial characterizations of circle graphs

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P₄-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.     

Locally 2‐arc transitive graphs,homogeneous factorizations,and partial linear spaces

We establish natural bijections between three different classes of combinatorial objects; namely certain families of locally 2‐arc transitive graphs, partial linear spaces, and homogeneous factorizations of arc‐transitive graphs. Moreover, the bijections intertwine the actions of the relevant automorphism groups. Thus constructions in any of these areas provide examples for the others. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 139–148, 2006     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

Weighted parameters in graphs

We use the modular decomposition to give O(n(m + n) algorithms for finding a maximum weighted clique (respectively stable set) and an approximate weighted colouring (respectively partition into cliques) in a graph. As a by-product, we obtain an O(m + n) algorithm for finding a minimum weighted transversal of the C₅ in a graph.     

Construction of some countable 1-arc-transitive bipartite graphs

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.     

Approximate Hamilton decompositions of random graphs

We show that if pn ? log n the binomial random graph G_n,p has an approximate Hamilton decomposition. More precisely, we show that in this range G_n,p contains a set of edge‐disjoint Hamilton cycles covering almost all of its edges. This is best possible in the sense that the condition that pn ? log n is necessary. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A note on the recognition of bisplit graphs

We show that bisplit graphs can be recognized in O(n²) time. The previous best bound of O(mn) for the problem appeared in a recently published article [A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, Discrete Math. 299 (2005) 11-32] in this journal.