On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

A new forbidden pair for 6-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. If every $k$-connected graph with no $k$-contractible edge has either $H_1$ or $H_2$ as a subgraph, then an unordered pair of graphs $\{H_1,H_2\}$ is said to be a forbidden pair for $k$-contractible edges. We prove that $\{K_1+3K_2,K_1+(P_3\cup K_2)\}$ is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.     

Turán numbers of vertex-disjoint cliques in r-partite graphs

For two graphs $G$ and $H$, the Turán number$ex(G,H)$ is the maximum number of edges in a subgraph of $G$ that contains no copy of $H$. Chen, Li, and Tu determined the Turán numbers $ex(K_{m,n},k{K}_2)$ for all $k\ge 1$ Chen et al. (2009). In this paper we will determine the Turán numbers $ex(K_{a_1,\dots ,a_r},k{K}_r)$ for all $r\ge 3$ and $k\ge 1$.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$