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.     

Torsion and Abelianization in Equivariant Cohomology

Let X be a topological space upon which a compact connected Lie group G acts. It is well known that the equivariant cohomology H ^* _G (X; Q) is isomorphic to the subalgebra of Weyl group invariants of the equivariant cohomology H ^* _T (X; Q), where T is a maximal torus of G. This relationship breaks down for coefficient rings k other than Q. Instead, we prove that under a mild condition on k the algebra H ^* _G (X; k) is isomorphic to the subalgebra of H ^* _T (X; k) annihilated by the divided difference operators.     

Topological sums and products in ZF-set theory

In ZF, i.e., Zermelo-Fraenkel set theory without the axiom of choice, the category Top of topological spaces and continuous maps is well-behaved. In particular, Top has sums (=coproducts) and products. However, it may happen that for families (Xi)_i∈I and (Yi)_i∈I with the property that each Xi is homeomorphic to the corresponding Yi neither their sums _⊕i∈IXi and _⊕i∈IYi nor their products _∏i∈IXi and _∏i∈IYi are homeomorphic. It will be shown that the axiom of choice is not only sufficient but also necessary to rectify this defect.     

Exklusive Graphen und Hamiltonche Graphenn-ten Grades II

The graphs considered are finite and undirected, loops do not occur. An induced subgraphI of a graphX is called animitation ofX, if

1. the degreesd _I(v)≡d _X(v) (mod 2) for allv∈V(I)
2. eachu∈V(X)?V(I) is connected with the setv(I) by an even number of edges. If the set of imitations ofX consists only ofX itself, thenX is anexclusive graph. AHamiltonian graph of degree n (abbr.:HG ⁿ) in the sense ofA. Kotzig is ann-regular graph (n>1) with a linear decomposition and with the property, that any two of the linear components together form a Hamiltonian circuit of the graph.

In the first chapter some theorems concerning exclusive graphs and Euler graphs are stated. Chapters 2 deals withHG ^n′ s and bipartite graphs. In chapters 3 a useful concept—theX-graph of anHG ⁿ—is defined; in this paper it is the conceptual connection between exclusive graphs andHG ^n′ s, since a graphG is anHG ⁿ, if all itsX-graphs are exlusive. Furthermore, some theorems onX-graphs are proved. Chapter 4 contains the quintessence of the paper: If we want to construct a newHG ⁿ F from anotherHG ⁿ G, we can consider certain properties of theX-graphs ofG to decide whetherF is also anHG ⁿ.     

Measure transport on Wiener space and the Girsanov theoremTransport de mesure sur l'espace de Wiener et théorème de Girsanov

Let (W,H,μ) be an abstract Wiener space, and assume that ν_i, i=1,2, are two probability measures on $\text{(W,}\text{B}\text{(W))}$ which are absolutely continuous with respect to μ. Assume that the Wasserstein distance between ν₁ and ν₂ is finite. Then there exists a map T=I_W+ξ of W into itself such that ξ:W→H is measurable and 1-cyclically monotone such that the image of ν₁ under T is ν₂. Moreover T is invertible on the support of ν₂. We give also some applications of this result such as the existence of the solutions of the Monge–Ampère equation in infinite dimensions. To cite this article: D. Feyel, A.S. Üstünel, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 1025–1028.     

On super edge-magic decomposable graphs

Let G be any graph and let {H _i } _i??I be a family of graphs such that $E\left( {H_i } \right) \cap E\left( {H_j } \right) = \not 0$ when i ?? j, ?? _i??I E(H _i ) = E(G) and $E\left( {H_i } \right) \ne \not 0$ for all i ?? I. In this paper we introduce the concept of {H _i } _i??I -super edge-magic decomposable graphs and {H _i } _i??I -super edge-magic labelings. We say that G is {H _i } _i??I -super edge-magic decomposable if there is a bijection ??: V(G) ?? {1,2,..., |V(G)|} such that for each i ?? I the subgraph H _i meets the following two requirements: ??(V(H _i )) = {1,2,..., |V(H _i )|} and {??(a) +??(b): ab ?? E(H _i )} is a set of consecutive integers. Such function ?? is called an {H _i } _i??I -super edge-magic labeling of G. We characterize the set of cycles C _n which are {H ₁, H ₂}-super edge-magic decomposable when both, H ₁ and H ₂ are isomorphic to (n/2)K ₂. New lines of research are also suggested.     

Graph minors. I. Excluding a forest

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG₁,…,G_r each of which has at mostk + 1 vertices, by identifying some vertices ofG_i pairwise with some ofG_i+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

Distance in stratified graphs

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G, the X-eccentricity e _X(v) of a vertex v of G is the distance between v and an X-colored vertex furthest from v. The minimum X-eccentricity among the vertices of G is the X-radius rad_X G of G and the maximum X-eccentricity is the X-diameter diam_X G. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_X G = a and diam_X G = b. The number s _X denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with rad_X G t diam_X G, there exist at least one vertex v with e _X(v) = t; while if rad_X G t s _X, then there are at least two such vertices. The X-center C _X(G) is the subgraph induced by those vertices v with e _X(v) = rad_X G and the X-periphery P _X (G) is the subgraph induced by those vertices v with e _X(G) = diam_X G. It is shown that for k-stratified graphs H ₁, H ₂,..., H _k with colors X ₁, X ₂,..., X _k and a positive integer n, there exists a k-stratified graph G such that C X _i(G) H _i (1 ; i ; k1) and for i j. Those k-stratified graphs that are peripheries of k-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

Primitive words,free factors and measure preservation

