2K2 vertex-set partition into nonempty parts

A graph is 2K₂-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K₂-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C₄-free graphs, circular-arc graphs, spiders, P₄-sparse graphs, and bipartite graphs the 2K₂-partition problem can be solved in polynomial time.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

Partitioning a Graph into Highly Connected Subgraphs

Given , a k‐proper partition of a graph G is a partition of such that each part P of induces a k‐connected subgraph of G. We prove that if G is a graph of order n such that , then G has a 2‐proper partition with at most parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if G is a graph of order n with minimum degree where , then G has a k‐proper partition into at most parts. This improves a result of Ferrara et al. ( Discrete Math 313 (2013), 760–764), and both the degree condition and the number of parts is best possible up to the constant c.     

图的导出森林2-划分

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．     

Partitioning a Graph into Global Powerful k-Alliances

A set S of vertices of a graph is a defensive k-alliance if every vertex ${v\in S}$ has at least k more neighbors in S than it has outside of S. Analogously, a set S is an offensive k-alliance if every vertex in the neighborhood of S has at least k more neighbors in S than it has outside of S. Also, a powerful k-alliance is a set S of vertices of the graph, which is both defensive k-alliance and offensive (k?+?2)-alliance. A powerful k-alliance is called global if it is a dominating set. In this paper we show that for k?≥ 0, no graph is partitionable into global powerful k-alliances and, for k?≤ ?1, we obtain upper bounds on the maximum number of sets belonging to a partition of a graph into global powerful k-alliances. In addition, we study the close relationships that exist between partitions of a Cartesian product graph, Γ₁?× Γ₂, into (global) powerful (k ₁?+?k ₂)-alliances and partitions of Γ _i into (global) powerful k _i -alliances, ${i\in \{1,2\}}$ .     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

A general rule for disk and hemisphere partition into equal-area cells

A new general rule is presented to define procedures in order to cut a disk or a hemisphere into an imposed number of equal-area cells. The system has several degrees of freedom that can be fixed, for instance, by enforcing the cells aspect ratios. Therefore, the cells can have very comparable forms, i.e. close to the square. This kind of method is effectively useful because it is not possible to build exact dense uniform distributions of points on the sphere. However, it will be shown that it is easy to cover the sphere, the hemisphere or the disk with equal-area cells. This capability makes easy, for instance, the implementation of stratified sampling in Monte Carlo methods. Moreover, the use of different azimuthal projections allows to link problems initially stated either on the hemisphere or within the circle.     

Ramsey’s theorem and König’s Lemma

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

Exponentially many genus embeddings of the complete graph K 12s+3

In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding(or rotation) scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s+3, which show that there are at least12× 2(009)s distinct genus embeddings for K12s+3.     

Lagrangian 4-planes in holomorphic symplectic varieties of K3[4]-type

We classify the cohomology classes of Lagrangian 4-planes ?⁴ in a smooth manifold X deformation equivalent to a Hilbert scheme of four points on a K3 surface, up to the monodromy action. Classically, the Mori cone of effective curves on a K3 surface S is generated by nonnegative classes C, for which (C, C) ≥ 0, and nodal classes C, for which (C, C) = ?2; Hassett and Tschinkel conjecture that the Mori cone of a holomorphic symplectic variety X is similarly controlled by “nodal” classes C such that (C, C) = ?γ, for (·,·) now the Beauville-Bogomolov form, where γ classifies the geometry of the extremal contraction associated to C. In particular, they conjecture that for X deformation equivalent to a Hilbert scheme of n points on a K3 surface, the class C = ? of a line in a smooth Lagrangian n-plane ? ⁿ must satisfy (?,?) = ?(n + 3)/2. We prove the conjecture for n = 4 by computing the ring of monodromy invariants on X, and showing there is a unique monodromy orbit of Lagrangian 4-planes.