Search

We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.

We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. (A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k−1)-colorable). Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical (P8,C4)-free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical H-free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 52 4-critical planar P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least (8n−2m−2)/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a clique of order either 4 or 5. This improves the previous lower bound 2n22m+n of Alon–Kahn–Seymour for m≤5n/2, and implies that such a graph has an induced forest of order at least n/2 for m

Given a graph F, a graph G is uniquely F-saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely -saturated graphs. We prove the following: (1) a graph is uniquely C5-saturated if and only if it is a friendship graph. (2) There are no uniquely C6-saturated graphs or uniquely C7-saturated graphs. (3) For , there are only finitely many uniquely -saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k-friendship graphs (as defined by Kotzig) for .

Let H be a given graph. A graph G is said to be H-free if G contains no induced copies of H. For a class of graphs, the graph G is -free if G is H-free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2-connected -free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non-hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n0 such that every 2-connected -free graph of order at least n0 is hamiltonian.

We study the topic of “extremal” planar graphs, defining to be the maximum number of edges possible in a planar graph on n vertices that does not contain a given graph H as a subgraph. In particular, we examine the case when H is a small cycle, obtaining for all and for all , and showing that both of these bounds are tight.

DeVos and Mohar proved a rough structure theorem about small separations in vertex-transitive graphs [5, 6]. By using a new version of Varopolous isoperimetric inequality, we give an improvement of their lower bound on the expansion in the case of infinite vertex-transitive graphs. Specifically, let be a locally finite connected graph such that there is a group G acting discretely and transitively on X. If is nonempty and finite such that is connected and , then X has a ring-like structure. Moreover, we give a similar asymptotic result under the assumption that X is an infinite vertex transitive graph. In the setting of finite groups, we use local expansion to show the existence of a nontrivial cyclic subgroup with an effectively bounded index. Finally, we prove that for any there is a graph T and a subgraph A of T, such that .

Motivated by a recent extension of the zero-one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph Gn,p. We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two-component graphs in Gn,p for all q, and we give infinite families of many-component graphs with a uniform asymptotic distribution for all q. We also prove a negative result that no recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.

Determining the maximum number of edges in an n-vertex C4-free graph is a well-studied problem that dates back to a paper of Erdős from 1938. One of the most important families of C4-free graphs are the Erdős-Renyi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose-Chowla Sidon set is isomorphic to a large induced subgraph of the Erdős-Renyi orthogonal polarity graph. Using this isomorphism, we prove that the Petersen graph is a subgraph of every sufficiently large Erdős-Renyi orthogonal polarity graph.

A bi-subdivision of a graph J is a graph H obtained from J by subdividing each of its edges by inserting an even number of vertices. A matching covered subgraph H of a matching covered graph G is conformal if has a perfect matching. Using the theory of ear decompositions, Lovasz (Combinatorica, 3 (1983), 105–117) showed that every nonbipartite matching covered graph has a conformal subgraph which is either a bi-subdivision of K4 or of . (The graph is the triangular prism.) A matching covered graph is K4-based if it contains a bi-subdivision of K4 as a conformal subgraph; otherwise it is K4-free. -based and -free graphs are analogously defined. The result of Lovasz quoted above implies that any nonbipartite matching covered graph is either K4-based or -based (or both). The problem of deciding which matching covered graphs are K4-based and which are -based is, in general, unsolved. In this paper, we present a solution to this classification problem in the special case of planar graphs. In Section 2, we show that a matching covered graph is K4-free (-free) if and only if each of its bricks is K4-free (-free). In Section 5, we show that a planar brick is K4-free if and only if it has precisely two odd faces. In Section 6, we determine the list of all -free planar bricks; apart from one exception, it consists of two infinite families of bricks. The principal tool we use for proving our results is the brick generation procedure established by Norine and Thomas (J Combin Theory Ser B, 97 (2007), 769–817).

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck-the collection of its vertex-deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let be the number of distinct mutually nonisomorphic graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n-vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all n-vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies .

