Highly edge-connected regular graphs without large factorizable subgraphs

We construct highly edge-connected $r$-regular graphs of even order which do not contain $r?2$ pairwise disjoint perfect matchings. When $r$ is a multiple of 4, the result solves a problem of Thomassen [4].     

On the structure of unbreakable graphs

A nonempty set C of vertices is a star-cutset in a graph G if G – C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Va?ek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star-cutset. A path with four vertices and three edges will be termed a P₄. An edge uv of a graph G is called a wing, if for some vertices x, y, {u,v,x,y} induces a P₄ in G. We define recursively the coercion class C_uv of a wing uv as follows:

• 1 uv ∈ C_uv, and
• 1 if xy ∈ C_uv and xy, x'y' are wings of a same P₄ in G, then x'y' ∈ C_uv.

The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

On the combinatorial structure of Rauzy graphs

Let S _m ⁰ be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S _m ⁰ . For a permutation ?? ?? S _m ⁰ , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S _m ⁰ is a tree composed of cycles, then the set R(??) contains a permutation ?? ₀: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? ₀) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.     

On the structure of infinite vertex-transitive graphs

A characterization of all vertex-transitive graphs Γ of connectivity l is given in terms of the lobe structure of Γ. Among these, all graphs are determined whose automorphism groups act primitively (respectively, regularly) on the vertex set.