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)\}.$     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

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.     

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.     

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.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

Packed words and quotient rings

The coinvariant algebra is a quotient of the polynomial ring $\mathbb{Q}[x_1,\dots ,x_n]$ whose algebraic properties are governed by the combinatorics of permutations of length n. A word $w=w_1\dots w_n$ over the positive integers is packed if whenever $i>2$ appears as a letter of w, so does $i?1$. We introduce a quotient $S_n$ of $\mathbb{Q}[x_1,\dots ,x_n]$ which is governed by the combinatorics of packed words. We relate our quotient $S_n$ to the generalized coinvariant rings of Haglund, Rhoades, and Shimozono as well as the superspace coinvariant ring.     

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.