Given an edge coloring of a graph with a set of m colors, we say that the graph is exactly m-colored if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number m>2 and for all sufficiently large k, there is a k-coloring of the complete graph on N such that no complete infinite subgraph is exactly m-colored. In the light of this result, we consider the question of how close we can come to finding an exactly m-colored complete infinite subgraph. We show that for a natural number m and any finite coloring of the edges of the complete graph on N with m or more colors, there is an exactly mi¾?-colored complete infinite subgraph for some mi¾? satisfying |m-mi¾?|i¾?m/2+1/2; this is best possible up to the additive constant. We also obtain analogous results for this problem in the setting of r-uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalizations of this conjecture to r-uniform hypergraphs.

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree dF(x) of each vertex x in F is odd, and each tree of F is an induced subgraph of G. We provide a short linear-algebraic proof of the following theorem of A. D. Scott (Graphs Combin 17 (2001), 539–553): A connected graph G contains a perfect forest if and only if G has an even number of vertices.

A graph is K2, 3-saturated if it has no subgraph isomorphic to K2, 3, but does contain a K2, 3 after the addition of any new edge. We prove that the minimum number of edges in a K2, 3-saturated graph on vertices is sat.

Let be the class of all graphs with no induced four-edge path or four-edge antipath. Hayward and Nastos [6] conjectured that every prime graph in not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this article, we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour [1] we give a short proof of Fouquet's result [3] on the structure of the subclass of bull-free graphs contained in .

In this article, we study so-called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted -packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum -packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum -packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2-edge star and S contains the center of the star only. We prove a min–max theorem for -packings in this case.

We consider the problem of determining the maximum induced density of a graph H in any graph on n vertices. The limit of this density as n tends to infinity is called the inducibility of H. The exact value of this quantity is known only for a handful of small graphs and a specific set of complete multipartite graphs. Answering questions of Brown–Sidorenko and Exoo, we determine the inducibility of K1, 1, 2 and the paw graph. The proof is obtained using semidefinite programming techniques based on a modern language of extremal graph theory, which we describe in full detail in an accessible setting.

According to the classical Erd˝´ theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most O(klogk) vertices that hits all its cycles. Robertson and Seymour [Graph minors. V. Excluding a planar graph. J. Comb. Theory Series B, 41:92‐114, 1986] generalized this result in the best possible way. More specifically, they showed that ifH is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex-disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph inH or there exists a set S of at most f(k) vertices such that Gn S contains no subgraph isomorphic to any graph inH. However the function f is exponential. In this note, we prove that this function becomes quadratic whenH consists all graphs that can be contracted to a fixed planar graph c. For a fixed c, c is the graph with two vertices and c 1 parallel edges. Observe that for c = 2 this corresponds to the classical Erd˝´ osa theorem.

An -factor of a graph G is defined to be a spanning subgraph F of G such that each vertex has a degree belonging to the set in F, where . In this article, we investigate -factors of graphs by using Lovasz's structural descriptions to the degree prescribed subgraph problem. We find some sufficient conditions for the existence of an -factor of a graph. In particular, we make progress on the characterization problem for a special family of graphs proposed by Cui and Kano in 1988.

