An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

On the P4-structure of perfect graphs I. Even decompositions

We present easily verifiable conditions, under which a graph G contains nonempty vertex-disjoint induced subgraphs G₁, G₂ such that G is perfect if and only if G₁ and G₂ are. This decomposition is defined in terms of the induced subgraphs of G that are isomorphic to the chordless path with four vertices.     

On a Class of P5-Free Graphs

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement ? contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P₅-free graphs.     

On a problem of R. Halin concerning infinite graphs II

For every countable, connected graph A containing no one-way infinite path the following is shown: Let G be an arbitrary graph which contains for every positive integer n a system of n disjoint graphs each isomorphic to a subdivision of A. Then G also contains infinitely many disjoint subgraphs each isomorphic to a subdivision of A. In addition, corrections of errors are given that occur unfortunately in the forerunner of the present paper.     

Über eine eigenschaft lokalfiniter,unendlicher bäume

Let A be an arbitrary locally finite, infinite tree and assume that a graph G contains for every positive integer n a system of n disjoint graphs each isomorphic to a subdivision of A. Then G contains infinitely many disjoint subgraphs each isomorphic to a subdivision of A. This sharpens a theorem of Halin [5], who proved the corresponding result for the case that A is a tree in which each vertex has degree not greater than 3.     

Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

Graphoidal bipartite graphs

A graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths inG such that every path in ψ has at least two vertices, every vertex ofG is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω (ψ) denote the intersection graph of ψ. A graph G is said to be graphoidal if there exists a graphH and a graphoidal cover ψof H such that G is isomorphic to Ω(ψ). In this paper we study the properties of graphoidal graphs and obtain a forbidden subgraph characterisation of bipartite graphoidal graphs.     

Some results on the reconstruction problems. p-claw-free,chordal, and p4-reducible graphs

A claw is an induced subgraph isomorphic to K_1,3. The claw-point is the point of degree 3 in a claw. A graph is called p-claw-free when no p-cycle has a claw-point on it. It is proved that for p ≥ 4, p-claw-free graphs containting at least one chordless p-cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw-free graphs. A simple proof of vertex reconstructibility of P₄-reducible graphs is also presented. © 1995 John Wiley & Sons, Inc.     

On brittle graphs

Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P₄ or not an endpoint of any P₄. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n₄) algorithm to recognize HHD-free graphs, and also an O(n₄) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n₄) time.     

Note on the longest paths in {K 1,4, K 1,4 + e}-free graphs

A graph G is {K 1,4,K 1,4 + e}-free if G contains no induced subgraph isomorphic to K 1,4 or K 1,4 + e.In this paper,we show that G has a path which is either hamiltonian or of length at least 2δ(G) + 2 if G is a connected {K 1,4,K 1,4 + e}-free graph on at least 7 vertices.     

Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that the resulting monochromatic subgraphs are isomorphic. We show that any infinite tree of maximum degree Δ with infinitely many vertices of degree at least Δ −1 is bisectable as is any infinite tree of maximum degree Δ ≤ 4. Further, it is proved that every infinite tree T of finite maximum degree contains a finite subset E of its edges so that the graph T − E is bisectable. To measure how “far” a graph G is from being bisectable, we define c(G) to be the smallest number k > 1 so that there is a coloring of the edges of G by k colors with the property that any two monochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 113–127, 2000     

Automorphism groups of graphs with forbidden subgraphs

For a graph Ф letF(Ф) be the class of finite graphs which do not contain an induced subgraph isomorphic to Ф. We show that whenever Ф is not isomorphic to a path on at most 4 vertices or to the complement of such a graph then for every finite groupG there exists a graph ГєF(Ф) such thatG is isomorphic to the automorphism group of Г. For all paths д on at most 4 vertices we determine the class of all automorphism groups of members ofF(д).     

Matchings in 3-vertex-critical graphs: The odd case

A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of v∈V(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K_1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K_1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.     

Opposition graphs are strict quasi-parity graphs

An opposition graph is a graph whose edges can be acyclically oriented in such a way that every chordless path on four vertices has its extreme edges both pointing in or pointing out. A strict quasi-parity graph is a graphG such that every induced subgraphH ofG either is a clique or else contains a pair of vertices which are not endpoints of an odd (number of edges) chordless path ofH. The perfection of opposition graphs and strict quasi-parity graphs was established respectively by Olariu and Meyniel. We show here that opposition graphs are strict quasi-parity graphs.The second author acknowledges the support of the Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Eigenvalues of a graph and its imbeddings

A graph H is imbedded in a graph G if a subset of the vertices of G determines a subgraph isomorphic to H. If λ(G) is the least eigenvalue of G and k_R(H) = lim sup_d→∞ {λ(G)| H imbedded in G; G regular and connected; diam(G) > d; deg(G) > d}, then λ(H) ? 2 ≤ k_R(H) ≤ λ(H) with these bounds being the best possible. Given a graph H, there exist arbitrarily large families of isospectral graphs such that H can be imbedded in each member of the family.     

On geodesic structures of weakly median graphs—II: Compactness, the role of isometric rays

We prove that the vertex set of a K_ℵ0-free weakly median graph G endowed with the weak topology associated with the geodesic convexity on V(G) is compact if and only if G has one of the following equivalent properties: (1) G contains no isometric rays; (2) any chain of interval of G ordered by inclusion is finite; (3) every self-contraction of G fixes a non-empty finite regular weakly median subgraph of G. We study the self-contractions of K_ℵ0-free weakly median graphs which fix no finite set of vertices. We also follow a suggestion of Imrich and Klavzar [Product Graphs, Wiley, New York, 2000] by defining different centers of such a graph G, each of them giving rise to a non-empty finite regular weakly median subgraph of G which is fixed by all automorphisms of G.     

Retract-collapsible graphs and invariant subgraph properties

A (finite or infinite) graph G is retract-collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract-collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract-collapsible. It is shown that the subretract-colapsible graphs are cop-win; and that a ball-Helly graph is subretract-collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract-collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ? S. This last result generalizes a property of bounded ball-Helly graphs. © 1995 John Wiley & Sons, Inc.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.