% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P47}{19(4)}{2012}
\sloppy

\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%\documentclass[12pt]{article}
%\usepackage{amsmath}
%\usepackage{latexsym}
%
%\usepackage{url}
%%\usepackage{floatflt}
%\usepackage{amssymb}
%\usepackage{exscale}
%\usepackage{graphicx}
%\usepackage{makeidx}
%
%\usepackage{color}
%\usepackage{pstricks}
%
%\newtheorem{thm}{Theorem}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{con}[thm]{Conjecture}
%\newtheorem{remark}[thm]{Remark}
%\newtheorem{lem}[thm]{Lemma}
%\newtheorem{problem}[thm]{Problem}
%\newtheorem{dnt}[thm]{Definition}
\newtheorem{alg}[theorem]{Algorithm}


%\newenvironment{proof}[1][Proof]
%{\par\noindent{\bf #1.} }{\hspace*{\fill}\nolinebreak{$\Box$}\bigskip\par}

%\begin{center} {  Luis Boza, Janusz Dybizba\'nski, Tomasz Dzido}\end{center}
%\begin{center} {  University of Sevilla, University of Gda\'nsk}\end{center}

\title{\bf Three color Ramsey numbers for graphs \\ with at most 4 vertices }

\author{Luis Boza\\
\small University of Sevilla\\[-0.8ex]
\small Department of Applied Mathematics I\\[-0.8ex]
\small Reina Mercedes 2, 41012-Seville, Spain\\[-0.8ex]
\small \tt{boza@us.es}\\
\and
\large Janusz Dybizba\'nski\quad Tomasz Dzido\\
\small University of Gda\'nsk\\[-0.8ex]
\small Institute of Informatics\\[-0.8ex]
\small Wita Stwosza 57, 80-952 Gda\'nsk, Poland\\[-0.8ex]
\small \tt{jdybiz@inf.ug.edu.pl, tdz@inf.ug.edu.pl}\\
}

\date{\dateline{Mar 23, 2012}{Dec 8, 2012}{Dec 31, 2012}\\
\small Mathematics Subject Classifications: 05C55, 05D10}


\begin{document}
\maketitle
\begin{abstract}
For given graphs $H_{1}, H_{2}, H_{3}$, the \emph{3-color Ramsey number} $R(H_{1},$ $H_{2}, H_{3})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph of order $n$ with $3$ colors, then it always contains a monochromatic copy of
$H_{i}$ colored with $i$, for some $1 \leq i \leq 3$.

We study the bounds on 3-color Ramsey numbers $R(H_1,H_2,H_3)$, where $H_i$ is an isolate-free graph different from $K_2$ with at most four vertices, establishing that $R(P_4,C_4,K_4)=14$, $R(C_4,K_3,K_4-e)=17$, $R(C_4,K_3+e,K_4-e)=17$, $R(C_4,K_4-e,K_4-e)=19$, $28\le R(C_4,K_4-e,K_4)\le36$, $R(K_3,K_4-e,K_4)\le41$, $R(K_4-e,K_4-e,K_4)\le59$ and $R(K_4-e,K_4,K_4)\le113$. Also, we prove that $R(K_3+e,K_4-e,K_4-e)=R(K_3,K_4-e,K_4-e)$, $R(C_4,K_3+e,K_4)\le\max\{R(C_4,K_3,K_4),29\}\le32$, $R(K_3+e,K_4-e,K_4)\le\max\{R(K_3,K_4-e,K_4),33\}\le41$ and $R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.

This paper is an extension of the article by Arste, Klamroth, Mengersen [{\em Utilitas Mathematica}, 1996].
\end{abstract}

\section{Introduction}

In this paper all graphs considered are undirected, finite and
contain neither loops nor multiple edges. Let $G$ be such a graph.
The vertex set of $G$ is denoted by $V(G)$, the edge set of $G$
by $E(G)$, and the number of edges in $G$ by $e(G)$. The degree of the vertex $v$ and the number of the edge incident to $v$ colored with color $i$ are denoted with $d(v)$ and $d_i(v)$, respectively. By $\delta_i(G)$ and $\Delta_i(G)$ we denote the minimum and the maximum degree of vertices in $G$ that are colored with color $i$, respectively. The open neighborhood of vertex $v$ in color $i$ in graph $G$ is $N_i(v) = \{u \in V(G) | \{u,v\} \in E(G) \textrm { and $\{u,v\}$ is colored with color $i$} \}$. Define $G[S]$ to be a subgraph of $G$ induced by a set of vertices $S \subseteq V(G)$ and $G^{i}$ to be a graph induced by the edges of $G$ colored with color $i$. Let $P_n$ (resp. $C_n$) be the path (resp. cycle) on $n$ vertices. The cardinality of a set $A$ is denoted by $|A|$.

For given graphs $G_{1}, G_{2},\ldots,G_{k}$, $k \ge 2$, the \emph{multicolor Ramsey number} $R(G_{1}, G_{2},\ldots$, $G_{k})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph of order $n$ with $k$ colors, then it always contains a monochromatic copy of $G_{i}$ colored with the color $i$, for some $1 \leq i \leq k$. A coloring of the edges of $n$-vertex complete graph with $m$ colors is called a $(G_1, G_2,\ldots,G_m ; n)$-coloring, if it does not contain a subgraph isomorphic to $G_i$ colored with the color $i$, for each $i$. The set of all non-isomorphic $(G_1,\ldots,G_m;n)$-colorings is denoted by $(G_1,\ldots,G_m;n)$. We refer to consecutive colors corresponding to the parameters of colorings as red, blue and green.

In this paper we consider isolate-free graphs different from $K_2$ with at most four vertices, improving some results from the article by Arste, Klamroth, Mengersen~\cite{AKM} from 1996 and~\cite{DyDz}.

Note that $R(H_1,H_2,H_3)=R(H_{\sigma(1)},H_{\sigma(2)},H_{\sigma(3)})$ for every permutation $\sigma$ of $\{1,2,3\}$. The case $K_2$ is omitted here, because $R(K_2,H_2,H_3)=R(H_2,H_3)$ and these numbers were already determined in \cite{CH1,CH2,GG}.

We use the following two formulas, which are very well known:

\vspace{3mm}

\noindent $R(H'_1,H'_2,H'_3)\ge R(H_1,H_2,H_3)$, if $H_i$ is a subgraph of $H'_i$.\hfill (1)

\vspace{3mm}

\noindent $R(H_1,H_2,H_3)\le R(H_1-v_1,H_2,H_3)+R(H_1,H_2-v_2,H_3)+R(H_1,H_2,H_3-v_3)-1$, if $v_i\in V(H_i)$, with strict inequality when the right-hand-side and at least one of its terms are even.\hfill (2)

% In general, we expect that even paths cases are harder than those for odd paths.

\section{Results}

The values $R(H_1,H_2,H_3)$ are known if:

\begin{itemize}
\item some $H_i$ is $P_3$, $2K_2$, $P_4$ or $K_{1,3}$, except $R(P_4,C_4,K_4)$ \cite{AKM,BE3,BuRo1,Ex7,Jac,KM2},
\item some $H_i$ is $C_4$, $K_3$, $K_3+e$ or $K_4-e$ and the other are $C_4$, $K_3$ or $K_3+e$, except $R(K_3,C_4,K_4-e)$ and $R(K_3+e,C_4,K_4-e)$ \cite{AKM,BS,DyDz,ExRe,GG,Schu,ShWR}.
\end{itemize}

Also, bounds of other values are known \cite{AKM,DyDz,Ex7,Ka2,KLR,Piw2,PR1,ShWR,XSR1}.

In this paper we improve the lower bound $R(C_4,K_4-e,K_4)\ge27$ obtained from (1). Also, we improve the upper bounds $R(C_4,K_3,K_4-e)\le25$, $R(C_4,K_3+e,K_4-e)\le25$, $R(C_4,K_3+e,K_4)\le43$, $R(C_4,K_4-e,K_4)\le54$, $R(K_3,K_4-e,K_4)\le44$, $R(K_3+e,K_4-e,K_4)\le44$, $R(K_4-e,K_4-e,K_4)\le60$ and $R(K_4-e,K_4,K_4)\le121$, obtained from (2), as well as $R(P_4,C_4,K_4)\le 15$ \cite{AKM} and $R(C_4,K_4-e,K_4-e)\le22$ \cite{DyDz}.

We prove that $R(P_4,C_4,K_4)=14$, $R(C_4,K_3,K_4-e)=17$, $R(C_4,K_3+e,K_4-e)=17$, $R(C_4,K_4-e,K_4-e)=19$, $28\le R(C_4,K_4-e,K_4)\le36$, $R(K_3,K_4-e,K_4)\le41$, $R(K_4-e,K_4-e,K_4)\le59$ and $R(K_4-e,K_4,K_4)\le113$.

For some classes of $G$ and $H$, it was known that $R(K_3+e,G,H)=R(K_3,G,H)$, for instance $R(K_3+e,K_3+e,K_4)=R(K_3,K_3+e,K_4)=R(K_3,K_3,K_4)$ \cite{AKM} and $R(K_3+e,K_3+e,K_4-e)=R(K_3,K_3+e,K_4-e)=R(K_3,K_3,K_4-e)$ \cite{ShWR}. We prove that $R(K_3+e,K_4-e,K_4-e)=R(K_3,K_4-e,K_4-e)$. Also, we prove that $R(C_4,K_3+e,K_4)\le\max\{R(C_4,K_3,K_4),29\}\le32$, $R(K_3+e,K_4-e,K_4)\le\max\{R(K_3,K_4-e,K_4),33\}\le41$ and $R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.

Now, we give the values and bounds of $R(H_1,H_2,H_3)$ in the following tables. Although the first two complete tables and parts of the remaining tables are shown in \cite{AKM}, for the sake of completeness, we repeat them below. In these tables, the lower bounds obtained from (1) are marked with a ``*". Also, we will mark with ``$\dag$" the upper bounds obtained using (2). We use bold style to denote the new values or bounds presented in this paper.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\cline{1-2}
     $P_3$ &  5{\tiny\cite{BuRo1}}\\ \cline{3-3}
     $2K_2$ & 4{\tiny\cite{AKM}} & 5{\tiny\cite{AKM}} \\ \cline{4-4}
     $P_4$ & 5{\tiny\cite{AKM}} & 5{\tiny\cite{AKM}} & 5{\tiny\cite{AKM}} \\ \cline{5-5}
     $K_{1,3}$ & 5{\tiny\cite{BuRo1}} & 6{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}} & 7{\tiny\cite{BuRo1}} \\ \cline{6-6}
     $C_4$ & 6{\tiny\cite{AKM}} & 6{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}} & 7{\tiny\cite{KM2}} & 8{\tiny\cite{AKM}} \\ \cline{7-7}
     $K_3$ & 5{\tiny\cite{Jac}} & 6{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}} & 9{\tiny\cite{Jac}} & 8{\tiny\cite{AKM}} & 11{\tiny\cite{BE3}} \\ \cline{8-8}
     $K_3+e$ & 5{\tiny\cite{AKM}} & 6{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}} & 8{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} \\ \cline{9-9}
     $K_4-e$ & 7{\tiny\cite{AKM}} & 6{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 11{\tiny\cite{Ex7}} \\ \cline{10-10}
     $K_4$ & 7{\tiny\cite{Jac}} & 8{\tiny\cite{AKM}} & 10{\tiny\cite{AKM}} & 13{\tiny\cite{Jac}} & 13{\tiny\cite{AKM}} & 17{\tiny\cite{BE3}} & 17{\tiny\cite{AKM}} & 17{\tiny\cite{AKM}} & 35{\tiny\cite{BE3}} \\ \hline
     {\large$P_3$} & $P_3$ & $2K_2$ & $P_4$ & $K_{1,3}$ & $C_4$ & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values of $R(P_3,H_1,H_2)$.}
\label{tp3}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\cline{1-2}
     $2K_2$ & 6{\tiny\cite{KM2}}\\ \cline{3-3}
     $P_4$ & 6{\tiny\cite{KM2}} & 6{\tiny\cite{KM2}}\\ \cline{4-4}
     $K_{1,3}$ & 6{\tiny\cite{KM2}} & 6{\tiny\cite{KM2}} & 7{\tiny\cite{KM2}}\\ \cline{5-5}
     $C_4$ & 6{\tiny\cite{KM2}} & 6{\tiny\cite{KM2}} & 7{\tiny\cite{KM2}} & 7{\tiny\cite{KM2}}\\ \cline{6-6}
     $K_3$ & 7{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{Jac}} & 8{\tiny\cite{KM2}}\\ \cline{7-7}
     $K_3+e$ & 7{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}}\\ \cline{8-8}
     $K_4-e$ & 7{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 9{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 8{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}}\\ \cline{9-9}
     $K_4$ & 8{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}} & 11{\tiny\cite{KM2}} & 13{\tiny\cite{KM2}} & 20{\tiny\cite{KM2}}\\ \hline
     {\large $2K_2$} & $2K_2$ & $P_4$ & $K_{1,3}$ & $C_4$ & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values of $R(2K_2,H_1,H_2)$.}