We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham, and Wilson [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G, the main result of [3] which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H.

A graph G is called -vertex stable if G contains a subgraph isomorphic to H even after removing any k of its vertices. By stab we denote the minimum size among the sizes of all -vertex stable graphs. Given an integer , we prove that, apart of some small values of k, stab. This confirms in the affirmative the conjecture of Dudek et al. [Discuss Math Graph Theory 28(1) (2008), 137–149]. Furthermore, we characterize the extremal graphs.

The bull is a graph consisting of a triangle and two vertex-disjoint pendant edges. A graph is called bull-free if no induced subgraph of it is a bull. A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the size of the largest complete subgraph of H. This article describes the structure of all bull-free perfect graphs.

Let X, Y be connected graphs. A graph G is -free if G contains a copy of neither X nor Y as an induced subgraph. Pairs of connected graphs such that every 3-connected -free graph is Hamilton connected have been investigated most recently in (Guantao Chen and Ronald J. Gould, Bull. Inst. Combin. Appl., 29 (2000), 25–32.) [8] and (H. Broersma, R. J. Faudree, A. Huck, H. Trommel, and H. J. Veldman, J. Graph Theory, 40(2) (2002), 104–119.) [5]. This paper improves those results. Specifically, it is shown that every 3-connected -free graph is Hamilton connected for and or N1, 2, 2 and the proof of this result uses a new closure technique developed by the third and fourth authors. A discussion of restrictions on the nature of the graph Y is also included.

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.

For a family of graphs, a graph G is -saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an -saturated graph of order n is denoted *. A subdivision of a graph H, or an H-subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H-subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that *. For we show that will suffice, and that this can be improved slightly depending on the value of *. We also give an upper bound on for all t and show that *. This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge-maximal graphs without a K5-minor have at least edges. © 2012 Wiley Periodicals, Inc. (Research supported in part by UCD GK12 project, NSF award no. 0742434. The author acknowledges support of the National Science Foundation through a fellowship funded by the grant “EMSW21-MCTP: Research Experience for Graduate Students” (NSF DMS 08-38434).)

A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex-transitive non-Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc. (Contract grant sponsor: National Natural Science Foundation of China; Contract grant number: 10901015; Contract grant sponsor: Fundamental Research Funds for the Central Universities; Contract grant numbers: 2011JBM127 and 2011JBZ012; Contract grant sponsor: Science and Technology Foundation of Beijing Jiaotong University; Contract grant number: 2008RC037.)

The topological approach to the study of infinite graphs of Diestel and KUhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4-edge-connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6-edge-connected graph with a finite number of ends, each of which is thin, is hamiltonian. © 2012 Wiley Periodicals, Inc.

It is shown that every sufficiently large almost-5-connected non-planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost-5-connected, by which we mean that they are 4-connected and all 4-separations contain a “small” side. As a corollary, every sufficiently large almost-5-connected non-planar graph contains both a K3, 4-minor and a -minor. The connectivity condition cannot be reduced to 4-connectivity, as there are known infinite families of 4-connected non-planar graphs that do not contain a K3, 4-minor. Similarly, there are known infinite families of 4-connected non-planar graphs that do not contain a -minor. © 2012 Wiley Periodicals, Inc. (Contract grant sponsors: C8C Foundation; Inamori Foundation; Kayamori Foundation (K. K.).)

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2-variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory © 2012 Wiley Periodicals, Inc.

A new characterization of generalized line graphs, analogous to that of line graphs found by Van Rooij and Wilf [Acta Math Acad Sci Hungar 16 (1965), 263–269] is obtained. By a cycle of implications, we settle the equivalence of the definition of generalized line graph given by Hoffman [Combinatorial Structures and their Applications, Gordon and Breach, NY, 1970, pp. 173–176], its description by vectorial representation [P. J. Cameron et al., Algebra 43 (1976), 305–327], the current characterization and the one involving minimal nongeneralized line graphs [D. Cvetkovic et al., J Graph Theory 5(4) (1981), 385–399; D. Cvetkovic et al., Des Codes Cryptogr 34(2–3) (2005), 229–240; S. B. Rao et al., Combinatorics and Graph Theory, Lecture Notes 885, Springer, Berlin, 1981, pp. 459–472; G. R. Vijayakumar, J Combin Inform System Sci 9(3) (1984), 182–192]. This process includes a short method of finding the aforementioned graphs, analogous to the method found by Beineke [J Combin Theory 9 (1970), 129–135] to obtain all minimal nonline graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 27-33, 2011 © 2011 Wiley Periodicals, Inc.

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρn distinct (4, 1)-colorings, where c is constant and ρ≈1.466 satisfies ρ3 = ρ2 + 1. On the other hand for any e>0, we give examples of planar graphs with fewer than c(ϕ + e)n distinct (4, 1)-colorings, where c is constant and **image**. Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2n distinct (γ(S), 1)-colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129-136, 2011 © 2011 Wiley Periodicals, Inc.

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor-phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65:253–262, 2010 © 2010 Wiley Periodicals, Inc.

Let ℋ and 𝒢 be graph classes. We say that ℋ has the Erdős–Posa property for 𝒢 if for any graph G ∈𝒢, the minimum vertex covering of all ℋ-subgraphs of G is bounded by a function f of the maximum packing of ℋ-subgraphs in G (by ℋ-subgraph of G we mean any subgraph of G that belongs to ℋ). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ℋ is the class of all graphs that can be contracted to a fixed planar graph H, then ℋ has the Erdős–Posa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when 𝒢 is any non-trivial minor-closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235-240, 2011 © 2011 Wiley Periodicals, Inc.

We show that every 3-connected claw-free graph which contains no induced copy of P11 is hamiltonian. Since there exist non-hamiltonian 3-connected claw-free graphs without induced copies of P12 this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004

Let ϕ be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ϕ-tolerance graph if each vertex υ ∈ V can be assigned a closed interval Iυ and a positive tolerance tυ so that xy ∈ E ⇔ | Ix ∩ Iy|≥ ϕ (tx,ty). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K2,k) is a ϕ-tolerance graph for all Archimedean functions ϕ. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ϕG-tolerance graph for some Archimedean polynomial ϕG. Finally, we prove that there is a „universal” Archimedean function ϕ * such that every graph G is a ϕ*-tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: “given a graph G which is a parity graph, is G also well-covered graph?” is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (Quaestiones Math. 16 (1993)) and Finbow, Hartnell, and Whitehead (Discrete Math. 125 (1994)). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 85–94, 1997

