For graph $G$ and integers $a_1 ge cdots ge a_r ge 2$, we write $G rightarrow (a_1 ,cdots ,a_r)^v$ if and only if for every $r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i in {1, cdots, r}$. The v
ertex Folkman number $F_v(a_1 ,cdots ,a_r; s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G rightarrow (a_1 ,cdots ,a_r)^v$. It is well known that if $G rightarrow (a_1 ,cdots ,a_r)^v$ then $chi(G) geq m$, where $m = 1+ sum_{i=1}^r (a_i - 1)$. In this paper we study such Folkman graphs $G$ with chromatic number $chi(G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G rightarrow (s,cdots_r,s)^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ for this $r$-color arrowing to hold. We also conjecture that, in some cases, our construction is the best possible, in particular that for every $s ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s; s+1)$ vertices with $chi(G)=2s-1$ such that $G rightarrow (s,s)^v$.
For a planar graph with a given f-vector $(f_{0}, f_{1}, f_{2}),$ we introduce a cubic polynomial whose coefficients depend on the f-vector. The planar graph is said to be real if all the roots of the corresponding polynomial are real. Thus we have a
bipartition of all planar graphs into two disjoint class of graphs, real and complex ones. As a contribution toward a full recognition of planar graphs in this bipartition, we study and recognize completely a subclass of planar graphs that includes all the connected grid subgraphs. Finally, all the 2-connected triangle-free complex planar graphs of 7 vertices are listed.
Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy
of $H$. In this paper, we consider $gr_k(K_3 : H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.
A path in an(a) edge(vertex)-colored graph is called a conflict-free path if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called conflict-free (vertex-)connected if for each pair of distinct vertic
es, there is a conflict-free path connecting them. For a connected graph $G$, the conflict-free (vertex-)connection number of $G$, denoted by $cfc(G)(text{or}~vcfc(G))$, is defined as the smallest number of colors that are required to make $G$ conflict-free (vertex-)connected. In this paper, we first give the exact value $cfc(T)$ for any tree $T$ with diameters $2,3$ and $4$. Based on this result, the conflict-free connection number is determined for any graph $G$ with $diam(G)leq 4$ except for those graphs $G$ with diameter $4$ and $h(G)=2$. In this case, we give some graphs with conflict-free connection number $2$ and $3$, respectively. For the conflict-free vertex-connection number, the exact value $vcfc(G)$ is determined for any graph $G$ with $diam(G)leq 4$.
We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. Using a criterion of Vakil and a special position argument due to Schubert, this follows from a particular inequality among Kost
ka numbers of two-rowed tableaux. In most cases, an easy combinatorial injection proves the inequality. For the remaining cases, we use that these Kostka numbers appear in tensor product decompositions of sl_2(C)-modules. Interpreting the tensor product as the action of certain commuting Toeplitz matrices and using a spectral analysis and Fourier series rewrites the inequality as the positivity of an integral. We establish the inequality by estimating this integral.