Sharp Dirac's theorem for DP‐critical graphs

Correspondence coloring, or DP‐coloring, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP‐colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list‐critical graphs that satisfy Dirac's bound with equality.     

The automorphism group of a product of hypergraphs

A theorem of G. Sabidussi (1959, Duke Math. J. 26, 693–696) gives necessary and sufficient conditions for the automorphism group of the wreath product of two graphs to be the wreath product of their respective automorphism groups. In this paper we define a wreath product of hypergraphs and prove a theorem extending that of Sabidussi.     

On the graph of a function over a prime field whose small powers have bounded degree

Let f be a function from a finite field with a prime number p of elements, to . In this article we consider those functions f(X) for which there is a positive integer with the property that f(X)ⁱ, when considered as an element of , has degree at most p−2−n+i, for all i=1,…,n. We prove that every line is incident with at most t−1 points of the graph of f, or at least n+4−t points, where t is a positive integer satisfying n>(p−1)/t+t−3 if n is even and n>(p−3)/t+t−2 if n is odd. With the additional hypothesis that there are t−1 lines that are incident with at least t points of the graph of f, we prove that the graph of f is contained in these t−1 lines. We conjecture that the graph of f is contained in an algebraic curve of degree t−1 and prove the conjecture for t=2 and t=3. These results apply to functions that determine less than directions. In particular, the proof of the conjecture for t=2 and t=3 gives new proofs of the result of Lovász and Schrijver [L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Sci. Math. Hungar. 16 (1981) 449–454] and the result in [A. Gács, On a generalization of Rédei’s theorem, Combinatorica 23 (2003) 585–598] respectively, which classify all functions which determine at most 2(p−1)/3 directions.     

G ∞-Formality Theorem in Terms of Graphs and Associated Chevalley–Eilenberg–Harrison Cohomology #

In 1997, M. Kontsevich proved the L _∞-formality conjecture (which implies the existence of star-products for any Poisson manifold) using graphs. A year later, D. Tamarkin gave another proof of a more general conjecture (for G _∞-structures) using operads and cohomological methods. In this article, we show how Tamarkin's construction can be written using graphs. For that, we introduce a generalization of Kontsevich graphs on which we define a “Chevalley–Eilenberg–Harrison” complex. We show that this complex on graphs is related to the “Chevalley–Eilenberg–Harrison” complex for maps on polyvector fields, which is trivial and give Tamarkin's formality theorem as a consequence. This formality reduces to an L _∞-formality.     

A Fixed Point Theorem of Krasnoselskii—Schaefer Type

In this paper we focus on three fixed point theorems and an integral equation. Schaefer's fixed point theorem will yield a T-periodic solution of (0.1) x(t)= a(t) + ^t_t-h D(t,s)g(s,x(s))ds if D and g satisfy certain sign conditions independent of their magnitude. A combination of the contraction mapping theorem and Schauder's theorem (known as Krasnoselskii's theorem) will yield a T-periodic solution of (0.2) x(t) = f(t,x(t)) + ^t_t-h D(t,s)g(s,x(s))ds if f defines a contraction and if D and g are small enough. We prove a fixed point theorem which is a combination of the contraction mapping theorem and Schaefer's theorem which yields a T-periodic solution of (0.2) when / defines a contraction mapping, while D and g satisfy the aforementioned sign conditions.     

t-expansive andt-wise intersecting hypergraphs

We give a hypergraph generalization of Gallai's theorem about factor-critical graphs. This result can be used to determine ^*(r, t) forr < 3t/2, where ^*(r, t) denotes the maximum value of the fractional covering numbers oft-wise intersecting hypergraphs of rankr. Dedicated to Tibor Gallai     

A coincidence point result in Menger spaces using a control function

In the present work we prove a coincidence point theorem in Menger spaces with a t-norm T which satisfies the condition sup{T(t,t):t<1}=1. As a corollary of our theorem we obtain some existing results in metric spaces and probabilistic metric spaces. Particularly our result implies a probabilistic generalization of Banach contraction mapping theorem. We also support our result by an example.     

A generalization of Eagon–Reiner’s theorem and a characterization of bi-CMt bipartite and chordal graphs

We give a generalization of Eagon-Reiner’s theorem relating Betti numbers of the Stanley-Reisner ideal of a simplicial complex and the CM_t property of its Alexander dual. Then we characterize bi-CM_t bipartite graphs and bi-CM_t chordal graphs. These are generalizations of recent results due to Herzog and Rahimi.     

On the Number of Precolouring Extensions

We investigate the number of proper λ -colourings of a hypergraph extending a given proper precolouring. We prove that this number agrees with a polynomial in λ for any sufficiently largeλ , and we establish a generalization of Whitney’s broken circuit theorem by applying a recent improvement of the inclusion–exclusion principle.     

A note on kernels and Sperner’s Lemma

The kernel-solvability of perfect graphs was first proved by Boros and Gurvich, and later Aharoni and Holzman gave a shorter proof. Both proofs were based on Scarf’s Lemma. In this note we show that a very simple proof can be given using a polyhedral version of Sperner’s Lemma. In addition, we extend the Boros–Gurvich theorem to h-perfect graphs and to a more general setting.     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Covering skew-supermodular functions by hypergraphs of minimum total size

The paper presents results related to a theorem of Szigeti on covering symmetric skew-supermodular set functions by hypergraphs. We prove the following generalization using a variation of Schrijver’s supermodular colouring theorem: if p₁ and p₂ are skew-supermodular functions with the same maximum value, then it is possible to find in polynomial time a hypergraph of minimum total size that covers both p₁ and p₂. We also give some applications concerning the connectivity augmentation of hypergraphs.     

A new type of fixed point theorem in metric spaces

We prove a generalization of Edelstein’s fixed point theorem. Though there are thousands of fixed point theorems in metric spaces, our theorem is a new type of theorem.     

A generalization of chordal graphs

In a 3-connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3-connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique-sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.     

A generalized mixed vector variational-like inequality problem

In this paper, we introduce relaxed η-α-P-monotone mapping, and by utilizing KKM technique and Nadler’s Lemma we establish some existence results for the generalized mixed vector variational-like inequality problem. Further, we give the concepts of η-complete semicontinuity and η-strong semicontinuity and prove the solvability for generalized mixed vector variational-like inequality problem without monotonicity assumption by applying the Brouwer’s fixed point theorem. The results presented in this paper are extensions and improvements of some earlier and recent results in the literature.     

Three-graphs without two triples whose symmetric difference is contained in a third

Katona conjectured that if a three-graph has 3n vertices and n³+1 triples, then there are two triples whose symmetric difference is contained in a third triple. This conjecture can be considered as a natural generalization of Turán's theorem [4] for edge graphs. The aim of this note is to prove this conjecture.     

Total chromatic number of complete r-partite graphs

Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete r-partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete r-partite graph. Rosenfeld's result had been generalized recently to complete r-partite graphs by Yap (1989). The main result of this paper is to prove that the total chromatic number of every complete r-partite graph G of odd order is Δ (G) + 1. This result gives a partial generalization of Bermond's theorem.     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Existence of periodic solutions for a fourth-order -Laplacian equation with a deviating argument

In this paper, we study the existence of periodic solutions for a fourth-order p-Laplacian differential equation with a deviating argument as follows:

[φ_p(u^″(t))]^″+f(u^″(t))+g(u(t−τ(t)))=e(t).