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.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

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.     

Context-free grammars,generating functions and combinatorial arrays

Let ${\left[R_{n,k}\right]}_{n,k\ge 0}$ be an array of nonnegative numbers satisfying the recurrence relation $R_{n,k}=(a_{1}n+a_{2}k+a_3)R_{n-1,k}+(b_{1}n+b_{2}k+b_3)R_{n-1,k-1}+(c_{1}n+c_{2}k+c_3)R_{n-1,k-2}$ with $R_{0,0}=1$ and $R_{n,k}=0$ unless $0\le k\le n$. In this paper, we first prove that the array ${\left[R_{n,k}\right]}_{n,k\ge 0}$ can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of ${\left[R_{n,k}\right]}_{n,k\ge 0}$. Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type $B$, and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong $q$-log-convexity of some generating functions.     

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.     

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.     

Sharp upper bounds of the spectral radius of a graph

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges. The spectral radius $\rho \left(G\right)$ of $G$ is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of $\rho \left(G\right)$ which improves some known bounds: If $\frac{(k?2)(k?3)}{2}\le m?n\le \frac{k(k?3)}{2}$, where $k(3\le k\le n)$ is an integer, then $\rho \left(G\right)\le \sqrt{2m?n?k+\frac{5}{2}+\sqrt{2m?2n+\frac{9}{4}}}.$The equality holds if and only if $G$ is a complete graph $K_n$ or $K_4?e$, where $K_4?e$ is the graph obtained from $K_4$ by deleting some edge $e$.     

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.     

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

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