Let F _k be the free group on k generators. A word w ∈ F _k is called primitive if it belongs to some basis of F _k . We investigate two criteria for primitivity, and consider more generally subgroups of F _k which are free factors. The first criterion is graph-theoretic and uses Stallings core graphs: given subgroups of finite rank H ≤ J ≤ F _k we present a simple procedure to determine whether H is a free factor of J. This yields, in particular, a procedure to determine whether a given element in F _k is primitive. Again let w ∈ F _k and consider the word map w: G × … × G → G (from the direct product of k copies of G to G), where G is an arbitrary finite group. We call w measure preserving if given uniform measure on G × … × G, w induces uniform measure on G (for every finite G). This is the second criterion we investigate: it is not hard to see that primitivity implies measure preservation, and it was conjectured that the two properties are equivalent. Our combinatorial approach to primitivity allows us to make progress on this problem and, in particular, prove the conjecture for k = 2. It was asked whether the primitive elements of F _k form a closed set in the profinite topology of free groups. Our results provide a positive answer for F ₂.     

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.     

Finite 2-groups whose length of chain of nonnormal subgroups is at most 2

Assume that G is a finite non-Dedekind p-group. D. S. Passman introduced the following concept: we say that H₁ < H₂ < ? < H_k is a chain of nonnormal subgroups of G if each H_i ? G and if |H_i : H_i?1| = p for i = 2, 3,…, k. k is called the length of the chain. chn(G) denotes the maximum of the lengths of the chains of nonnormal subgroups of G. In this paper, finite 2-groups G with chn(G) ? 2 are completely classified up to isomorphism.     

Extending compact topologies to compact Hausdorff topologies in ZF

Within the framework of Zermelo-Fraenkel set theory ZF, we investigate the set-theoretical strength of the following statements:

(1)

For every family(Ai)_i∈Iof sets there exists a family(Ti)_i∈Isuch that for everyi∈I(Ai,Ti)is a compactT₂space.

(2)

For every family(Ai)_i∈Iof sets there exists a family(Ti)_i∈Isuch that for everyi∈I(Ai,Ti)is a compact, scattered, T₂space.

(3)

For every set X, every compactR₁topology (itsT₀-reflection isT₂) on X can be enlarged to a compactT₂topology.

We show:

(a)

(1) implies every infinite set can be split into two infinite sets.

(b)

(2) iff AC.

(c)

(3) and “there exists a free ultrafilter” iff AC.

We also show that if the topology of certain compact T₁ spaces can be enlarged to a compact T₂ topology then (1) holds true. But in general, compact T₁ topologies do not extend to compact T₂ ones.     

<Emphasis Type="Bold">K</Emphasis><Subscript>0</Subscript> of Semiartinian Von Neumann Regular Rings. Direct Finiteness Versus Unit-Regularity

If R is a regular and semiartinian ring, it is proved that the following conditions are equivalent: (1) R is unit-regular, (2) every factor ring of R is directly finite, (3) the abelian group K _O(R) is free and admits a basis which is in a canonical one to one correspondence with a set of representatives of simple right R-modules. For the class of semiartinian and unit-regular rings the canonical partial order of K _O(R) is investigated. Starting from any partially ordered set I, a special dimension group G(I) is built and a large class of semiartinian and unit-regular rings is shown to have the corresponding K _O(R) order isomorphic to G(P r i m _R ), where P r i m _R is the primitive spectrum of R. Conversely, if I is an artinian partially ordered set having a finite cofinal subset, it is proved that the dimension group G(I) is realizable as K _O(R) for a suitable semiartinian and unit-regular ring R.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

Étale covers of affine spaces in positive characteristicRevêtements étales des espaces affines en caractéristique positive

We prove that every projective, geometrically reduced scheme of dimension n over an infinite field k of positive characteristic admits a finite morphism over some finite radicial extension k′ of k to projective n-space, étale away from the hyperplane H at infinity, which maps a chosen Weil divisor into H and a chosen smooth geometric point of X not on the divisor to some point not in H. To cite this article: K.S. Kedlaya, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 921–926.     

Graphs admitting transitive commutative group actions

Let X be a compact metric space, and Homeo(X) be the group consisting of all homeomorphisms from X to X. A subgroup H of Homeo(X) is said to be transitive if there exists a point x∈X such that {k(x):k∈H} is dense in X. In this paper we show that, if X=G is a connected graph, then the following five conditions are equivalent: (1) Homeo(G) has a transitive commutative subgroup; (2) G admits a transitive Z²-action; (3) G admits an edge-transitive commutative group action; (4) G admits an edge-transitive Z²-action; (5) G is a circle, or a k-fold loop with k?2, or a k-fold polygon with k?2, or a k-fold complete bigraph with k?1. As a corollary of this result, we show that a finite connected simple graph whose automorphism group contains an edge-transitive commutative subgroup is either a cycle or a complete bigraph.     

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

Results on the Grundy chromatic number of graphs

Given a graph G, by a Grundy k-coloring of G we mean any proper k-vertex coloring of G such that for each two colors i and j, i<j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ(G) and called Grundy (chromatic) number of G. We first discuss the fixed-parameter complexity of determining Γ(G)?k, for any fixed integer k and show that it is a polynomial time problem. But in general, Grundy number is an NP-complete problem. We show that it is NP-complete even for the complement of bipartite graphs and describe the Grundy number of these graphs in terms of the minimum edge dominating number of their complements. Next we obtain some additive Nordhaus-Gaddum-type inequalities concerning Γ(G) and Γ(G^c), for a few family of graphs. We introduce well-colored graphs, which are graphs G for which applying every greedy coloring results in a coloring of G with χ(G) colors. Equivalently G is well colored if Γ(G)=χ(G). We prove that the recognition problem of well-colored graphs is a coNP-complete problem.