\label{t2k2}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\cline{1-2}
     $P_4$ & 6{\tiny\cite{Ir}}\\ \cline{3-3}
     $K_{1,3}$ & 7{\tiny\cite{AKM}} & 7{\tiny\cite{AKM}}\\ \cline{4-4}
     $C_4$ & 7{\tiny\cite{AKM}} & 8{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}}\\ \cline{5-5}
     $K_3$ & 9{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}} & 16{\tiny\cite{BE3}}\\ \cline{6-6}
     $K_3+e$ & 9{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}}\\ \cline{7-7}
     $K_4-e$ & 10{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}}\\ \cline{8-8}
     $K_4$ & 13{\tiny\cite{AKM}} & 13{\tiny\cite{AKM}} & {\bf 14} & 25{\tiny\cite{BE3}} & 25{\tiny\cite{AKM}} & 25{\tiny\cite{AKM}} & 52{\tiny\cite{BE3}}\\ \hline
     {\large $P_4$} & $P_4$ & $K_{1,3}$ & $C_4$ & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values of $R(P_4,H_1,H_2)$.}
\label{tp4}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\cline{1-2}
     $K_{1,3}$ & 8{\tiny\cite{BuRo1}}\\ \cline{3-3}
     $C_4$ & 8{\tiny\cite{AKM}} & 9{\tiny\cite{AKM}}\\ \cline{4-4}
     $K_3$ & 11{\tiny\cite{Jac}} & 11{\tiny\cite{AKM}} & 16{\tiny\cite{BE3}}\\ \cline{5-5}
     $K_3+e$ & 11{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}}\\ \cline{6-6}
     $K_4-e$ & 11{\tiny\cite{AKM}} & 11{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}} & 16{\tiny\cite{AKM}}\\ \cline{7-7}
     $K_4$ & 16{\tiny\cite{Jac}} & 16{\tiny\cite{KM2}} & 25{\tiny\cite{BE3}} & 25{\tiny\cite{AKM}} & 25{\tiny\cite{AKM}} & 52{\tiny\cite{BE3}}\\ \hline
     {\large $K_{1,3}$} & $K_{1,3}$ & $C_4$ & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values of $R(K_{1,3},H_1,H_2)$.}
\label{tk13}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\cline{1-2}
     $C_4$ & 11{\tiny\cite{BS}}\\ \cline{3-3}
     $K_3$ & 12{\tiny\cite{Schu}} & 17{\tiny\cite{ExRe}}\\ \cline{4-4}
     $K_3+e$ & 12{\tiny\cite{AKM}} & 17{\tiny\cite{AKM}} & 17{\tiny\cite{AKM}}\\ \cline{5-5}
     $K_4-e$ & 16{\tiny\cite{DyDz}} & {\bf 17} & {\bf 17} & {\bf 19}\\ \cline{6-6}
     $K_4$ & 20{\tiny\cite{DyDz}}-22{\tiny\cite{XSR1}} & 27{\tiny\cite{DyDz}}-32{\tiny\cite{XSR1}} & 27{\tiny $*$}-{\bf 32} & {\bf 28}-{\bf 36} & 52{\tiny $*$}-72{\tiny\cite{XSR1}}\\ \hline
     {\large $C_4$} & $C_4$ & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values and bounds of $R(C_4,H_1,H_2)$.}
\label{tc4}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\cline{1-2}
     $K_3$ & 17{\tiny\cite{GG}}\\ \cline{3-3}
     $K_3+e$ & 17{\tiny\cite{AKM}} & 17{\tiny\cite{AKM}}\\ \cline{4-4}
     $K_4-e$ & 17{\tiny\cite{ShWR}} & 17{\tiny\cite{ShWR}} & 21{\tiny\cite{ShWR}}-27{\tiny\cite{ShWR}}\\ \cline{5-5}
     $K_4$ & 30{\tiny\cite{Ka2}}-31{\tiny\cite{PR1}} & $R(K_3,K_3,K_4)${\tiny\cite{AKM}} & 30{\tiny $*$}-{\bf 41} & 55{\tiny\cite{KLR}}-79{\tiny $\dag$}\\ \hline
     {\large $K_3$} & $K_3$ & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values and bounds of $R(K_3,H_1,H_2)$.}
 \label{tk3}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\cline{1-2}
     $K_3+e$ & 17{\tiny\cite{YR3}}\\ \cline{3-3}
     $K_4-e$ & 17{\tiny\cite{ShWR}} & $\boldsymbol{R(K_3,K_4-e,K_4-e)}$\\ \cline{4-4}
     $K_4$ & $R(K_3,K_3,K_4)${\tiny\cite{AKM}} & 30{\tiny $*$}-{\bf 41} & 55{\tiny $*$}-79{\tiny $\dag$}\\ \hline
     {\large $K_3+e$} & $K_3+e$ & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Values and bounds of $R(K_3+e,H_1,H_2)$.}
\label{tk4mp3}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\cline{1-2}
     $K_4-e$ & 28{\tiny\cite{Ex7}}-30{\tiny\cite{Piw2}}\\ \cline{3-3}
     $K_4$ & 33{\tiny\cite{ShWR}}-{\bf 59} & 55{\tiny $*$}-{\bf 113}\\ \hline
     {\large $K_4-e$} & $K_4-e$ & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Bounds on $R(K_4-e,H_1,H_2)$.}
\label{tb2}
\end{table}

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|}
\cline{1-2}
     $K_4$ & 128{\tiny\cite{Hilr}}-236{\tiny $\dag$}\\ \hline
     {\large $K_4$} & $K_4$\\ \hline
