Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

A characterization of graphs without long induced paths

In a connected graph define the k-center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d-dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d. Call a graph P_t-free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P_2k-1-free (P_2k-free) if and only if each of its connected induced subgraphs H satisfy the following property: The k-center of H (k - 1)-dominates ((k - 2)-dominates) H. Moreover, we show that the subgraph induced by the (t - 3)-center in any P_t-free connected graph is again connected and has diameter at most t - 3.     

RandomlyH-coverable graphs

A graph israndomly matchable if every matching of the graph is contained in a perfect matching. We generalize this notion and say that a graphG israndomly H-coverable if every set of independent subgraphs, each isomorphic toH, that does not cover the vertices ofG can be extended to a larger set of independent copies ofH. Various problems are considered for the situation whereH is a path. In particular, we characterize the graphs that are randomlyP ₃ -coverable.     

On large sets of Pk‐decompositions

Let G = (V(G),E(G)) be a graph. A (ν, G, λ)‐GD is a partition of all the edges of λK_ν into subgraphs (G‐blocks), each of which is isomorphic to G. The (ν, G, λ)‐GD is named as graph design for G or G‐decomposition. The large set of (ν, G, λ)‐GD is denoted by (ν, G, λ)‐LGD. In this paper, we obtain a general result by using the finite fields, that is, if q ≥ k ≥ 2 is an odd prime power, then there exists a (q,P_k, k ? 1)‐LGD. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.     

Path-Bicolorable Graphs

In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k ≥ 2, a graph G = (V, E) is P _k -bicolorable if its vertex set V can be partitioned into two subsets (i.e., color classes) V ₁ and V ₂ such that for every induced P _k (a path with exactly k − 1 edges and k vertices) in G, the two colors alternate along the P _k , i.e., no two consecutive vertices of the P _k belong to the same color class V _i , i = 1, 2. Obviously, a graph is bipartite if and only if it is P ₂-bicolorable. We give a structural characterization of P ₃-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of P ₄-bicolorable graphs in terms of forbidden subgraphs.     

Some remarks on (k−1)-critical subgraphs ofk-critical graphs

A graphG is said to bek-critical if it has chromatic numberk, but every proper subgraph ofG has a (k–1)-coloring. Gallai asked whether every largek-critical graph contains many (k–1)-critical subgraphs. We provide some information concerning this question and some related questions.     

On Extensions of a Conjecture of Gallai

A graphGisk-criticalif it has chromatic numberkbut every proper subgraph ofGhas a (k−1)-coloring. We prove the following result. IfGis ak-critical graph of ordern>k3, thenGcontains fewer thann−3k/5+2 complete subgraphs of orderk−1.     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

The dynamics of the line and path graph operators

For any integerk e 1 thek- path graph P_k (G) of a graph G has all length-k subpaths ofG as vertices, and two such vertices are adjacent whenever their union (as subgraphs ofG) forms a path or cycle withk + 1 edges. Fork = 1 we get the well-known line graphP ₁ (G) =L(G). Iteratedk-path graphs P^t _k(G) are defined as usual by P^t _k (G) := P_k(P ^t?1 _k(G)) ift < 1, and by P¹ _k(G): = P_k(G). A graph G isP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -periodic. A graph has infiniteP _k -depth if for any positive integert there is a graphH such that P^t _k(H) ?G. In this paperP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -periodic graphs,P _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -convergent graphs, and graphs with infiniteP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -depth are characterized inside some subclasses of the class of locally finite graphs fork = 1, 2.     

On coloring graphs with locally small chromatic number

In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc _k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc _k n ^1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc _k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.     

ON UNIQUELY -G k-COLOURABLE GRAPHS

Abstract

Given graphs F and G and a nonnegative integer k, a map Π: V(F) → + {lm …, k} is a -G k-colouring of F if the subgraphs induced by each colour class do not contain G as an induced subgraph; F is -G k-chromatic if F has a -G k-colouring but no -G (k—1)-colouring. Further, we say F is uniquely -G k-colourable if and only if F is -G k-chromatic and, up to a permutation of colours, it has only one -G k-colouring. Such notions are extensions of the well known corresponding definitions from chromatic theory. In a previous paper (J. Graph. Th. 11 (1987), 87–99), the authors conjectured that for all graphs G of order at least two and all nonnegative integers k there exist uniquely -G k-colourable graphs. We show here that the conjecture holds whenever G or its complement is 2-connected.     

Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs

The Loebl–Komlós–Sós conjecture states that for any integers k and n, if a graph G on n vertices has at least n/2 vertices of degree at least k, then G contains as subgraphs all trees on k+1 vertices. We prove this conjecture in the case when k is linear in n, and n is sufficiently large.     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

On galois descent for Hochschild and cyclic homology

LetG be a finite group acting by automorphisms on an algebraS over some commutative ringk. We show that if the action ofG restricted to the center ofS is Galois in the sense of [C-H-R], thenHH _*(S ^G)≊HH _* (S) ^G. An analogous result holds for cyclic homology, provided the order ofG is invertible ink. The author was supported in part by a grant from the NSF.     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

Permutability of minimal subgroups and<Emphasis Type="Italic">p</Emphasis>-nilpotency of finite groups

In this paper it is proved that ifp is a prime dividing the order of a groupG with (|G|,p − 1) = 1 andP a Sylowp-subgroup ofG, thenG isp-nilpotent if every subgroup ofP ∩G ^N of orderp is permutable inN _G (P) and whenp = 2 either every cyclic subgroup ofP ∩G ^N of order 4 is permutable inN _G (P) orP is quaternion-free. Some applications of this result are given. The research of the first author is supported by a grant of Shanxi University and a research grant of Shanxi Province, PR China. The research of the second author is partially supported by a UGC(HK) grant #2160126 (1999/2000).     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

Cleavages of graphs: the spectral radius

A cleavage of a finite graph G is a morphism f : H → G of graphs such that if P is the m × n characteristic matrix defined as P _ik = 1 if i ∈ f ^?1(k), otherwise = 0, then A(H)P ≤ PA(G), where A(G) and A(H) are the adjacency matrices of G and H, respectively. This concept generalizes induced subgraphs, quotients of graphs, Galois covers, path-tree graphs and others. We show that for spectral radii we have the inequality ρ(H) ≤ ρ(G). Equality holds only in case f : H → G is an equivariant quotient and H has isoperimetric constant i(H) = 0.