Berge graphs with chordless cycles of bounded length

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C₃ or to C₄. The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200–208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C₄ by an arbitrary C_p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p ≥ 6, the graphs whose cycles are isomorphic either to C₃ or to one of C_p, C_p+2, …, C_{2p 6} are perfect. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 73–79, 1999     

Graphs with symmetric automorphism group

We investigate the properties of graphs whose automorphism group is the symmetric group. In particular, we characterize graphs on less than 2n points with group S_n, and construct all graphs on n + 3 points with group S_n. Graphs with 2n or more points and group S_n are discussed briefly.     

Properties of almost all graphs and complexes

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u₁, …, u_n, v₁, …, v_n), there exists another vertex w adjacent to each u₁ and not adjacent to any v_i. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.     

Pairs of Chromatically Equivalent Graphs

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. In this paper we give the means to construct infinitely many pairs of chromatically equivalent graphs where one graph in the pair is clique-separable, that is, can be obtained by identifying an r-clique in some graph H ₁ with an r-clique in some graph H ₂, and the other graph is non-clique-separable. There are known methods for finding pairs of chromatically equivalent graphs where both graphs are clique-separable or both graphs are non-clique-separable. Although examples of pairs of chromatically equivalent graphs where only one of the graphs is clique-separable are known, a method for the construction of infinitely many such pairs was not known. Our method constructs such pairs of graphs with odd order n ≥ 9.     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

A note on strong perfectness of graphs

In (strongly) perfect graphs, we define (strongly) canonical colorings; we show that for some classes of graphs, such colorings can be obtained by sequential coloring techniques. Chromatic properties ofP ₄-free graphs based on such coloring techniques are mentioned and extensions to graphs containing no inducedP ₅, orC ₅ are presented. In particular we characterize the class of graphs in which any maximal (or minimal) nodex in the vicinal preorder has the following property: there is either noP ₄ havingx as a midpoint or noP ₄ havingx as an endpoint. For such graphs, according to a result of Chvatal, there is a simple sequential coloring algorithm.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Induced subgraphs and well-quasi-ordering

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤_i, and (2) well-quasi-ordered (WQO) by this relation. The main result shows that the class of cographs (P₄-free graphs) is WQO by ≤_i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P₄-reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤_i are also given.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Forbidding Kuratowski Graphs as Immersions

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K₅ and K_{3, 3}) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch‐width at most 10 by repetitively applying i‐edge‐sums, for . We also use this result to give a structural characterization of graphs that exclude K_{3, 3} as an immersion.     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

A generalization of line graphs: (X,Y)-intersection graphs

Given a pair (X, Y) of fixed graphs X and Y, the (X, Y)-intersection graph of a graph G is a graph whose vertices correspond to distinct induced subgraphs of G that are isomorphic to Y, and where two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X. This generalizes the notion of line graphs, since the line graph of G is precisely the (K₁, K₂)-intersection graph of G. In this paper, we consider the forbidden induced subgraph characterization of (X, Y)-intersection graphs for various (X, Y) pairs; such consideration is motivated by the characterization of line graphs through forbidden induced subgraphs. For this purpose, we restrict our attention to hereditary pairs (a pair (X, Y) is hereditary if every induced subgraph of any (X, Y)-intersection graph is also an (X, Y)-intersection graph), since only for such pairs do (X, Y)-intersection graphs have forbidden induced subgraph characterizations. We show that for hereditary 2-pairs (a pair (X, Y) is a 2-pair if Y contains exactly two induced subgraphs isomorphic to X), the family of line graphs of multigraphs and the family of line graphs of bipartite graphs are the maximum and minimum elements, respectively, of the poset on all families of (X, Y)-intersection graphs ordered by set inclusion. We characterize 2-pairs for which the family of (X, Y)-intersection graphs are exactly the family of line graphs or the family of line graphs of multigraphs. © 1996 John Wiley & Sons, Inc.     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

An edge coloring problem for graph products

The edges of the Cartesian product of graphs G × H are to be colored with the condition that all rectangles, i.e., K₂ × K₂ subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H is 4- or 5-chromatic. © 1996 John Wiley & Sons, Inc.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

On Partitional and Other Related Graphs

The partitional graphs, which are a subclass of the sequential graphs, were recently introduced by Ichishima and Oshima (Math Comput Sci 3:39–45, 2010), and the cartesian product of a partitional graph and K ₂ was shown to be partitional, sequential, harmonious and felicitous. In this paper, we present some necessary conditions for a graph to be partitional. By means of these, we study the partitional properties of certain classes of graphs. In particular, we completely characterize the classes of the graphs B _m and K _m,2 × Q _n that are partitional. We also establish the relationships between partitional graphs and graphs with strong α-valuations as well as strongly felicitous graphs.     

Fixed Points of Automorphisms of Graphs with 1 – Factorizations

We consider sets of fixed points of finite simple undirected connected graphs with 1 – factorizations. The maximum number of fixed points of complete graphs K_2n (n > 2) is n if n ≡ 0 mod 4, n — 1 if n ≡ 3 mod 4 or n ≡ 5 mod 12, n — 2 if n ≡ 2 mod 4, n — 3 if n ≡ 1 mod 4 and n ≢ 5 (mod 12). The maximum number of fixed points of 1 – factorizations of (non – complete) graphs with 2n vertices is less than or equal to n. If n is a prime number, then there are graphs with 2n vertices whose 1 – factorizations have automorphisms with n fixed points. Moreover, a result on the structure of a group of fixed – point – free automorphisms is presented.     

Maximal non- hamilton-laceable graphs

For bipartite graphs the property of being Hamilton laceable is analogous to the property of being Hamilton connected for simple graphs. in this paper it is proven that all of the graphs obtained by deleting fewer than m ? 1 edges from either of the complete bipartite graphs K_{m, m} or K_{m, m+1} are Hamilton laceable. It is also proven that the deletion of m ? 1 edges results in a non-Hamiltonlaceable graph if and only if the graph is either the complement of the star K_1,m?1 in K_{m, m} or K_{m, m+1} or else the complement in K_3,3 of a pair of nonadjacent edges.     

Minimal non-neighborhood-perfect graphs

Neighborhood-perfect graphs form a subclass of the perfect graphs if the Strong Perfect Graph Conjecture of C. Berge is true. However, they are still not shown to be perfect. Here we propose the characterization of neighborhood-perfect graphs by studying minimal non-neighborhood-perfect graphs (MNNPG). After presenting some properties of MNNPGs, we show that the only MNNPGs with neighborhood independence number one are the 3-sun and 3K₂. Also two further classes of neighborhood-perfect graphs are presented: line-graphs of bipartite graphs and a 3K₂-free cographs. © 1996 John Wiley & Sons, Inc.     

On the critical point‐arboricity graphs

In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of k‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph G embedded on a surface S with Euler genus g = 2, 5, 6 or g ≥ 10 is at most with equality holding iff G contains either K_2k?1 or K_2k?4 + C₅ as a subgraph. It is also proved that locally planar graphs have point‐arboricity ≤ 3 and that triangle‐free locally planar‐graphs have point‐arboricity ≤ 2. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 50–61, 2002