\end{tabular}
\end{center}
\vspace*{-2ex}
\caption{Bounds on $R(K_4,K_4,K_4)$.}
\label{tk4}
\end{table}

\section{Proofs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$R(P_4,H_1,H_2)$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In \cite{AKM} it is claimed that $14\le R(P_4,C_4,K_4)\le 15$, but no $(P_4,C_4,K_4;13)$-coloring is showed. A $(P_4,C_4,K_4; 13)$-coloring can be found in the Appendix. In this subsection we will prove that $R(P_4,C_4,K_4)=14$.

Let $F$ be a $P_4$-free graph and let $S(F)$ be the set of $(P_4,C_4,K_4;|V(F)|)$-colorings of $G$ such that $G^1=F$.

We note that $R(P_4,C_4,K_4)=14$ if and only if for any $P_4$-free graph $F$ of order 14 $S(F)$ is empty.

Let $H$ and $H'$ be two $P_4$-free graphs. It is easy to obtain $S(H')$ from $S(H)$ if one of the following two algorithms is applied:

Case a) $H$ is an induced subgraph of $H'$ such that $|V(H')|=|V(H)|+1$.
\begin{alg} \label{A1} ~\\
Input: coloring $G\in S(H)$.\\
Output: set of all one-vertex extensions of $G$ which are in $S(H')$.
\end{alg}
%It is similar to Algorithm Extension \ref{alg1}.
For instance, if we consider the coloring $G$ belonging to $S(K_2\cup K_1)$ with 3 vertices, such that the edge $\{1,2\}$ is red and both $\{1,3\}$ and $\{2,3\}$ are blue, then we obtain two colorings of four vertices belonging to $S(2K_2)$, adding a new vertex, assigning red color to $\{3,4\}$, green color to $\{1,4\}$ and blue or green color to $\{2,4\}$. The coloring such that $\{1,4\}$ and $\{2,4\}$ are blue, is not considered because it contains a blue $C_4$. The coloring such that $\{1,4\}$ is blue and $\{2,4\}$ is green, is not considered because it is isomorphic to coloring in which $\{1,4\}$ is green and $\{2,4\}$ is blue.

Case b) $H'$ is a subgraph of $H$ such that $|V(H')|=|V(H)|$.
\begin{alg} \label{A2} ~\\
Input: coloring $G\in S(H)$.\\
Output: set of all colorings of $S(H')$ obtained assigning blue or green color to some edges of $G$.
\end{alg}
For instance, if we consider the coloring $G$ belonging to $S(2K_2\cup K_1)$ with 5 vertices, such that the edges $\{1,2\}$ and $\{3,4\}$ are red, $\{1,5\}$ is blue and the remaining seven edges are green, then we obtain three colorings of five vertices belonging to $S(K_2\cup3K_1)$, assigning blue color to $\{3,4\}$ or assigning blue or green color to $\{1,2\}$. The coloring obtained assigning green color to $\{3,4\}$ is not considered because it contains a green $K_4$.

The lists of graphs generated in order to prove that $S(F)=\emptyset$ for any $P_4$-free graph $F$ of order 14 are not very large, thus, it is not necessary to utilize the program {\em nauty} to eliminate graph isomorphisms \cite{McKay1,McKay2}. To check isomorphisms of graphs, we use the {\em IsomormicQ} command of the {\em Combinatorica} package of the {\em Mathematica} 8.0 program \cite{mat}.

We use the following result:
\begin{lemma} \label{L2P4C4K4}
Let $F_1$, $F_2$ and $F_3$ be three graphs. If $S(F_1)=\emptyset$, $F_3$ is a subgraph of $F_1$ with $V(F_3)=V(F_1)$ and $F_3$ is an induced subgraph of $F_2$, then $S(F_2)=\emptyset$.
\end{lemma}
\begin{proof}
Applying Algorithm \ref{A2} we obtain $S(F_3)$ from $S(F_1)$, thus $S(F_3)=\emptyset$, and applying Algorithm \ref{A1} we obtain $S(F_2)$ from $S(F_3)$, hence $S(F_2)=\emptyset$.
\end{proof}

In order to prove that for any $P_4$-free graph $F$ of order 14, $S(F)=\emptyset$, without loss of generality we can assume that the components of $F$ are $K_2$, $K_3$ or $K_{1,n}$, with $n\ge3$, because if $K_1$ or $P_3$ are  components of $F$, there exists a graph $F_0$ or order 14 such that $F$ is a subgraph of $F_0$ and $K_1$ and $P_3$ are not components of $F_0$. Thus, if $S(F_0)=\emptyset$ then, applying Algorithm \ref{A2}, we have that $S(F)=\emptyset$.

Since $R(C_4,K_4)=10$ \cite{CH2}, $F_0$ has no independent set of order 10 and, since $R(P_3,C_4$, $K_4)=13$, $F_0$ has at least two components different of $K_2$. Thus, it is easy to check that $F_0\in\{4K_3\cup K_2,3K_3\cup K_{1,4},2K_3\cup K_{1,7},2K_3\cup K_{1,5}\cup K_2,2K_3\cup2K_{1,3},2K_3\cup K_{1,3}\cup2K_2,2K_3\cup4K_2,K_3\cup K_{1,6}\cup2K_2,K_3\cup K_{1,4}\cup K_{1,3}\cup K_2,K_3\cup K_{1,4}\cup3K_2,2K_{1,3}\cup3K_2\}$.

From Lemma \ref{L2P4C4K4}, we obtain:

\begin{corollary}
If $S(K_3\cup 2K_2\cup5K_1)=\emptyset$ then $S(2K_3\cup K_{1,7})$, $S(2K_3\cup K_{1,5}\cup K_2)$, $S(K_3\cup K_{1,6}\cup2K_2)$, $S(K_3\cup K_{1,4}\cup K_{1,3}\cup K_2)$ and $S(2K_{1,3}\cup3K_2)=\emptyset$.
\end{corollary}
\begin{proof}
Let $F_1=K_3\cup 2K_2\cup5K_1$. Considering $F_3=K_3\cup 2K_2\cup5K_1$ we have that $S(2K_3\cup K_{1,5}\cup K_2)$, $S(K_3\cup K_{1,6}\cup2K_2)=\emptyset$. Considering $F_3=K_3\cup K_2\cup7K_1$ we obtain that $S(2K_3\cup K_{1,7})$, $S(K_3\cup K_{1,4}\cup K_{1,3}\cup K_2)=\emptyset$. Finally, considering $F_3=3K_2\cup6K_1$ we obtain that $S(2K_{1,3}\cup3K_2)=\emptyset$.
\end{proof}
\begin{corollary}
If $S(2K_3\cup3K_2\cup K_1)=\emptyset$ then $S(2K_3\cup K_{1,3}\cup2K_2)$, $S(2K_3\cup4K_2)$, $S(K_3\cup K_{1,4}\cup3K_2)=\emptyset$.
\end{corollary}
\begin{proof}
Let $F_1=2K_3\cup3K_2\cup K_1$. Considering $F_3=2K_3\cup3K_2\cup K_1$ we have that $S(2K_3\cup4K_2)=\emptyset$. Considering $F_3=2K_3\cup2K_2\cup3K_1$ we obtain that $S(2K_3\cup K_{1,3}\cup2K_2)=\emptyset$. Finally, considering $F_3=K_3\cup3K_2\cup4K_1$ we obtain that $S(K_3\cup K_{1,4}\cup3K_2)=\emptyset$.
\end{proof}

Consequently, we have that if $S(F)=\emptyset$ for any $F\in{\cal F}=\{4K_3\cup K_2,3K_3\cup K_{1,4},2K_3\cup2K_{1,3},K_3\cup 2K_2\cup5K_1,2K_3\cup3K_2\cup K_1\}$ then $R(P_4,C_4,K_4)=14$.

Now, we are going to prove the main result of this subsection.

\begin{theorem}
$R(P_4,C_4,K_4)=14$.
\end{theorem}
\begin{proof}
It is enough to prove that for any $F\in{\cal F}$ then $S(F)=\emptyset$.

There is a coloring in $S(5K_1)$ for every $(C_4,K_4;5)$-coloring, thus $|S(5K_1)|=13$. From this set, applying Algorithm \ref{A1}, we obtain the sets $S(K_2\cup4K_1)$, $S(2K_2\cup3K_1)$, $S(3K_2\cup2K_1)$, $S(4K_2\cup K_1)$, $S(5K_2)$, $S(K_3\cup4K_2)$, $S(2K_3\cup3K_2)$, the cardinalities of which are 122, 1012, 4808, 8569, 2676, 7466 and 968. From $S(2K_3\cup3K_2)$, applying Algorithm \ref{A2}, we generate the sets $S(2K_3\cup2K_2\cup2K_1)$, $S(2K_3\cup K_2\cup4K_1)$ and $S(2K_3\cup6K_1)$, the cardinalities of which are 944, 84 and 1. From $S(2K_3\cup6K_1)$, applying Algorithm \ref{A1}, we obtain the sets $S(2K_3\cup K_{1,3}\cup3K_1)$, and $S(2K_3\cup2K_{1,3})$, the cardinalities of which are 5  and 0, respectively. Thus $S(2K_3\cup2K_{1,3})=\emptyset$.

From $S(2K_3\cup K_2\cup4K_1)$, applying Algorithm \ref{A2}, we obtain that $S(K_3\cup2K_2\cup5K_1)=\emptyset$.

From $S(2K_3\cup3K_2)$, applying Algorithm \ref{A1}, we generate the set $S(3K_3\cup2K_2)$. Its cardinality is 1. From $S(3K_3\cup2K_2)$, applying Algorithm \ref{A2}, we obtain $S(3K_3\cup K_2\cup2K_1)$ and $S(3K_3\cup4K_1)$. Their cardinalities are 2 and 1. From $S(3K_3\cup4K_1)$, applying Algorithm \ref{A1}, we have that $S(3K_3\cup K_{1,4})=\emptyset$.

From $S(3K_3\cup2K_2)$, applying Algorithm \ref{A1}, we obtain that $S(4K_3\cup K_2)=\emptyset$ and, finally, from $S(3K_3\cup2K_2)$, applying Algorithm \ref{A2}, we have that $S(2K_3\cup3K_2\cup K_1)=\emptyset$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$R(C_4,H_1,H_2)$}
To generate subfamilies of $(C_4,H_1,H_2;n)$, where $H_1, H_2 \in \{K_3,K_4-e\}$ we used the following algorithm.

