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.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Construction of extremal Type II Z2k-codes

We give methods for constructing many self-dual ${\mathbb{Z}}_m$-codes and Type II ${\mathbb{Z}}_{2k}$-codes of length 2n starting from a given self-dual ${\mathbb{Z}}_m$-code and Type II ${\mathbb{Z}}_{2k}$-code of length 2n, respectively. As an application, we construct extremal Type II ${\mathbb{Z}}_{2k}$-codes of length 24 for $k=4,5,\dots ,20$ and extremal Type II ${\mathbb{Z}}_{2k}$-codes of length 32 for $k=4,5,\dots ,10$. We also construct new extremal Type II ${\mathbb{Z}}_4$-codes of lengths 56 and 64.     

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$.     

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.     

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.     

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.