We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.

For graphs $G$, $F_1$, $F_2$, we write $G\to (F_1,F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\widehat{r}(F_1,F_2)$ is the minimum number of edges of a graph $G$ such that $G\to (F_1,F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t\ge 2$ matchings $t{K}_2$, the size Ramsey number $\widehat{r}(t{K}_2,C_n)<n+(4t+3)\sqrt{n}$. We improve their upper bound for $t=2$ and $t=3$ by showing that $\widehat{r}(2K_2,C_n)\le n+2\sqrt{3n}+9$ for $n\ge 12$ and $\widehat{r}(3K_2,C_n)<n+6\sqrt{n}+9$ for $n\ge 25$.

Let $T_{s}H$ be the graph obtained from a given graph $H$ by subdividing each edge $s$ times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph $H$, there exist graphs $G$ with $O\left(s\right)$ edges that are Ramsey with respect to $T_{s}H$.

Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential...

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

In this note we present some sufficient conditions for the uniqueness of a stable matching in the Gale-Shapley marriage classical model of even size. We also state the result on the existence of exactly two stable matchings in the marriage problem of odd size with the same conditions.

Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.

Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.

It is well known that each tree metric M has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of M. We extend this result to the class of symmetric matrices M with zero diagonal, positive entries, and such that mij + mkl ≤ max{mik + mjl, mil + mjk} for all distinct i,j,k,l.