We find necessary and sufficient conditions for a graph G to be the core of a graph containing an overfull subgraph of the same maximum degree. Thus we enlarge the list of graphs known to be cores of class II graphs. © 1995 John Wiley & Sons, Inc.

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.

A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1 -well- covered graph was introduced by Staples in her 1975 dissertation: a well-covered -graph G is 1 -well-covered if and only if G-v is also well-covered for every point v in G. Except for K.) and C5, every 1- well-covered graph contains triangles or 4-cycles. Thus, triangle-free 1 -well- covered graphs necessarily have girth 4. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family.

In a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge set E(G) of a connected graph G to decompose G into a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,” Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,” European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,” Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from finite to infinite graphs.

No countable Cn-free graph contains every countable Cn-free graph as a subgraph, for n ≧ 4. For n = 4, this was proved earlier by J. Pach.

A graph G is collapsible if for every even subset R ⊆ V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. A graph is reduced if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defined and studied in [4]. In this article, we obtain a lower bound on the size of a maximum matching in a reduced graph. As an application, we verify and strengthen the Benhocine, Clark, Kohler, and Veldman conjecture [1], when restricted to 3-edge-connected graphs, by showing that for n large, a simple graph G with order n and with k′(G) ≥ 3 is collapsible or is contractible to the Petersen graph if for each edge uv ∈ E(G), d(u) + d(v) ≥ (n/5) − 2. We also characterize the extremal graphs. © 1993 John Wiley & Sons, Inc.

A graph is supereulerian if it has a spanning eulerian subgraph. There is a rduction method to determine whether a graph is supereulerian, and it can also be applied to study other concepts, e.g., hamiltonian line graphs, a certain type of double cycle cover, and the total interval number of a graph. We outline the research on supereulerian graphs, the reduction method, and its applications.

New characterizations of triangulated and cotriangulated graphs are pre- sented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability func- tion has all its coefficients equal to 0, +1 or -1.

We call a graph (m, k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)-colorable. We include an elementary proof (not assuming the truth of the four-color theorem) that every planar graph is (4, 1)-colorable. Finally, we prove that, for each compact surface S, there is an integer k = k(S) such that every graph in S can be (4, k)-colored; we conjecture that 4 can be replaced by 3 in this statement.