\begin{alg} Extension\\
Input: coloring $G\in (C_4,H_1,H_2;n)$ \\
Output: set of all one-vertex extensions of $G$ which belong to $(C_4,H_1,H_2;n+1)$
\label{alg1}
\end{alg}

For $R(C_4, K_4-e, K_3)$ we used the next algorithm. Let $H^-=K_2$ if $H=K_3$, and $H^-=P_3$ if $H=K_4-e$.

\begin{alg} Merge\\
Input: coloring $G_1\in (C_4,H,P_3;n)$ and $G_2\in (C_4,H^-,K_4-e;m)$\\
Output: set of all colorings $G\in (C_4,H,K_4-e;n+m+1)$ such that $G_1=G[N_2(v)]$ and $G_2=G[N_3(v)]$
\label{alg2}
\end{alg}

Algorithm~\ref{alg1} is a standard procedure in graph theoretical computations. In case of generated subfamilies of $(C_4,H_1,H_2;n)$, where $H_1, H_2 \in \{K_3,K_4-e\}$ we cannot use it alone because we would have to keep collections of nonisomorphic colorings which are to large. Algorithm~\ref{alg1} is used to determine the collections of colorings $(C_4,P_3,K_3;n)$ for $n\leq 7$, $(C_4,K_4-e,K_2;n)$ for $n\leq 6$ and $(C_4,P_3,K_4-e;n)$ for $n\leq 8$. The colorings from these collections were used as the parameters of Algorithm~\ref{alg2}. Both of these algorithms are often used to determine Ramsey numbers (see~\cite{BaRT,RST}) therefore  we do not discuss them in detail.

Let $t(n)$ denote the maximum number of edges of a graph with $n$ vertices not containing a $C_4$ as a subgraph.


\begin{theorem}
$R(C_4, K_4-e, K_3)=17.$
\label{c4b2k3}
\end{theorem}

\begin{proof}
Since $R(C_4, K_4-e, K_3) \ge R(C_4,K_3,K_3) = 17$ \cite{ExRe}, we obtain the lower bound. To obtain the upper bound we use the following computations. Since $R(C_4,P_3,K_3)=8$ and $R(C_4,K_4-e,K_2)=7$ \cite{AKM}, then for every vertex $u$ we have $d_2(u)\le 7$ and $d_3(u) \le 6$. Since $t(17)=36$ \cite{CFS}, then every coloring of $(C_4, K_4-e, K_3;17)$ must contain a vertex $v$ such that $d_1(v)\leq 4$. There are only $3$ possibilities:
\begin{itemize}

\item There exists a vertex $v$ such that $d_1(v)=3$, $d_2(v)=7$ and $d_3(v)=6$.

We use Algorithm~\ref{alg2} for every graph $G_1\in (C_4,P_3,K_3;7)$ and $G_2\in (C_4,K_4-e,K_2;6)$ and find $8$ colorings of $(C_4,K_4-e,K_3;14)$. Next we use Algorithm~\ref{alg1} to one-vertex extensions of these $8$ colorings and obtain subfamilies of $(C_4,K_4-e,K_3;n)$ for $n\in \{15,16,17\}$. Cardinalities of these sets are 6, 43, 0, respectively.

\item There exists a vertex $v$ such that $d_1(v)=4$, $d_2(v)=7$ and $d_3(v)=5$.

Similarly, for every $G_1\in (C_4,P_3,K_3;7)$ and $G_2\in (C_4,K_4-e,K_2;5)$ we found $26355$ colorings of $(C_4,K_4-e,K_3;13)$. Next, we computed subsets of $(C_4,K_4-e,K_3;n)$ for $n\in \{14,15,16,17\}$, the cardinalities of which are 470854, 515882, 3444, 0, respectively.

\item There exists a vertex $v$ such that $d_1(v)=4$, $d_2(v)=6$ and $d_3(v)=6$.

Again, for every $G_1\in (C_4,P_3,K_3;6)$ and $G_2\in (C_4,K_4-e,K_2;6)$ we found $132266$ colorings of $(C_4,K_4-e,K_3;13)$. Next, we computed subsets of $(C_4,K_4-e,K_3;n)$ for $n \in \{14,15,16,17\}$, the cardinalities of which are 4077662, 8109281, 56653, 0, respectively.
\end{itemize}

Finally, this means that $(C_4,K_4-e,K_3;17)=\emptyset$ and $R(C_4, K_4-e, K_3)=17$.
\end{proof}

In order to prove some Theorems \ref{c4b2k3+e} and \ref{c4k3k4}, we use the following lemma:

\begin{lemma} \label{c4}
Let $F$ be a graph of order $n$ and let $v_1,v_2,v_3\in V(F)$, such that $v_i$, for $i=1,2,3$, is adjacent to at least $\lfloor\frac{n}{3}\rfloor+1$ vertices of $V(F)\backslash\{v_1,v_2,v_3\}$. Then $C_4$ is a subgraph of $G$.
\end{lemma}
\begin{proof}
Let $a_i$ be the number of vertices of $V(F)\backslash\{v_1,v_2,v_3\}$ adjacent to $v_i$ and non-adjacent to the other two vertices of $\{v_1,v_2,v_3\}$, let $b_{i,j}$ be the number of vertices of $V(F)\backslash\{v_1,v_2,v_3\}$ adjacent to $v_i$ and $v_j$ and non-adjacent to the other one vertex of $\{v_1,v_2,v_3\}$ and let $c_{1,2,3}$ be the number of vertices of $V(F)\backslash\{v_1,v_2,v_3\}$ adjacent to $v_1$, $v_2$ and $v_3$. Then $a_1+a_2+a_3+b_{1,2}+b_{1,3}+b_{2,3}+c_{1,2,3}\le n-3$.

Since $v_i$ is adjacent at least to $\lfloor\frac{n}{3}\rfloor$+1 vertices of $V(G)\backslash\{v_1,v_2,v_3\}$, we have that $a_1+b_{1,2}+b_{1,3}+c_{1,2,3}\ge\lfloor\frac{n}{3}\rfloor+1$, $a_2+b_{1,2}+b_{2,3}+c_{1,2,3}\ge\lfloor\frac{n}{3}\rfloor+1$ and $a_3+b_{1,3}+b_{2,3}+c_{1,2,3}\ge\lfloor\frac{n}{3}\rfloor+1$.

Consequently, $a_1+a_2+a_3+2b_{1,2}+2b_{1,3}+2b_{2,3}+3c_{1,2,3}\ge3\lfloor\frac{n}{3}\rfloor+3\ge n+1$ and
$b_{1,2}+b_{1,3}+b_{2,3}+2c_{1,2,3}\ge4$. Then there are $i$ and $j$ such that $b_{i,j}+c_{1,2,3}\ge2$, $v_i$ and $v_j$ have at least two common neighbors belonging to $V(F)\backslash\{v_1,v_2,v_3\}$ and $C_4$ is a subgraph of $F$.
\end{proof}

We prove that adding an edge to $K_3$ leaves its Ramsey number unchanged, such as in the following theorem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
$R(C_4, K_4-e, K_3+e)=R(C_4, K_4-e, K_3)=17$.
\label{c4b2k3+e}
\end{theorem}
\begin{proof}
By Theorem \ref{c4b2k3} and by the monotonicity of Ramsey numbers we have that $17 = R(C_4, K_4-e, K_3) \leq  R(C_4, K_4-e, K_3+e)$. Assume, towards a contradiction, that $R(C_4, K_4-e, K_3)<R(C_4, K_4-e, K_3+e)$. Let $G$ be a $(C_4, K_4-e, K_3+e; 17)$-coloring. There is a green triangle in $G$. Let $\{v_1, v_2, v_3\}$ be the vertices of a green triangle of $G$. Since $R(C_4, P_3, K_3+e)=8$ \cite{AKM}, then $|N_2(v_i)|\le7$ and $|N_1(v_i)|\ge7$ for $i \in \{1,2,3\}$. By Lemma \ref{c4}, we obtain a red $C_4$, a contradiction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
$R(C_4, K_4-e, K_4-e)=19$.
\label{c4b2b2}
\end{theorem}
\begin{proof}
Lower bound $R(C_4, K_4-e, K_4-e)\ge 19$ is presented in \cite{DyDz}. To obtain the upper bound we use similar computations as in the proof of Theorem~\ref{c4b2k3}. Since $R(C_4,P_3,K_4-e)=R(C_4,K_4-e,P_3)=9$ \cite{AKM}, then for every vertex $u$ we have $d_2(u)\le 8$ and $d_3(u) \le 8$. Since $t(19)=42$ \cite{CFS}, then every coloring of $(C_4, K_4-e, K_3; 19)$ must contain vertex $v$ such that $d_1(v)\leq 4$. There are only $4$ possibilities:
\begin{itemize}

