Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Strong chromatic index of subset graphs

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S_m(k, l) is a bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, we demonstrate that the conjecture is also valid for a more general family of bipartite graphs. © 1997 John Wiley & Sons, Inc.     

Monotone heteroclinic solutions to non-autonomous equations via phase plane analysis

We study the existence of at least one increasing heteroclinic solution to a scalar equation of the kind ẍ = a(t)V′(x), where V is a non-negative double well potential, and a(t) is a positive, measurable coefficient. We first provide with a complete answer in the definitively autonomous case, when a(t) takes a constant value l outside a bounded interval. Then we consider the case in which a(t) is definitively monotone, converges from above, as t → ±∞, to two positive limits l _* and l ^*, and never goes below min(l _*, l ^*). Furthermore, the convergence to max(l _*, l ^*) is supposed to be not too fast (slower than a suitable exponential term).     

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

On the stability number of AH-free graphs

We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graph G a new graph G^l that has fewer nodes and has the property that α(G^l) = α(G) ? 1. This new class of graphs is different from the known classes for which the stability number can be computed in polynomial time. © 1993 John Wiley & Sons, Inc.     

The Erdős–Pósa Property For Long Circuits

We show that, for every l, the family of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk²).     

The f-factor Problem for Graphs and the Hereditary Property

If P is a hereditary property then we show that, for the existence of a perfect f-factor, P is a sufficient condition for countable graphs and yields a sufficient condition for graphs of size ℵ₁. Further we give two examples of a hereditary property which is even necessary for the existence of a perfect f-factor. We also discuss the ℵ₂-case.This paper was supported by the Volkswagen Stiftung     

The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

A decomposition property of polyhedra

A polyhedronP = {x∈ ℝ ₊ ⁿ ∣d ⩽Ax ⩽e} is said to have the real decomposition property (RDP) if for any positiveT and any realx∈TP, there are positive coefficients λ₁,…, λ _r and integers ¹, …,s ^r ∈P withx = λ _l s ^l + … + λ _r s ^r andT=λ _l + ⋯ + λ _r . We give a constructive proof that this property holds for a polyhedronP iffP is integral. This construction is used to show that some classes of polyhedra have an integral decomposition property. Furthemore, the RDP provides a generalization of the theorem of Birkhoff-von Neumann. So RDP may be used in some scheduling problems on parallel processors with preemptions.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

Edge-disjoint paths and cycles in n-edge-connected graphs

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n-edge-connected graph, s₁, ?,s_k, t₁, ?,t_k are vertices of G, and f₁, ?,f_l, g₁, ?,g_l, are pairwise distinct edges of G, then for each i = 1, ?, k there exists a path P_i in G, connecting s_i and t_i and for each i = 1, ?,l there exists a cycle C_i in G containing f_i and g_i such that P₁, ?,P_k, C₁, ?, C_l are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).     

Probabilities of Sentences about Very Sparse Random Graphs

We consider random graphs with edge probability βn^?α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit.     

Pitt's theorem for the Lorentz and Orlicz sequence spaces

LetL(X, Y) be the Banach space of all continuous linear operators fromX toY, and letK(X, Y) be the subspace of compact operators. Some versions of the classical Pitt theorem (ifp>q, thenK(l _p, l_q)=L(l_p, l_q)) for subspaces of Lorentz and Orlicz sequence spaces are established. Translated fromMatematicheskie Zametki, Vol. 61, No. 1, pp. 18–25, January, 1997. Translated by V. N. Dubrovsky     

Remarks Concerning Completeness of Translates in Function Spaces

This note explains how to translate the author's old result on cyclic vectors of the multiple shift operator into the language of completeness theorems for integer translates. This translation, together with those results, turns out to be a source for many completeness theorems. In particular, there follows the existence of functions f whose positive integer translates f(x−k), where k ₊ are complete in the spaces C^l₀( ), L^p( ), W^l_p( ), 2<p<∞, l=0, 1, …, as well as in their weighted and/or vector-valued analogues.     

Integral representations of functions and embeddings of sobolev spaces on cuspidal domains

Some classes of cuspidal domainsG ⊂ ℝ ⁿ are introduced, and embeddings of the formW _p ^(l) (G)↪L_q(G),l ∈ ℕ, for sobolev spaces are established. To this end, estimates of some integral operators are needed. These operators cannot be estimated via Riesz potentials or their anisotropic analogs. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 201–219, February, 1997. Translated by V. E. Nazaikinskii     

Zur Existenz von Lösungen gewisser Randwertaufgaben

Summary With the aid of some known results about integral equations of the Hammerstein type there is proofed an existence theorem for the following class of boundary value problems–y–l ₂ y=f(x,y),y(a)=y(b)=0,l ₂>0 mit|f(x, y)|<=l ₁ |y|+l ₃ (x),l ₁ >=0,l ₃ (x)>0. The existence range is determined by the greatest eigenvalue of some linear problem.     

Improved boolean formulas for the Ramsey graphs

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well-known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd² log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}ⁿ of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log² d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.