The undirected two disjoint shortest paths problem

The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source–sink pairs $(s_i,t_i)$ asks if there exist $k$ pairwise edge- or vertex-disjoint shortest $s_i$–$t_i$-paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for $2$-DSPP on undirected graphs with non-negative edge lengths.     

More complete intersection theorems

The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a $k$-uniform $t$-intersecting family on $n$ points, and describes all optimal families. In recent work, we extended this theorem to the weighted setting, giving the maximum ${\mu }_p$ measure of a $t$-intersecting family on $n$ points. In this work, we prove two new complete intersection theorems. The first gives the supremum ${\mu }_p$ measure of a $t$-intersecting family on infinitely many points, and the second gives the maximum cardinality of a subset of ${\mathbb{Z}}_m^n$ in which any two elements $x,y$ have $t$ positions $i_1,\dots ,i_t$ such that $x_{i_j}?y_{i_j}\in \{?(s?1),\dots ,s?1\}$. In both cases, we determine the extremal families, whenever possible.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Erdős–Gallai stability theorem for linear forests

The Erd?s–Gallai Theorem states that every graph of average degree more than $l?2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=\left({?}_{i=1}^k{P}_{2a_i}\right)?\left({?}_{i=1}^l{P}_{2b_i+1}\right)$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta \left(G\right)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i?1$, then $F?G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

A note on the weak (2,2)-Conjecture

Let $G=(V,E)$ be any graph without isolated edges. The well known 1–2–3 Conjecture asserts that the edges of $G$ can be weighted with $1,2,3$ so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if $G$ additionally has no isolated triangles, then it can be edge decomposed into two subgraphs $G_1,G_2$ which fulfil the 1–2–3 Conjecture with just weights 1,2, i.e. such that there exist weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ so that for every $uv\in E$, if $uv\in E\left(G_i\right)$ then $d_{{\omega }_i}\left(u\right)\ne d_{{\omega }_i}\left(v\right)$, where $d_{{\omega }_i}\left(v\right)$ denotes the sum of weights incident with $v\in V$ in $G_i$ for $i=1,2$. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if $\delta \left(G\right)\ge 3660$, then $G$ can be decomposed into graphs $G_1,G_2$ for which weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ exist so that for every $uv\in E$, $d_{{\omega }_1}\left(u\right)\ne d_{{\omega }_1}\left(v\right)$ or $d_{{\omega }_2}\left(u\right)\ne d_{{\omega }_2}\left(v\right)$. In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

Ramsey number of multiple copies of stars

Let G and H be simple graphs. The Ramsey number $r(G,H)$ is the minimum integer N such that any red-blue-coloring of edges of $K_N$ contains either a red copy of G or a blue copy of H. Let $m{K}_{1,t}$ denote m vertex-disjoint copies of $K_{1,t}$. A lower bound is that $r(m{K}_{1,t},n{K}_{1,s})\ge m(t+1)+n?1$. Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t=s=3$, $m\ge 2$ and $m\ge n$. In this paper, we show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t\ge s=3,m\ge 2$ and $m\ge n$. We also show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $s\ge 4,t>\frac{s(s?1)}{2}$ and $m>n$.     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

Properties of G-martingales with finite variation and the application to G-Sobolev spaces

As is known, if $B={\left(B_t\right)}_{t\in [0,T]}$ is a $G$-Brownian motion, a process of form ${\int }_0^t{\eta }_{s}d{〈B〉}_s?{\int }_0^{t}2G\left({\eta }_s\right)ds$, $\eta \in M_G^1(0,T)$, is a non-increasing $G$-martingale. In this paper, we shall show that a non-increasing $G$-martingale cannot be form of ${\int }_0^t{\eta }_{s}ds$ or ${\int }_0^t{\gamma }_{s}d{〈B〉}_s$, $\eta ,\gamma \in M_G^1(0,T)$, which implies that the decomposition for generalized $G$-Itô processes is unique: For arbitrary $\zeta \in H_G^1(0,T)$, $\eta \in M_G^1(0,T)$ and non-increasing $G$-martingales $K,L$, if ${\int }_0^t{\zeta }_{s}d{B}_s+{\int }_0^t{\eta }_{s}ds+K_t=L_t,t\in [0,T],$then we have $\eta \equiv 0$, $\zeta \equiv 0$ and$K_t=L_t$. As an application, we give a characterization to the $G$-Sobolev spaces introduced in Peng and Song (2015).     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Forcing clique immersions through chromatic number

Building on recent work of Dvořák and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t+4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no independent set of size three contains $K_{2\lfloor n∕5\rfloor }$ as an immersion.