\item There is a vertex $v$ such that $d_1(v)=4$, $d_2(v)=7$ and $d_3(v)=7$.

We use Algorithm~\ref{alg2} for every graph $G_1\in (C_4,P_3,K_4-e;7)$ and $G_2\in (C_4,K_4-e,P_3;7)$ and find $621308$ colorings of $(C_4,K_4-e,K_4-e;15)$. Next, we use Algorithm~\ref{alg1} to one-vertex extensions of these colorings and obtain subfamilies of $(C_4,K_4-e,K_3;n)$ for $n\in \{16,17,18,19\}$. Cardinalities of these sets are 731002, 18285, 7, 0, respectively.

\item There is a vertex $v$ such that $d_1(v)=4$, $d_2(v)=8$ and $d_3(v)=6$, (a case in which $d_2(v)=6$ and $d_3(v)=8$ is symmetrical).

Similarly, for every $G_1\in (C_4,P_3,K_4-e;8)$ and $G_2\in (C_4,K_4-e,P_3;6)$ we found $10488$ colorings of $(C_4,K_4-e,K_4-e;15)$. Next, we computed subsets of $(C_4,K_4-e,K_4-e;n)$ for $n\in \{16,17,18\}$, the cardinalities of which are 28733, 1807, 0, respectively.

\item There is a vertex $v$ such that $d_1(v)=3$, $d_2(v)=8$ and $d_3(v)=7$, (a case in which $d_2(v)=7$ and $d_3(v)=8$ is symmetrical).

In this case Algorithm~\ref{alg2} returns an empty set of colorings.

\item There is a vertex $v$ such that $d_1(v)=2$, $d_2(v)=8$ and $d_3(v)=8$.

In this case Algorithm~\ref{alg2} returns an empty set of colorings.
\end{itemize}
We state that set $(C_4,K_4-e,K_4-e;19)=\emptyset$ and $R(C_4, K_4-e, K_4-e)=19$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Also, we have:

\begin{theorem}
$R(C_4,K_3+e,K_4)\le\max\{R(C_4,K_3,K_4),29\}\le32$.
\label{c4k3k4}
\end{theorem}
\begin{proof}
We know that $27 \leq R(C_4 , K_3 , K_4 ) \leq 32$ \cite{DyDz,XSR1}.
Let us suppose that there exists $G$ a $(C_4,K_3+e,K_4;\max\{R(C_4,K_3,K_4),29\})$-coloring. There is a blue triangle in $G$. Let $v_1$, $v_2$, $v_3$ be the vertices of a blue triangle. To avoid a blue $K_4+e$ we have that $d_2(v_i)=2$ and, since $R(C_4, K_3+e, K_3)=17$,
%\cite {AKM},
$d_3(v_i) \leq 16$. Thus $d_1(v_i)\geq\max\{R(C_4,K_3,K_4),29\}-19\ge\lfloor\frac{\max\{R(C_4,K_3,K_4),29\}}{3}\rfloor+1 $. By Lemma \ref{c4}, we have a red $C_4$, a contradiction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
$28 \leq R(C_4,K_4-e,K_4) \leq 36.$
\label{c4b2k4}
\end{theorem}
\begin{proof}
To prove the lower bound, we present a $(C_4,K_4-e,K_4; 27)$-coloring in the Appendix. Let us suppose that there exits $G$, a $(C_4,K_4-e,K_4;36)$-coloring. Since $R(C_4,P_3,$ $K_4)=13$ and $R(C_4,K_4-e,K_3)=17$ then $\Delta_2(G)\le12$, $\Delta_3(G)\le16$, $\delta_1(G)\ge7$, and $|E(G^1)|\ge126$. Since $t(36)\le115$ \cite{CFS}, there is a contradiction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$R(K_3,H_1,H_2)$ and $R(K_3+e,H_1,H_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
$R(K_3+e, K_4-e, K_4-e)=R(K_3,K_4-e,K_4-e).$
\end{theorem}

\begin{proof}
$R(K_3,K_4-e,K_4-e) \geq 21$ \cite{ShWR}. Let us suppose that $R(K_3+e, K_4-e, K_4-e)>R(K_3,K_4-e,K_4-e)$, thus there exists $G$ a $(K_3+e, K_4-e, K_4-e; R(K_3,K_4-e,K_4-e))$-coloring and there is a red triangle in $G$. Let $v_1$, $v_2$ and $v_3$ be the vertices of a red triangle of $G$. We may also assume that $d_2(v_1) \geq 9$. Clearly $G[N_2(v_1)]$ contains no blue $P_3$. Assume that $w_i$, $1 \leq i \leq 9$ are the $9$ first vertices of $G[N_2(v_1)]$.  Next, we consider the cases with respect to the number of blue edges in $G[N_2(v_1)]$ as follows.

\begin{itemize}
\item $G[N_2(v_1)]$ has $4$ disjoint blue edges.

Assume that $\{w_i, w_{i+1}\}$ are blue for all $i \in \{1,3,5,7\}$. To avoid a blue $K_4-e$, without the loss of generality we can assume that $\{v_2, w_i \}$ are green for all $i \in \{2,4,6,8\}$. Without the loss of generality we can assume that $\{w_2, w_4\}$, $\{w_6, w_8\}$  are green, then $\{w_2, w_6\}$, $\{w_2, w_8\}$, $\{w_4, w_6\}$, $\{w_4, w_8\}$ must be red. To prevent $\{v_2, w_2, w_4, w_9\}$ from forming a green $K_4-e$, for at least one $i \in \{2,4\}$, the edge $\{w_i, w_9\}$ is red. We have that $\{w_6, w_9\}$, $\{w_8, w_9\}$ are green, then $\{v_2, w_6, w_8, w_9\}$ forms a green $K_4-e$.

\item $G[N_2(v_1)]$ has $3$ disjoint blue edges.

Clearly $G[N_2(v_1)]$ contains a $K_7-e$ with only red and green edges. By Lemma 2 in \cite{ShWR}, we have either a red $K_3+e$ or a green $K_4-e$.

\item $G[N_2(v_1)]$ has at most $2$ disjoint blue edges.

Since $R(K_3+e, K_4-e)=7$ \cite{CH2}, we immediately obtain a red $K_3+e$ or a green $K_4-e$.
\end{itemize}
\vspace*{-5ex}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

By using similar methods we obtain the following:

\begin{theorem}
$R(K_3, K_4-e, K_4) \leq\max\{R(K_3+e, K_4-e, K_4),33\}\le41$.
\label{rk3b2k4+e}
\end{theorem}

\begin{proof}

Let us suppose that $R(K_3+e, K_4-e, K_4)>\max\{R(K_3+e, K_4-e, K_4),33\}$, thus there exists $G$ be a $(K_3+e, K_4-e, K_4;\max\{R(K_3+e, K_4-e, K_4),33\})$-coloring and there is a red triangle in $G$. Let $v_1$, $v_2$ and $v_3$ be the vertices of a red triangle of $G$. We may also assume that $d_2(v_1) \geq 14$. Clearly $G[N_2(v_1)]$ does not contain any blue $P_3$. Assume that $w_1, w_2, \ldots, w_{14}$ are the $14$ first vertices of $G[N_2(v_1)]$.  Next, we consider the cases with respect to the number of blue edges in $G[N_2(v_1)]$ as follows.

\begin{itemize}
\item $G[N_2(v_1)]$ has $7$ disjoint blue edges.

Assume that $\{w_i, w_{i+1}\}$ are blue for odd $1 \leq i \leq 13$. To avoid a blue $K_4-e$, we can assume that $\{v_2, w_i\}$ are green for even $2 \leq i \leq 14$. Since $R(K_3+e, K_3)=7$ \cite{CH2}, we immediately obtain a red $K_3+e$ or a green $K_4$.

\item $G[N_2(v_1)]$ has $6$ disjoint blue edges.

Assume that $\{w_i, w_{i+1}\}$ are blue for odd $1 \leq i \leq 11$. To avoid a blue $K_4-e$, we can assume that $\{v_2, w_i\}$ are green for even $2 \leq i \leq 12$. If $\{v_2, w_{13}\}$ is green, then by $R(K_3+e, K_3)=7$ \cite{CH2}, we have either a red $K_3+e$ or a green $K_4$. This means that $\{v_2, w_{13}\}$  is blue. Since $R(K_3,K_3)=6$, then we can assume there are two red triangles, let their vertices be $\{w_2, w_4, w_6\}$ and $\{w_8, w_{10}, w_{12}\}$. The remaining edges of a subgraph on $\{w_2, w_4, w_6, w_8, w_{10}, w_{12}\}$ are green. There is at least one green edge in the subgraph on vertices  $\{w_1, w_3, w_5, w_7, w_9, w_{11}\}$, say $\{w_1, w_3\}$, then $\{w_1, w_3, w_6, w_8\}$ forms a green $K_4$.

\item $G[N_2(v_1)]$ has $5$ disjoint blue edges.

Assume that $\{w_i, w_{i+1}\}$ are blue for all $i \in \{1,3,5,7,9\}$. Let us consider a subgraph $H$ on vertices $\{w_2, w_4, w_6, w_8, w_{10}, w_{11}, w_{12}, w_{13}, w_{14}\}$. Since $R(K_3, K_4)=9$, then $H$ contain a red triangle. To avoid a red $K_3+e$ and a green $K_4$ the remaining vertices of $H$ contain a next red triangle. By the fact that a subgraph on vertices $\{w_1, w_3, w_5, w_7, w_9\}$ has at least one green edge, we immediately obtain a green $K_4$.


\item $G[N_2(v_1)]$ has at most $4$ disjoint blue edges.

Since $R(K_3+e, K_4)=10$ \cite{CH2}, we immediately obtain a red $K_3+e$ or a green $K_4$.
\end{itemize}
\vspace*{-5ex}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In order to prove Theorems \ref{k3b2k4} and \ref{k3eb2k4} we use some definitions and lemmas.

\begin{lemma} \label{cot}
Let $G$ be a $(K_3,K_4-e,K_4;41)$-coloring. For any $v\in V(G)$,  $G^2[N_2(v)]\in\{7K_2,6K_1\cup2K_1\}$.
\end{lemma}
\begin{proof}
Let $v_0\in V(G)$ such that $d_2(v_0)=\Delta_2(G)$. Then $d_2(v_0)\le R(K_3,P_3,K_4)-1=16$. If $d_2(v_0)=16$, as $G[N_2(v_0)]$ is a $(K_3,P_3,K_4;16)$-coloring and $R(K_3,K_4)=9$ \cite{GG}, we have that $G^2[N_2(v_0)]=8K_2$. Let $x_1,\ldots,x_8$ be the edges of $G^2[N_2(v_0)]$ and let $w$ be one of the $24$ vertices of $N_1(v_0)\cup N_3(v_0)$. To prevent a blue $K_4-e$, for at least one vertex $w_i$ of $x_i$, with $1\le i\le8$, the edge $\{w,w_i\}$ is red or green. Then $G[\{w,w_1,\ldots,w_8\}]$ has not blue edges and there is a red $K_3$ or a green $K_4$. There is a contradiction, thus $\Delta_2(G)\le 15$.

If $d_2(v_0)=15$, as $G[N_2(v_0)]$ is a $(K_3,P_3,K_4;15)$-coloring, then $G^2[N_2(v_0)]=7K_2\cup K_1$. Let $x_1,\ldots,x_7$ be the edges of $G^2[N_2(v_0)]$, let $u$ be the isolated vertex of $G^2[N_2(v_0)]$ and let $w$ be some of the at least 11 vertices of $(N_1(v_0)\cup N_3(v_0))\backslash N_2(u)$. To prevent a blue $K_4-e$, for at least one vertex $w_i$ of $x_i$, with $1\le i\le7$, the edge $\{w,w_i\}$ is red or green. Then $G[\{w,u,w_1,\ldots,w_7\}]$ has not blue edges and there is a red $K_3$ or a green $K_4$. Thus $\Delta_2(G)\le 14$.

Let $v\in V(G)$. Since $d_1(v)\le R(K_2,K_4-e,K_4)-1=10$, $d_2(v)\le14$, $d_3(v)\le R(K_3,K_4-e,K_3)-1=16$ and $d_1(v)+d_2(v)+d_3(v)=40$, we have that $d_1(v)=10$, $d_2(v)=14$, $d_3(v)=16$ and, as $G[N_2(v)]$ is a $(K_3,P_3,K_4;14)$-coloring, $G^2[N_2(v)]\in\{7K_2,6K_2\cup2K_1\}$.
\end{proof}

Let $A=\{v\in V(G):N_2(v)=6K_2\cup2K_1\}$. We have:
\begin{lemma}
$A\ne\emptyset$.
\end{lemma}
\begin{proof}
If $A=\emptyset$ then every vertex belongs to 7 blue triangles and $G$ has $\frac{41\cdot7}{3}$ blue triangles. This number is not an integer and there is a contradiction.
\end{proof}
For any $v\in A$ we define $D_v=\{u\in N_2(v):d_{G^2[N_2(v)]}(u)=1\}$. Clearly $|N_2(v)\backslash D_v|=2$ and $N_2(v)\backslash D_v\subseteq A$.
\begin{lemma} \label{dis}
Let $v_1\in A$ and $v_0,v_2\in N_2(v_1)\backslash D_{v_1}$, then $N_2(v_0)\cap N_2(v_2)=\{v_1\}$.
\end{lemma}
\begin{proof}
 If $|N_2(v_0)\cap N_2(v_2)\backslash\{v_1\}|\ge1$, since $|N_2(v_0)\backslash\{v_1\}|,|N_2(v_2)\backslash\{v_1\}|=13$, $N_2(v_0)\backslash\{v_1\}$, $N_2(v_2)\backslash\{v_1\}\subset N_1(v_1)\cup N_3(v_1)$ and $|N_1(v_1)\cup N_3(v_1)|=26$, we have that there exists $w\in(N_1(v_1)\cup N_3(v_1))\backslash(N_2(v_0)\cup N_2(v_2))$. Let $x_1,\ldots,x_6$ be the edges of $G^2[N_2(v_1)]$. To prevent a blue $K_4-e$, for at least one vertex $w_i$ of $x_i$, with $1\le i\le6$, the edge $\{w,w_i\}$ is red or green. Then $G[\{w,v_0,v_2,w_1,\ldots,w_6\}]$ has not blue edges and, as $R(K_3,K_4)=9$, there is a red $K_3$ or a green $K_4$, a contradiction.
\end{proof}
Now, we have:
\begin{theorem} \label{k3b2k4}
$R(K_3,K_4-e,K_4)\le 41$.
\end{theorem}
\begin{proof}
Let $G$  be a $(K_3,K_4-e,K_4;41)$-coloring. Let $v_1\in A$, $v_0,v_2\in N_2(v_1)\backslash D_{v_1}$ and $v_3\in (N_2(v_2)\backslash D_{v_2})\backslash\{v_1\}$. By Lemma \ref{dis}, $N_2(v_0)\cap N_2(v_2)=\{v_1\}$ and $N_2(v_1)\cap N_2(v_3)=\{v_2\}$. Let $B=V(G)\backslash\{v_0,v_1,v_2,v_3\}\backslash(D_{v_1}\cup D_{v_2})$. As  $|B|=13$, $|N_2(v_0)\backslash\{v_1,v_3\}|$, $|N_2(v_3)\backslash\{v_0,v_2\}|\ge12$ and $N_2(v_0)\backslash\{v_1,v_3\}$, $N_2(v_3)\backslash\{v_0,v_2\}\subseteq B$, we have that $|(N_2(v_0)\backslash\{v_1,v_3\})\cap(N_2(v_3)\backslash$ $\{v_0,v_2\})|\ge11$ and, as $R(K_3,K_4)=9$,  $G[(N_2(v_0)\backslash\{v_1,v_3\})\cap(N_2(v_3)\backslash\{v_0,v_2\})]$ contains a blue edge and $G[((N_2(v_0)\backslash\{v_1,v_3\})\cap(N_2(v_3)\backslash\{v_0,v_2\}))\cup\{v_0,v_3\}]$ contains a blue $K_4-e$, a contradiction.
\end{proof}

\begin{theorem} \label{k3eb2k4}
$R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.
\end{theorem}
\begin{proof}
The result is obvious if $R(K_3+e,K_4,K_4)=R(K_3,K_4,K_4)\le 79$. Assume that $R(K_3+e,K_4,K_4)>R(K_3,K_4,K_4)$, and let $G$ be a
$(K_3+e,K_4,K_4;$ $R(K_3+e,K_4,K_4)-1)$-coloring. As $R(K_3+e,K_4,K_4)-1\ge R(K_3,K_3,K_4)$, there are at least a triangle in $G$. Let $v$ be a vertex of a red triangle. To avoid a red $K_3+e$, $d_1(v)=2$, and $d_2(v),d_3(v)\le R(K_3+e,K_3,K_4)-1=R(K_3,K_3,K_4)-1$. As $R(K_3+e,K_4,K_4)-1=1+d_1(v)+d_2(v)+d_3(v)$, we have that $R(K_3+e,K_4,K_4)\le2R(K_3,K_3,K_4)+2\le64$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$R(K_4-e,H_1,H_2)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this subsection we show new upper bounds on $R(K_4-e,K_4-e,K_4)$ and $R(K_3,K_4,K_4)$. In order to obtain the main results of this subsection we use the following lemma, which has a computational proof.
\begin{lemma} \label{red8}
Every $(P_3,K_4-e,K_4;16)$-coloring has 8 red edges.
\end{lemma}
\begin{theorem}
$R(K_4-e,K_4-e,K_4)\le59$.
\end{theorem}
\begin{proof}
Let $G$ be a $(K_4-e,K_4-e,K_4;59)$-coloring and let $v\in V(G)$. It is straightforward that $d_1(v),d_2(v)\le R(P_3,K_4-e,K_4)-1=16$ and $d_3(v)\le R(K_4-e,K_4-e,K_3)-1\le26$. Since $d_1(v)+d_2(v)+d_3(v)=58$, we have $d_1(v)=16$ and by Lemma \ref{red8}, $G[N_1(v)]$ has 8 red edges, $v$ belongs to 8 red triangles and $G$ has $\frac{59\cdot8}{3}$ red triangles. This number is not an integer and we have a contradiction.
\end{proof}

In order to prove the last theorem we need the following lemma:

\begin{lemma} \label{t16}
Let $G$ be a $(K_4-e,K_4,K_4;113)$-coloring and let $v\in V(G)$. Then $d_1(v)=32$, $d_2(v),d_3(v)=40$ and $G^1[N_1(v)]=16K_2$.
\end{lemma}
\begin{proof}
The proof of $\Delta_1(G)\le32$ is similar to the proof of Lemma \ref{cot}.

Since $d_1(v)\le32$, $d_2(v),d_3(v)\le R(K_4-e,K_3,K_4)-1\le40$ and $d_1(v)+d_2(v)+d_3(v)=112$, we have that $d_1(v)=32$, $d_2(v)=d_3(v)=40$ and, as $G[N_1(v)]$ is a $(P_3,K_4,K_4;32)$-coloring and $R(K_4,K_4)=18$ \cite{GG}, we have that $G^1[N_1(v)]\in\{16K_2,15K_2\cup2K_1\}$.

Let us suppose $G^1[N_1(v)]=15K_2\cup2K_1$. Let $x_1,\ldots,x_{15}$ be the edges of $G^1[N_1(v)]$, let $u_1$ and $u_2$ be the isolated vertices of $G^1[N_1(v)]$ and let $w$ be some of the at least 18 vertices of $(N_2(v)\cup N_3(v))\backslash(N_1(u_1)\cup N_1(u_2))$. To prevent a red $K_4-e$, for at least one vertex $w_i$ of $x_i$, with $1\le i\le15$, the edge $\{w,w_i\}$ is blue or green. Then $G[\{w,u_1,u_2,w_1,\ldots,w_{15}\}]$ has not red edges and, as $R(K_4,K_4)=18$ \cite{GG}, there is a blue $K_4$ or a green $K_4$, thus there is a contradiction.
\end{proof}
\begin{theorem}
$R(K_4-e,K_4,K_4)\le 113$.
\end{theorem}
\begin{proof}
Let $G$ be a $(K_4-e,K_4,K_4;113)$-coloring. By Lemma \ref{t16}, every vertex of $G$ belongs to 16 blue triangles, thus $G$ has $\frac{113\cdot16}{3}$ blue triangles. This number is not an integer and we have a contradiction.
\end{proof}

\section{Open cases}

The still open cases are the values of $R(H_1,K_4-e,K_4-e)$, with $H_1\in\{K_3,K_3+e,K_4-e,K_4\}$, and $R(H_1,H_2,K_4)$, with $H_1,H_2\in\{C_4,K_3,K_3+e,K_4-e,K_4\}$. In general, the difficulty of these open cases depends on the structure of the graphs and almost always grows with the number of edges of the graphs. On the one hand, we think that the following cases should be solved $R(C_4,C_4,K_4)$, $R(C_4,K_3,K_4)$, $R(K_3,K_4-e,K_4-e)$ or $R(K_3,K_4,K_4)$. On the other hand there is no progress in the bounds on $R(K_4,K_4,K_4)$ since 1982 \cite{Hilr} and the difference between its bounds are 108. Probably, this case can never be solved.

Also, we expect that the values of the open cases are closer to the lower bounds than the upper bounds and we conjecture that $R(K_3+e,H,K_4)=R(K_3,H,K_4)$ for $H\in\{C_4,K_4-e,K_4\}$.

\vspace{1cm}

\noindent{\large\bf Acknowledgement.} We would like to thank the anonymous reviewers
whose suggestions led to improved presentation of this work.

%\SquashBibFurther
\begin{thebibliography}{99}

\bibitem{AKM} J. Arste, K. Klamroth, and I. Mengersen.
\newblock Three Color Ramsey Numbers for Small Graphs.
\newblock {\em Utilitas Mathematica}, 49:85--96, 1996.

\bibitem{BaRT} A. Babak, S. P. Radziszowski and Kung-Kuen Tse.
\newblock Computation of the Ramsey Number $R(B_3,K_5)$.
\newblock {\em Bulletin of the Institute of Combinatorics and Its Applications}, 41:71--76, 2004.

\bibitem{BS} A. Bialostocki and J. Sch\"onheim.
\newblock On Some Tur\'an and Ramsey Numbers for $C_4$.
\newblock {\em Graph Theory and Combinatorics}, ed. B. Bollob\'as, Academic Press, London, 29--33, 1984.

%\bibitem{Bol} B. Bollob\'as, Extremal Graph Theory, {\it Academic Press}, %London, 1978.

%\bibitem{BH} R. Bolze and H. Harborth, The Ramsey Number $r(K_4$-$x,K_5)$, in %{\it The Theory and Applications of Graphs}, (Kalamazoo, MI, 1980), John Wiley %\& Sons, New York, 1981, 109--116.

%\bibitem{boza} L. Boza, Upper bounds for some Ramsey Numbers of $K_n$-$e$ %versus $K_m$, manuscript, 2011.

%\bibitem{Boza2} L. Boza, The Ramsey Number $r(K_5-P_3,K_5)$, {\it Electronic %Journal of Combinatorics}, {\bf 18} (2011), \#90, 10 pages. %{http://www.combinatorics.org/Volume\_18/PDF/v18i1p90.pdf}.

%\bibitem{BoRe} L. Boza and M. P. Revuelta, Sobre el n\'umero de Ramsey %$r(K_3,\ldots,K_3,K_{1,2},\ldots,K_{1,2})$, {\it Avances en matem\'atica %discreta en Andaluc\'{\i}a}, Servicio de Publicaciones de la Universidad de %C\'adiz, C\'adiz (Spain), 2007, 55--59.

\bibitem{BE3} S. A. Burr and P. Erd\"os.
\newblock Generalizations of a Ramsey-Theoretic Result of Chv\'atal.
\newblock {\em Journal of Graph Theory}, 7:39--51, 1983.

\bibitem{BuRo1} S. A. Burr and J. A. Roberts.
\newblock On Ramsey Numbers for stars.
\newblock {\em Utilitas Mathematica}, 4:217--220, 1973.

%\bibitem{CalSR} J. A. Calvert, M. J. Schuster and S. P. Radziszowski, The %Computation of $R(K_5-P_3,K_5)=25$, to appear in the Journal of Combinatorial %Mathematics and Combinatorial Computing, 2011. %{http://www.cs.rit.edu/~spr/PUBL/paper66.pdf}.

%\bibitem{CS} G. Chartrand and S. Schuster, On the existence of specified cycles %in complementary graphs, {\it Bulletin
%of the American Mathematical Society}, {\bf 77} (1971), 995--998.

%\bibitem{Chu1} F. R. K. Chung, On the Ramsey Numbers $N(3,3,\dots,3;2)$, {\it %Discrete Mathematics}, {\bf 5} (1973), 317--321.

\bibitem{CH1} V. Chv\'{a}tal and F.~Harary.
\newblock Generalized Ramsey Theory for Graphs, II. Small Diagonal Numbers.
\newblock {\em Proceedings of the American Mathematical Society}, 32:389--394, 1972.

\bibitem{CH2} V. Chv\'{a}tal and F.~Harary.
\newblock Generalized Ramsey Theory for Graphs, III. Small Off-Diagonal Numbers.
\newblock {\em Pacific Journal of Mathematics}, 41:335--345, 1972.

%\bibitem{Clan} M. Clancy, Some small Ramsey numbers, {\it Journal of Graph %Theory}, {\bf 1} (1977), 89--91.

\bibitem{CFS} C. Clapham, A. Flockhart, and J. Sheehan.
\newblock Graphs Without Four-Cycles.
\newblock {\em Journal of Graph Theory}, 13:29--47, 1989.

\bibitem{DyDz} J. Dybizba\'nski and T. Dzido.
\newblock On Some Ramsey Numbers for Quadrilaterals.
\newblock {\em Electronic Journal of Combinatorics}, 18:\#P154, 12 pages, 2011.
\url{http://www.combinatorics.org/}

%{http://www.combinatorics.org/Volume\_18/PDF/v18i1p154.pdf}.

%\bibitem{Ex4} G. Exoo, A Lower Bound for $R(5,5)$, {\it Journal of Graph %Theory}, {\bf 13} (1989), 97--98.

%\bibitem{Ex6} G. Exoo, A Lower Bound for $r(K_5$-$e,K_5)$, {\it Utilitas %Mathematica}, {\bf 38} (1990), 187--188.

\bibitem{Ex7} G. Exoo.
\newblock On the Three Color Ramsey Number of $K_4-e$.
\newblock {\em Discrete Mathematics}, 89:301--305, 1991.

%\bibitem{Ex8} G. Exoo, Indiana State University, manuscript, 1992.

%\bibitem{Ex10} G. Exoo, A Lower Bound for Schur Numbers and Multicolor Ramsey %Numbers of $K_3$, {\it Electronic
%Journal of Combinatorics}, {\bf 1} (1994), \#R8, 3 pages. %{http://www.combinatorics.org/Volume\_1/PDFFiles/v1i1r8.pdf}.

%\bibitem{EHM1} G. Exoo, H. Harborth and I. Mengersen, The Ramsey Number of %$K_4$ versus $K_5$-$e$, {\it Ars Combinatoria}, {\bf 25A} (1988), 277--286.

\bibitem{ExRe} G. Exoo and D. F. Reynolds.
\newblock Ramsey Numbers Based on $C_5$-Decompositions.
\newblock {\em Discrete Mathematics}, 71:119--127, 1988.

%\bibitem{FKR} S. Fettes, R. L. Kramer and S. P. Radziszowski, An Upper Bound of %62 on the Classical Ramsey
%Number $R(3,3,3,3)$, {\it Ars Combinatoria}, {\bf 72} (2004), 41--63. %{http://www.cs.rit.edu/~spr/PUBL/paper43.pdf}.

%\bibitem{FreSw} H. Fredricksen and M. M. Sweet, Symmetric Sum-Free Partitions %and Lower Bounds for Schur
%Numbers, {\it Electronic Journal of Combinatorics}, {\bf 7} (2000), \#R32, 9 %pages. {http://www.combinatorics.org/Volume\_7/PDF/v7i1r32.pdf}.

%\bibitem{GH} U. Grenda and H. Harborth, The Ramsey Number $r(K_3,K_7$-$e)$, %{\it Journal of Combinatorics, Information and System Sciences}, {\bf 7} %(1982), 166--169.

\bibitem{GG} R. E. Greenwood and A.M. Gleason.
\newblock Combinatorial Relations and Chromatic Graphs.
\newblock {\em Canadian Journal of Mathematics}, 7:1--7, 1955.

%\bibitem{He2} G. R. T. Hendry, Ramsey Numbers for Graphs with Five Vertices, %{\it Journal of Graph Theory}, {\bf 13} (1989), 245--248.

%\bibitem{He3} G. R. T. Hendry, The Ramsey Numbers $r(K_2$+$K_3,K_4)$ and %$r(K_1$+$C_4,K_4)$, {\it Utilitas Mathematica}, {\bf 35} (1989), 40--54, %addendum in {\bf 36} (1989), 25--32.

\bibitem{Hilr} R. Hill and R.W. Irving.
\newblock On Group Partitions Associated with Lower Bounds for Symmetric Ramsey Numbers.
\newblock {\em European Journal of Combinatorics}, 3:35--50, 1982.

\bibitem{Ir} R. W. Irving.
\newblock Generalized Ramsey Numbers for Small Graphs.
\newblock {\em Discrete Mathematics}, 9:251--264, 1974.

\bibitem{Jac} M. S. Jacobson.
\newblock On the Ramsey Number for Stars and a Complete Graph.
\newblock {\em Ars Combinatoria}, 17:167--172, 1984.

%\bibitem{Ka1} J. G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, %{\it Canadian Mathematical Bulletin}, {\bf 8} (1965), 575--584.

\bibitem{Ka2} J. G. Kalbfleisch.
\newblock {\em Chromatic Graphs and Ramsey's Theorem}
\newblock Ph D. thesis, University of Waterloo, 1966.

\bibitem{KM2} K. Klamroth and I. Mengersen.
\newblock The Ramsey Number of $r(K_{1,3},C_4,K_4)$.
\newblock {\em Utilitas Mathematica}, 52:65--81, 1997.

\bibitem{KLR} D. L. Kreher, L. Wei, and S. P. Radziszowski.
\newblock Lower Bounds for Multi-Colored Ramsey Numbers From Group Orbits.
\newblock {\em Journal of Combinatorial Mathematics and Combinatorial Computing}, 4:87--95, 1988.

\bibitem{mat} S. Wolfram.
\newblock Mathematica 8.0, 2010.
\newblock \url{http://www.wolfram.com/mathematica/}

\bibitem{McKay1} B.D. McKay.
\newblock Practical Graph Isomorphism.
\newblock {\em Congressus Numerantium}, 30:45--87, 1981.

\bibitem{McKay2} B.D. McKay.
\newblock Nauty User's Guide (Version 2.4).
\newblock Technical Report TR-CS-90-02, Department of Computer Science, Australian National
University, 1990. \url{http://cs.anu.edu.au/~bdm/nauty}.


%\bibitem{MR4} B. D. McKay and S. P. Radziszowski, $R(4,5)=25$, {\it Journal of %Graph Theory}, {\bf 19} (1995), 309--322. %{http://www.cs.rit.edu/~spr/PUBL/paper32.pdf}.

%\bibitem{MR5} B. D. McKay and S. P. Radziszowski, Subgraph Counting Identities %and Ramsey Numbers, {\it Journal of
%Combinatorial Theory, Series B}, {\bf 69} (1997), 193--209. %{http://www.cs.rit.edu/~spr/PUBL/paper35.pdf}.

%\bibitem{McR} J. McNamara and S. P. Radziszowski, The Ramsey Numbers %$R(K_4$-$e,K_6$-$e)$ and $R(K_4$-$e,K_7$-$e)$, {\it Congressus Numerantium}, %{\bf 81} (1991), 89--96.

\bibitem{Piw2} K. Piwakowski.
\newblock A New Upper Bound for $R_3(K_4$-$e)$.
\newblock {\em Congressus Numerantium}, 128:135--141, 1997.

\bibitem{PR1} K. Piwakowski and S.P. Radziszowski.
\newblock $30\le R(3,3,4)\le 31$.
\newblock {\em Journal of Combinatorial Mathematics and Combinatorial Computing}, 27:135--141, 1998. %{http://www.cs.rit.edu/~spr/PUBL/paper36.pdf}.

\bibitem{Rad} S. P. Radziszowski.
\newblock Small Ramsey numbers.
\newblock {\em The Electronic Journal of Combinatoric}, Dynamic Survey 1:\#13, 2011.
\url{http://www.combinatorics.org/}
%{http://www.combinatorics.org/Surveys/index.html}.

\bibitem{RST} S. P. Radziszowski, J. Stinehour and Kung-Kuen Tse.
\newblock Computation of the Ramsey Number $R(W_5,K_5)$.
\newblock {\em Bulletin of the Institute of Combinatorics and its Applications}, 47:53--57, 2006. %{http://www.cs.rit.edu/~spr/PUBL/paper49.pdf}.

\bibitem{Schu} C. U. Schulte.
\newblock {\em Ramsey-Zahlen f\"ur B\"aume und Kreise}.
\newblock Ph D. thesis, Heinrich-Heine-Universit\"at D\"usseldorf, 1992.

\bibitem{ShWR} D. S. Shetler, M. A. Wurtz, and S.P. Radziszowski.
\newblock On Some Multicolor Ramsey Numbers Involving $K_3+e$ and $K_4-e$.
\newblock To appear in the {\em SIAM Journal on Discrete Mathematics}. %{http://www.cs.rit.edu/~spr/PUBL/reu11.pdf}.

%\bibitem{West} D. West, Introduction to Graph Theory, second edition, Prentice %Hall, 2001.

\bibitem{XSR1} Xiaodong Xu, Zehui Shao, and S. P. Radziszowski.
\newblock Bounds on Some Ramsey Numbers Involving Quadrilateral.
\newblock{\em Ars Combinatoria}, 90:337--344, 2009. %{http://www.cs.rit.edu/~spr/PUBL/paper56.pdf}.

%\bibitem{YH} Yang Yuansheng and G. R. T. Hendry, The Ramsey Number %$r(K_1$+$C_4,K_5$-$e)$, {\it Journal of Graph Theory}, {\bf 19} (1995), 13--15.

%\bibitem{YR} Yang Yuansheng and P. Rowlinson, On Graphs without 6-Cycles and %Related Ramsey Numbers,
%{\it Utilitas Mathematica}, {\bf 44} (1993), 192--196.

\bibitem{YR3} Yang Yuansheng and P. Rowlinson.
\newblock The Third Ramsey Numbers for Graphs with at Most Four Edges.
\newblock {\em Discrete Mathematics}, 125:399--406, 1994.

\end{thebibliography}

\newpage
\pagestyle{empty}
\section{Appendix}

\begin{figure}[ht]
\begin{center}
{\scriptsize
X022122211212\\
0X22221202212\\
22X2111022222\\
222X221220120\\
1212X12021222\\
22121X0122222\\
211120X222112\\
2202012X12021\\
10222221X2211\\
122012222X120\\
2221221021X21\\
11222212122X2\\
\vspace{-0.16cm}
222022211012X
}
\end{center}
\caption{Matrix of $(P_4, C_4, K_4; 13)$-coloring.}
\end{figure}
\begin{figure}[ht!]
\begin{center}
{\scriptsize
X21211112222101200212202112\\
2X2211221110122220022011122\\
12X112222110210202222110200\\
221X22221022101122221021110\\
1112X0220221222111101021202\\
11220X222221012211121222021\\
122222X01102120110201211222\\
1222220X1112022111200211222\\
21210211X221202021202120221\\
211022112X01221222121002212\\
2112220120X1220222111202211\\
20021122111X122222022110122\\
112120102221X12201120222021\\
0210212202221X1122221221010\\
12012202210221X211222112001\\
222112110222212X20210120221\\
0202111122220212X0212122112\\
00221101122212100X212022112\\
202211222110122222X20112122\\
1222020002122221112X1211222\\
22211110211201202201X202120\\
201002221021221110122X21202\\
0112221120012212221102X2212\\
21011211022021202221212X221\\
112120222221000211121222X21\\
1201022221122102112220122X1\\
\vspace{-0.16cm}
22002122121210112222022111X
}
\end{center}
\caption{Matrix of $(C_4, K_4-e, K_4; 27)$-coloring.}
\end{figure}

\end{document}