# An Interpretable Algorithm for Uveal Melanoma Subtyping from Whole Slide
Cytology Images

Haomin Chen  T. Y. Alvin Liu  Catalina Gomez  Zelia Correa  Mathias Unberath

###### Abstract

Algorithmic decision support is rapidly becoming a staple of personalized
medicine, especially for high-stakes recommendations in which access to
certain information can drastically alter the course of treatment, and thus,
patient outcome; a prominent example is radiomics for cancer subtyping.
Because in these scenarios the stakes are high, it is desirable for decision
systems to not only provide recommendations but supply transparent reasoning
in support thereof. For learning-based systems, this can be achieved through
an interpretable design of the inference pipeline. Herein we describe an
automated yet interpretable system for uveal melanoma subtyping with digital
cytology images from fine needle aspiration biopsies. Our method embeds every
automatically segmented cell of a candidate cytology image as a point in a 2D
manifold defined by many representative slides, which enables reasoning about
the cell-level composition of the tissue sample, paving the way for
interpretable subtyping of the biopsy. Finally, a rule-based slide-level
classification algorithm is trained on the partitions of the circularly
distorted 2D manifold. This process results in a simple rule set that is
evaluated automatically but highly transparent for human verification. On our
in house cytology dataset of 88 uveal melanoma patients, the proposed method
achieves an accuracy of $87.5\,\%$ that compares favorably to all competing
approaches, including deep “black box” models. The method comes with a user
interface to facilitate interaction with cell-level content, which may offer
additional insights for pathological assessment.

Machine learning, Digital pathology, Cancer, Oncology, Instance segmentation,
Object Detection, UMAP

WSI short=WSI, long=whole slide image, foreign-plural= FNAC short=FNAC,
long=Cytology of Fine Needle Aspirates, foreign-plural= FNAB short=FNAB,
long=Fine Needle Aspiration Biopsy, foreign-plural= GEP short=GEP, long=Gene
Expression Profile, foreign-plural= UM short=UM, long=Uveal Melanoma, foreign-
plural= ROI short=ROI, long=Region of Interest, foreign-plural= mAP short=mAP,
long=Mean Average Precision, foreign-plural= IoU short=IoU, long=Intersection-
Over-Union, foreign-plural= HCI short=HCI, long=Human Computer Interaction,
foreign-plural= SVM short=SVM, long=Support Vector Machine, foreign-plural=

##  1 Introduction

Figure 1: An overview of the automatic interpretable algorithm for uveal
melanoma subtyping from cytology images. The algorithm consists of cell
instance segmentation to extract cell appearance information that is used to
cluster cells of similar appearance in a circular space. Based on a coarse
partitioning of the embedding space, which we refer to as pie chart, shown in
(a), we find simple rule sets (b) that enable uveal melanoma subtyping, which
otherwise, requires gene analysis. A pie chart of a representative patient is
shown in (c) - the patient is at high metastatic risk (GEP class 2).

UM is the most common primary intraocular malignancy in adults (Singh et al.,
2011). As standard care for UM, FNAB is often performed to confirm the
diagnosis and enable UM prognostication. To this end, a molecular test, GEP,
is performed and microscopic Cytology of Fine Needle Aspirates images are
created from the biopsy. According to a recent study, there exist two subtypes
in UM that can be identified based on its GEP: The first subtype exhibits low
metastatic risk, while the second subtype has been linked to high metastatic
risk. There is a stark contrast in long-term survival between the two classes:
the 92-month survival probability in class 1 patients is 95%, versus 31% in
class 2 patients (Onken et al., 2004). It is evident that access to UM subtype
information is critical for proper management of patients by providing
appropriate recommendation for metastasis surveillance. However, even after 10
years of development, GEP is still only available in the United States. The
technique is also expensive and has a long turn around time. A more accessible
test for UM subtyping is, therefore, highly desirable.

There is increasing evidence that the underlying genetic profile affects
cancer growth on multiple scales. Radiomics, for example, exploits this
observation to develop imaging-derived biomarkers that are informative for
prognosis (Grossmann et al., 2017). In the particular case of UM
prognostication, there is huge potential in using imaging-derived biomarkers
to determine GEP subtype and metastatic risk directly from cytology slides.
While it is impossible even for highly trained pathologists to derive this
information from cytology images, learning-based algorithms that discover
associations between intensity patterns in cytology images and GEP subtype are
promising (Liu et al., 2020; Chen et al., 2020). However, as “black box”
models that perform a super-human task, these algorithms do not offer insights
beyond the final recommendation to the human decision makers, which has been
linked to automation bias and over-trust or dis-trust in such systems (Nourani
et al., 2020; Gaube et al., 2021). A more transparent algorithm design may
enable humans to better calibrate their trust in the recommendation, which
would be an important feat for high-stakes decision making.

Figure 2: System overview of the proposed method. Cell-level features are
obtained by aggregation over instance cell segmentation masks and then
embedded into a 2D space. Several slides are embedded in this way to create a
representative cell appearance space, and the 2D embedding space is
subsequently distorted to a circle. For every other WSI, cells representations
are extracted and projected with the same embedding process into the circular
space, such that one density chart is generated for every slide. Finally, we
find an interpretable rule set to classify UM biopsies based on the density
charts.

In this paper, we develop an automatic system for interpretable UM subtype
classification from cytology images. The method is based on the idea that
biopsy samples of the two UM subtypes should differ in overall cell
composition. Thus, an algorithm that enables high level, rule-based reasoning
on the cell composition of the sample, would be interpretable and could easily
be verified by human users. To create this algorithm, we have developed
automated methods for cell instance segmentation in cytology images from weak
supervision, techniques to aggregate and represent whole slide-level cell
appearance information in an intuitive embedding space, and rule-based
classification algorithms to infer UM subtype from this representation. Figure
1 provides a concise overview of the user-facing side of the method. Because
subtyping now amounts to evaluating simple instructions, the rule-based system
is highly transparent and offers insight into whether a specific sample
“barely” or “strongly” obeys the rules, which may enable calibration of trust
in the system. The present manuscript details the technical developments that
were necessary to devise this system, and our future work will focus on human
factors, including trust and over-reliance issues, in this high-stakes, high-
knowledge imbalance scenario.

##  2 Related work

The high resolution and complexity of WSI make cell-level annotations
difficult or impossible to obtain, which is why many of the annotated datasets
are limited to slide-level labels that correspond to the overall diagnosis.
However, standard automatic cancer subtyping and analysis in WSI is based on
multiple small regions extracted from slides, that then need to be aggregated
to a single prediction on the slide level. These methods include majority
voting, coarse-to-fine techniques (Liu et al., 2017; Hou et al., 2016; Xu et
al., 2017; Zhang et al., 2020), and multiple instance learning approaches
(Chikontwe et al., 2020; Campanella et al., 2019). While most of the deep
learning approaches in WSI analysis consider black box models, recent works
attempt to introduce features that enhance model understanding by mimicking
the decision process of pathologists. For instance, content-based
histopathological image retrieval (Peng et al., 2019; Hegde et al., 2019)
contrasts a query image with a large database to determine the search results
with more similar histological features. Making intelligent systems
interpretable is another frontier in developing trustworthy medical decision
support applications (Rudin, 2019). In contrast to explainable models that
rely on post hoc analysis, interpretable models aim to explain the reasoning
behind a prediction. In a histopathologic context, patch-based regions
visualizations introduced in (Pirovano et al., 2020) display features related
to tumor tissue, in addition to providing slide-level heatmaps that improve
WSI classification. Different from previous methods that attempt to provide
human-meaningful visualizations, either from learned representations or image
retrieval, our method is interpretable by nature.

##  3 Method

Given high-quality ROI extracted from cytology images, we create an
interpretable system to analyze UM biopsy cytology and reveal GEP subtype
based on overall cell composition of the sample. Our learning-based system
comprises of three parts: 1) instance-level cell segmentation, 2) cell feature
embedding, and 3) interpretable classification. We note that the specifics of
each component may easily be replaced by other techniques since aspects
pertaining to the exact method choice are not the main focus of our work. In
the remainder of this chapter, we describe a cost-efficient way of weakly
labeling our dataset to enable supervised learning of the cell segmentation
network (Section 3.2). Cell-level features are then generated and embedded
into a 2D space for further classification as described in Section 3.3.
Finally, we define an interpretable classification model within the 2D space
to distinguish UM GEP classes by cell composition (Section 3.4). The system
overview is shown in Figure 2.

###  3.1 Considerations around interpretability

Before we introduce the technical details of the proposed method, we first
frame our model in the current interpretability definition. As proposed in
(Murdoch et al., 2019), interpretable machine learning is defined to be the
use of machine-learning models for the extraction of relevant knowledge about
domain relationships contained in data. Knowledge is considered to be relevant
if it provides insight for a particular audience into a chosen domain problem.
Our proposed method aims to provide an interpretable model for UM GEP
classification to pathologists, who already possess substantial expertise in
reading cytology slides. Indeed, clinicopathologic features of UM tumors, _e.
g._ epithelioid cell type and aggressiveness of cancer cells, can be readily
estimated from cytology images and have been associated with worse patient
prognosis and a higher incidence of metastatic disease (Worley et al., 2007).
These risk factors are widely used by pathologists, however, their accuracy to
predict metastatic potential has been shown to be limited (Schopper & Correa,
2016). Our interpretability mechanism is motivated by the fact that
clinicopathologic features of UM tumors, e. g., cell appearance, are relevant
knowledge for pathologists to predict UM metastatic risk. Instead of building
interpretable models with the clinicopathologic information manually extracted
by pathologists themselves, our system automatically extracts
clinicopathologic features (cell appearance features) and summarizes the cell
appearance distribution in a 2-dimensional space, which is further classified
by a simple and interpretable rule set. While the algorithm was developed in
close collaboration with ophthalmic oncologists and pathologists, this
manuscript is limited to describing the proposed system and characterizing its
performance and does not empirically demonstrate its interpretability on a
larger user group. Doing so will remain subject of future work.

###  3.2 Instance cell segmentation

There exist no cell annotations for the high-quality ROI that are
automatically extracted from cytology images using the method described in
(Chen et al., 2020). However, instance cell segmentation is essential for
further cell-level analysis. Thus, we prepare annotations on a small sub-set
with minimal manual labor to enable supervised training of an instance
segmentation network. Figure 3 presents the annotation procedure. In detail,
we randomly select 500 ROI from the 131k pool and partially annotate super-
pixels generated by SLIC (Achanta et al., 2010) to reduce the annotation
workload. We group all super-pixels within any annotated cells to generate
instance-level annotations. We trained the instance segmentation network
YOLACT (Bolya et al., 2019) on the annotated ROI, by converting annotated
super-pixels into pixel level annotations. We chose YOLACT because it can be
easily modified to enable training on partially annotated data. Unlike two-
stage segmentation networks, _e. g._ Mask RCNN (He et al., 2017), which first
detects candidate regions to then classify and segment these regions in the
second stage, YOLACT breaks the instance segmentation into two parallel tasks:
(1) generating a dictionary of non-local prototype masks over the entire
image, and (2) predicting a set of linear combination coefficients per
instance. We compute all loss functions, _e. g._ semantic segmentation loss,
only in annotated areas. All ROI are finally tested to extract cells.

Figure 3: The ROI annotation procedure. (a) the extracted high-quality ROI;
(b) the generated super-pixels.; (c) the annotations on super-pixels. Yellow
and blue regions are annotated super-pixels for cancer cells and background,
respectively.

###  3.3 Cell-level feature embedding

Previously, pathologists have attempted to quantify different cell components,
such as nuclear size and nucleolar size, to predict the behavior of tumors.
Our approach is similar to this process as it extracts network feature
representations of cells, which we assume contain information about cell
appearance. Cell-level features $F_{c}$ for cell $c$ are then extracted from
the entire feature map $F$ using the segmentation mask $M_{c}$ with masked
average pooling:

$\displaystyle F_{c}=\text{Avg}(F[M_{c}])\,,$ (1)

where $F$ is the output of the backbone network architecture.

To prepare subtype classification based on cell composition, and improve
classification performance, we embed all cell-level features in 20 GEP class 1
slides to create a 2D embedding space with UMAP (McInnes et al., 2020). All
other slides are then embedded into that space, to represent the respective
cell composition. We expect slides of distinct GEP classes have different cell
composition, and thus distribution in the 2D embedding space. The embedding
space is created using slides of one GEP class only to potentially maximize
the difference of GEP class 1 and class 2 representation in the embedding
space.

Figure 4: (a) The definition of spatial partitioning and density charts in the
distorted 2D embedding space. (b) The density chart of all cells in GEP class
1; (c) Two density chart examples of GEP class 1 slides; (d) The density chart
of all cells in GEP class 2; (e) Two density chart examples of GEP class 2
slides. Examples in (c) and (e) are all correctly predicted samples by using
the rule set defined in Equation 2.

###  3.4 Interpretable Classification

Based on our hypothesis that slide-level cell composition, and thus
distributions in the 2D cell appearance embedding space, should be different
between GEP classes, we devise an interpretable algorithm that reasons based
on these representations. Direct comparisons between distributions, _e. g._
chi-square test (Pearson, 1900) and Kolmogorov-Smirnov tests (Kolmogorov,
1933), are complicated and not usually interpretable. Instead, we partition
the embedding space and analyze the region densities. Because cells with
similar appearance, thus similar features, are close to each other in the
embedding space, the density of each region represents the portion of cells
with a specific kind of cell appearance in the slide. To make it easier to
define the spatial partitioning of the embedding space, we first distort the
space into a unit circle. We treat the center of gravity of all embedded cells
as the origin. Then, we normalize to unity the scale of all embedded cells in
every degree of angle in polar coordinate, so that the whole embedding space
is distorted to a unit circle. Parameters in circular distortion are
determined simultaneously with the embedding generation and are fixed when
embedding new slides. Finally, we divide the unit circle equally into 12
regions, as shown in Figure 4. Since we posit that each GEP class will have
different densities in distinct regions, in addition to the individual
densities of these regions ($D_{i}$), we define the relative densities
($D_{i}/D_{j}$) as input variables for classification. Finally, an
interpretable bayesian rule set algorithm (Wang et al., 2017) takes all these
78 input variables (12 values ($D_{i}$), and 66 relations ($D_{i}/D_{j}$)) for
GEP classification.

Different from logistic regression (which is only interpretable in low
dimensional problem settings because humans can handle at most $7\pm 2$
cognitive entities at once (Miller, 2020; Cowan, 2010)), the rule set
algorithm is not limited by the number of input variables. The number of
arguments in each rule can be controlled, as simple as determining the largest
allowed depth of a tree. In addition, it is different from a random forest
(which uses majority vote, and is thus not interpretable) since here, the
predicted output is determined once the sample obeys at least one rule in the
rule set.

##  4 Experiments

We demonstrate that our proposed interpretable learning pipeline does not
compromise on performance of UM subtyping when compared to deep black box
models. We also demonstrate an additional, interactive tool for expert review
of cell level composition through interaction with the 2D embedding space. By
simply clicking on areas of interest in the density charts, users may retrieve
and visually inspect cells that are representative of the appearance in that
specific embedding location. Details are shown in Figure 5.

###  4.1 Experimental setting

Dataset: The dataset we use includes 100 cytology samples from 88 uveal
melanoma patients. To the best of our knowledge, this is the largest dataset
on UM cytology. The dataset contains 50 slides from 43 patients with GEP class
1 and 50 slides from 45 patients with GEP class 2. The cellular aspirates
obtained from cytology of each tumor were submitted for cytology and GEP
testing. The cytology specimen was flushed on a standard pathology glass
slide, smeared, and stained with hematoxylin and eosin. The specimen submitted
for GEP was flushed into a tube containing extraction buffer and submitted for
DecisionDx-UM testing. Whole slide scanning was performed for each cytology
slide at a magnification of 40x. Automatic ROI extraction is performed using
(Chen et al., 2020), resulting in a total of $131,816$ high-quality ROI across
all slides.

Implementation details:  Super-pixel algorithm SLIC (Achanta et al., 2010) is
implemented following (Kim, ), where the number of components is $400$, and
the Euclidean distance ratio is $1$. On average, each of the 500 randomly
sampled ROI for manual annotation has 9 cells and 38 background super-pixels
annotated. The number of prototypes in YOLACT is doubled to 64 to potentially
segment more cells within every ROI. The segmentation model is optimized using
Adam (Kingma & Ba, 2014) with a learning rate of $10^{-5}$ and 4000 iterations
with a batch size of $1$. We train the model on $450$ annotated ROI and
validate on the other $50$ ROI. We empirically split the circular embedding
space into 12 partitions, as shown in Figure 4, which in internal development
was found to yield the best performance compared to other split approaches.
All cells that map outside the circular embedding space are projected to the
nearest region. For the interpretable classification, we use $80\%$ of the
projected slides in both class 1 and class 2 for training (64) and the other
$20\%$ for testing (16). The rule set algorithm is trained with simulated
annealing procedure as described in (Wang et al., 2017). The maximal length of
each rule in the rule set is set to 2 to preserve its intelligibility.

###  4.2 Cell Segmentation Performance

We use mAP as the main evaluation metric for cell segmentation performance.
The mAP is about $70\%$ when IoU is larger than $50\%$, which indicates that
the segmentation process catches a fairly good number of cancer cells.
However, mAP is low with high IoU threshold, because of the low quality of
super-pixel-based annotations on the cells’ boundary. Table 1 and Figure 6
present both quantitative and qualitative results, respectively. The algorithm
can easily tell apart cancer cells from blood cells, while some cancer cells
with ambiguous boundaries are missed. We attribute this to the low quality of
super-pixels for these cells during annotation. As a result, cells with
ambiguous boundaries are usually skipped in annotation if more clear cells
exist in the same ROI. Because there exist numerous cells in each slide,
missing some cells at random will not significantly impact the overall cell
composition, and further, the classification performance.

Figure 5: The additional tool for embedding space interaction. For every slide
embedding chart, users can click any area of interest, _i. e._ the green/blue
cross location. Several closest cells in the embedding space are visualized in
native and scaled resolution. Figure 6: Examples of segmentation results. The
segmentation network is able to (a) separate cancer cells (purple, large) from
blood cells (red, small); (b) segment cells with all sizes, but (c) misses
some ambiguous cells. The numbers within the boxes correspond to confidence
scores.

###  4.3 UM subtype classification

We compare our proposed method with a previously proposed deep black box model
(Coudray et al., 2018; Liu et al., 2020) evaluated on the same dataset, which
classifies UM subtype directly from ROI. In (Coudray et al., 2018), slide-
level subtype prediction is obtained by simply averaging class predictions for
all corresponding ROI. Both, the black box and our proposed method have the
same backbone network architecture (ResNet-50 (He et al., 2015)) and the same
training and testing split for a fair comparison. We find that the accuracy
performance of our method (87.5%) compares favorably to the black box approach
following (Coudray et al., 2018) (83.3%), and more importantly, is
interpretable based on the following rule set over the density chart
($D_{i}$), and thus, over the cell appearance composition of the whole slide:

$\begin{split}D_{6}/D_{11}>1.5&\text{ AND }D_{1}<0.07\\\ &\text{OR}\\\
D_{7}/D&{}_{12}\leq 0.4\end{split}$ (2)

There only exist $3$ arguments in the rule set, which makes algorithmic
recommendations transparent and verifiable, while enabling users to understand
overall cell composition. This rule set was visually represented already in
Figure 1.

Table 1: mAP for segmentation boxes and masks with different IoU threshold. IoU | $0.5$ | $0.6$ | $0.7$ | $0.8$ | $0.9$
---|---|---|---|---|---
box | $70.67\%$ | $64.41\%$ | $49.20\%$ | $27.52\%$ | $3.24\%$
mask | $69.30\%$ | $64.72\%$ | $53.07\%$ | $33.91\%$ | $2.49\%$
Table 2: Ablation study of interpretable classification with different methods and an ensemble technique. LR refers to logistic regression. Rule Set (class $k$, $k={1,2}$) refers to results using the embedding created from class $k$ slides. | w/o Ensemble | w/ Ensemble
---|---|---
| Accuracy | # of rules | Accuracy | # of rules
LR | $67.50\pm 5.56\%$ | N/A | $75.14\pm 9.00\%$ | N/A
SVM | $83.00\pm 6.37\%$ | N/A | $82.07\pm 8.23\%$ | N/A
ANN | $82.86\pm 8.33\%$ | N/A | $83.71\pm 10.15\%$ | N/A
Rule Set (class 1) | $86.36\pm 10.25\%$ | $2.28\pm 0.57$ | $87.50\pm 9.56\%$ | $2.11\pm 0.37$
Rule Set (class 2) | $81.93\pm 8.02\%$ | $2.06\pm 0.49$ | $84.33\pm 10.68\%$ | $1.96\pm 0.31$

###  4.4 Ablation Study

We conduct an ablation study of the rule-based interpretable classification to
benchmark its performance against other classification methods, _i. e._
logistic regression, SVM and Artificial Neural Network (ANN). We also compare
different embeddings, by creating the initial UMAP embedding space with
either, GEP class 1 or GEP class 2 slides. After the embedding space creation,
only 80 slides remain to train and evaluate the classification models.
Therefore, we also introduce an ensemble method to enrich the input data by
creating synthetic cell compositions. To create a synthetic slide, we randomly
selected $30\%$ cells from one slide and $1\%$ cells from all the other slides
in the same class as all the cells in the synthetic slide. Then, the synthetic
slide will represent the main pattern of one observed slide but also introduce
other variations. We created 100 synthetic slides for each class using this
approach, which is indicated as ”Ensemble” in Table 2. The simple ANN we used
is $\text{fc}(8)+\text{ReLU}+\text{fc}(1)$, where $n$ in $\text{fc}(n)$ means
the number of output channels. To evaluate the methods, we then perform 100
random training/testing splits of our dataset on the patient-level and train
all models on every split. The mean results and the corresponding confidence
intervals are summarized in Table 2.

Logistic regression has the lowest testing accuracy ($75.14\%$) and the rule
set achieves the highest performance ($87.50\%$), which is comparable to SVM
($82.07\%$) and ANN ($83.71\%$). Creating the embedding from distinct GEP
classes results in similar accuracy of the rule set algorithm ($87.50\%$ v.s.
$84.33\%$). As in the previous comparisons to black box models, the rule set
approach has the added benefit of being interpretable. Logistic regression and
SVM models suffer in this regard due to the high dimensionality of the input
representation (78). Dimensionality reduction techniques, _e. g._ principle
component analysis (PCA), exist but are not applicable here because the number
of input variables (78) is larger than the number of training samples (64).
Finally, all models reach higher accuracy with the ensemble except SVM.

Due to the fact that our segmentation model is not perfect, we also evaluate
the rule set model for different segmentation results. During early training,
the segmentation model will first identify the most clear cancer cells, but
along with plenty of false positives. As the optimization progresses, fewer
cancer cells are segmented but much fewer false positives occur. The accuracy
of the rule set algorithm for segmentation results after 2000, 3000 and 4000
training iterations is $77.23\pm 10.98\%$, $84.64\pm 10.46\%$ and $87.50\pm
9.56\%$, which suggests that the algorithm favors the output of a highly
specific cell segmentation algorithm.

##  5 Discussion

Our overall system utilizes the segmentation features to generate the
embedding and classify UM subtypes based on slide-level cell composition. We
assume that cell composition will be different across the two GEP classes,
which will result in different cell density chart representations of slides
from the two subtypes that can then be distinguished using an interpretable
rule-based algorithm. This hypothesis is supported by our experiments. One
aspect of the current approach is that we do not currently interpret the
embedded features themselves, e. g., by classifying cell types, so that
regions in the density chart do not immediately carry semantic information.
This circumstance may limit the interpretability of our tool for non-subject
matter experts, however, we emphasize that the tool is designed with
pathologists as primary user group in mind who possess substantial domain
expertise. While the algorithm does not currently identify specific cell types
during embedding, pathologists are domain experts and will be able to explore
and contextualize cell appearance in different embedding regions using the
graphical user interface (Figure 5). Doing so as part of a training period may
allow pathologists to understand and identify the major cell types in specific
embedding regions, linking pie chart sectors to semantic cell types.
Experience in observing how GEP class 1 and class 2 slides behave in the pie
chart embedding space combined with the above training may further add to the
interpretability of the model. Future work will investigate how this paradigm
compares to other approaches and black box models in building trust and
confidence in the user group.

In the current form, the circular space is evenly partitioned into 12 parts.
However, this partitioning process could be further guided by other semantic
information, _e. g._ clustering of specific cell types. If cell type
annotations are available, the segmentation network could also output cell
types for every extracted cells. We would expect to see clusters of cells
types in the embedding space and the partitioning process could be further
guided by the cell type clusters. However, such information is not available
in our dataset and it is also unclear whether such approach would prove
beneficial.

The boundary defined by the interpretable rule set could also be used as a
criterion for user trust calibration. If a slide maps close to the boundary, a
little variation could change the prediction result. Thus, the prediction of
that slide may be perceived as less reliable. We will investigate in future
work whether proximity to the decision boundary indeed correlates with
prediction performance, and more importantly, other clinical outcome measures
such as survival.

##  6 Conclusion

We have presented an automated yet interpretable system for UM subtyping from
fine needle aspiration cytology images that does not compromise performance
compared to conventional deep black box models. In future work, we will study
how our interpretable model affects treatment decisions and user trust, as a
next step to realize the huge potential of image-based tests for UM subtyping.

Acknowledgement: We gratefully acknowledge funding from the Emerson Collective
Cancer Research Fund and internal funds provided by the Wilmer Eye Institute
and the Malone Center for Engineering in Healthcare at Johns Hopkins
University.

## References

  * Achanta et al. (2010) Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., and Süsstrunk, S.  Slic superpixels, 2010.
  * Bolya et al. (2019) Bolya, D., Zhou, C., Xiao, F., and Lee, Y. J.  Yolact: Real-time instance segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , October 2019.
  * Campanella et al. (2019) Campanella, G., Hanna, M. G., Geneslaw, L., Miraflor, A., Silva, V. W. K., Busam, K. J., Brogi, E., Reuter, V. E., Klimstra, D. S., and Fuchs, T. J.  Clinical-grade computational pathology using weakly supervised deep learning on whole slide images.  _Nature medicine_ , 25(8):1301–1309, 2019.
  * Chen et al. (2020) Chen, H., Liu, T. A., Correa, Z., and Unberath, M.  An interactive approach to region of interest selection in cytologic analysis of uveal melanoma based on unsupervised clustering.  In _International Workshop on Ophthalmic Medical Image Analysis_ , pp. 114–124. Springer, 2020.
  * Chikontwe et al. (2020) Chikontwe, P., Kim, M., Nam, S. J., Go, H., and Park, S. H.  Multiple instance learning with center embeddings for histopathology classification.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , pp. 519–528. Springer, 2020.
  * Coudray et al. (2018) Coudray, N., Ocampo, P. S., Sakellaropoulos, T., Narula, N., Snuderl, M., Fenyö, D., Moreira, A. L., Razavian, N., and Tsirigos, A.  Classification and mutation prediction from non–small cell lung cancer histopathology images using deep learning.  _Nature medicine_ , 24(10):1559–1567, 2018.
  * Cowan (2010) Cowan, N.  The magical mystery four: How is working memory capacity limited, and why?  _Current directions in psychological science_ , 19(1):51–57, 2010.
  * Gaube et al. (2021) Gaube, S., Suresh, H., Raue, M., Merritt, A., Berkowitz, S. J., Lermer, E., Coughlin, J. F., Guttag, J. V., Colak, E., and Ghassemi, M.  Do as ai say: susceptibility in deployment of clinical decision-aids.  _npj Digital Medicine_ , 4(1):1–8, 2021.
  * Grossmann et al. (2017) Grossmann, P., Stringfield, O., El-Hachem, N., Bui, M. M., Velazquez, E. R., Parmar, C., Leijenaar, R. T. H., Haibe-Kains, B., Lambin, P., Gillies, R. J., and Aerts, H. J.  Defining the biological basis of radiomic phenotypes in lung cancer.  In _eLife_ , 2017.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  _arXiv preprint arXiv:1512.03385_ , 2015.
  * He et al. (2017) He, K., Gkioxari, G., Dollár, P., and Girshick, R.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 2961–2969, 2017.
  * Hegde et al. (2019) Hegde, N., Hipp, J. D., Liu, Y., Emmert-Buck, M., Reif, E., Smilkov, D., Terry, M., Cai, C. J., Amin, M. B., Mermel, C. H., et al.  Similar image search for histopathology: Smily.  _NPJ digital medicine_ , 2(1):1–9, 2019.
  * Hou et al. (2016) Hou, L., Samaras, D., Kurc, T. M., Gao, Y., Davis, J. E., and Saltz, J. H.  Patch-based convolutional neural network for whole slide tissue image classification.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 2424–2433, 2016.
  * (14) Kim, A.  Fastslic: Optimized slic superpixel.  URL https://github.com/Algy/fast-slic.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kolmogorov (1933) Kolmogorov, A.  Sulla determinazione empirica di una lgge di distribuzione.  _Inst. Ital. Attuari, Giorn._ , 4:83–91, 1933.
  * Liu et al. (2020) Liu, T. A., Zhu, H., Chen, H., Arevalo, J. F., Hui, F. K., Paul, H. Y., Wei, J., Unberath, M., and Correa, Z. M.  Gene expression profile prediction in uveal melanoma using deep learning: A pilot study for the development of an alternative survival prediction tool.  _Ophthalmology. Retina_ , 4(12):1213–1215, 2020\.
  * Liu et al. (2017) Liu, Y., Gadepalli, K., Norouzi, M., Dahl, G. E., Kohlberger, T., Boyko, A., Venugopalan, S., Timofeev, A., Nelson, P. Q., Corrado, G. S., et al.  Detecting cancer metastases on gigapixel pathology images.  _arXiv preprint arXiv:1703.02442_ , 2017.
  * McInnes et al. (2020) McInnes, L., Healy, J., and Melville, J.  Umap: Uniform manifold approximation and projection for dimension reduction, 2020.
  * Miller (2020) Miller, G. A.  _11\. The magical number seven, plus-or-minus two or some limits on our capacity for processing information_.  University of California Press, 2020.
  * Murdoch et al. (2019) Murdoch, W. J., Singh, C., Kumbier, K., Abbasi-Asl, R., and Yu, B.  Definitions, methods, and applications in interpretable machine learning.  _Proceedings of the National Academy of Sciences_ , 116(44):22071–22080, 2019.  ISSN 0027-8424.  doi: 10.1073/pnas.1900654116.  URL https://www.pnas.org/content/116/44/22071.
  * Nourani et al. (2020) Nourani, M., King, J., and Ragan, E.  The role of domain expertise in user trust and the impact of first impressions with intelligent systems.  In _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ , volume 8, pp. 112–121, 2020.
  * Onken et al. (2004) Onken, M. D., Worley, L. A., Ehlers, J. P., and Harbour, J. W.  Gene expression profiling in uveal melanoma reveals two molecular classes and predicts metastatic death.  _Cancer research_ , 64(20):7205–7209, 2004.
  * Pearson (1900) Pearson, K.  X. on the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 50(302):157–175, 1900.
  * Peng et al. (2019) Peng, T., Boxberg, M., Weichert, W., Navab, N., and Marr, C.  Multi-task learning of a deep k-nearest neighbour network for histopathological image classification and retrieval.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , pp. 676–684. Springer, 2019.
  * Pirovano et al. (2020) Pirovano, A., Heuberger, H., Berlemont, S., Ladjal, S., and Bloch, I.  Improving interpretability for computer-aided diagnosis tools on whole slide imaging with multiple instance learning and gradient-based explanations.  In _Interpretable and Annotation-Efficient Learning for Medical Image Computing_ , pp. 43–53. Springer, 2020.
  * Rudin (2019) Rudin, C.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  _Nature Machine Intelligence_ , 1(5):206–215, 2019.
  * Schopper & Correa (2016) Schopper, V. J. and Correa, Z. M.  Clinical application of genetic testing for posterior uveal melanoma.  _International journal of retina and vitreous_ , 2(1):1–6, 2016.
  * Singh et al. (2011) Singh, A. D., Turell, M. E., and Topham, A. K.  Uveal melanoma: Trends in incidence, treatment, and survival.  _Ophthalmology_ , 118(9):1881 – 1885, 2011.  ISSN 0161-6420.
  * Wang et al. (2017) Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y., Klampfl, E., and MacNeille, P.  A bayesian framework for learning rule sets for interpretable classification.  _The Journal of Machine Learning Research_ , 18(1):2357–2393, 2017.
  * Worley et al. (2007) Worley, L. A., Onken, M. D., Person, E., Robirds, D., Branson, J., Char, D. H., Perry, A., and Harbour, J. W.  Transcriptomic versus chromosomal prognostic markers and clinical outcome in uveal melanoma.  _Clinical Cancer Research_ , 13(5):1466–1471, 2007.
  * Xu et al. (2017) Xu, Y., Jia, Z., Wang, L.-B., Ai, Y., Zhang, F., Lai, M., Eric, I., and Chang, C.  Large scale tissue histopathology image classification, segmentation, and visualization via deep convolutional activation features.  _BMC bioinformatics_ , 18(1):1–17, 2017.
  * Zhang et al. (2020) Zhang, H., Kalirai, H., Acha-Sagredo, A., Yang, X., Zheng, Y., and Coupland, S. E.  Piloting a deep learning model for predicting nuclear bap1 immunohistochemical expression of uveal melanoma from hematoxylin-and-eosin sections.  _Translational Vision Science & Technology_, 9(2):50–50, 2020.


# Star-critical Ramsey numbers for cycles versus the complete graph on 5
vertices

Chula J. Jayawardene
Department of Mathematics
University of Colombo
Sri Lanka
email<EMAIL_ADDRESS>
###### Abstract

Let $G$, $H$ and $K$ represent three graphs without loops or parallel edges
and $n$ represent an integer. Given any red blue coloring of the edges of $G$,
we say that $K\rightarrow(G,H)$, if there exists red copy of $G$ in $K$ or a
blue copy of $H$ in $K$. Let $K_{n}$ represent a complete graph on $n$
vertices, $C_{n}$ a cycle on $n$ vertices and $S_{n}=K_{1,n}$ a star on $n+1$
vertices. The Ramsey number $r(G,H)$ is defined as $\min\\{n\mid
K_{n}\rightarrow(G,H)\\}$. Likewise, the star-critical Ramsey number
$r_{*}(H,G)$ is defined $\min\\{k\mid K_{r(G,H)-1}\sqcup
K_{1,k}\rightarrow(H,G)\\}$. When $n>3$, in this paper we show that
$r_{*}(C_{n},K_{5})=3n-1$ except $r_{*}(C_{4},K_{5})=13$. We also characterize
all Ramsey critical $r(C_{n},K_{5})$ graphs.

Keywords: Ramsey theory, Star-critical Ramsey numbers
Mathematics Subject Classification : 05C55, 05D10, 05C38

##  1 INTRODUCTION

In its classical form, Ramsey’s theorem ensures the existence of the Ramsey
numbers $r(n,m)$ defined as $r(n,m)=r(K_{n},K_{m})$. The exact determination
of these numbers progresses rapidly in difficulty from the nearly trivial
$r(3,3)=6$ to stubbornly resistant $r(5,5)$ [at present known to be between 43
and 48]. One new branches of classical Ramsey numbers namely star -critical
Ramsey numbers were introduced by Hook and Isaak in 2010 (see [5, 6]). Using
the arrow notation, $r_{*}(H,G)$ can be also be defined as the smallest
positive integer $k$ such that $K_{n}\setminus K_{1,n-k-1}\rightarrow(H,G)$
where $n=r(G,H)$ (as $K_{n-1}\sqcup K_{1,k}=K_{n}\setminus K_{1,n-k-1}$).
Obviously, the rational behind finding star critical Ramsey numbers is to get
a more in-dept understanding of classical case. Recently many papers have
tried to find star critical Ramsey numbers for such as fans vs. complete
graphs and cycles versus $K_{4}$ (see [2, 4, 5, 6, 7, 11]).

In this paper we concentrate on finding $r_{*}(C_{n},K_{5})$. Most of the work
related to this paper, originated with the attempt to solve Erdös and Bondy
conjecture which states that $r(C_{n},K_{m})=(n-1)(m-1)+1$ for all $n\geq
m\geq 3$, except when $n=m=3$ (see [1]). However, up to now, the conjecture is
unsolved and has been only proved for $n\geq m$ and $n\leq 7$ and some other
special cases.

##  2 NOTATION

All graphs $G=(V,E)$ considered in this paper are finite graphs without loops
and multiple edges. The order of the graph $G=(V,E)$ is denoted by $|V|$ and
the number of edges in the graph is denoted by $|E|$. For a graph $G=(V,E)$
the degree of $v$ is defined as the cardinality of the set of vertices
adjacent to $v$. A set $I$ of $V(G)$, is said to be an independent set of a
graph $G$ if no pair of vertices of $I$ are connected by an edge in $G$.

Suppose that a graph $G$ contains an $n$ cycle $(u_{1},u_{2},...,u_{n},u_{1})$
and a vertex (say $y_{1}$) outside of the cycle such that $y_{1}$ is adjacent
to exactly two vertices (say $u_{i}$ and $u_{j}$) of the $n$ cycle. In such a
situation, we say that $y_{1}$ is adjacent to two vertices of the
$\\{u_{1},u_{2},...,u_{n}\\}$ which are length $k$ apart where
$k=\min\\{(i-j)\mod n,(j-i)\mod n\\}$. Throughout the paper, in any graph
which is colored by red and blue, we will denote the red edges by a unbroken
line and the blue edges by a broken line. For a red/blue coloring of a graph
$G$, and vertices $u,v\in V(G)$ such that $(u,v)\in E(G)$, we say that $u$ is
a red (resp. blue) neighbor of $v$ if $(v,u)$ is colored red (resp. blue). Any
2-coloring of $K_{r(G,H)-1}$ that does not contain a red $G$ or a blue $H$, is
called a critical coloring.

##  3 PROPERTIES OF $(C_{4},K_{5})$ RAMSEY CRITICAL GRAPHS

In order to prove the main result of this paper, namely finding
$r_{*}(C_{n},K_{5})$, we try to utilize the the critical graphs of
$r(C_{n},K_{4})$ (see [7]) and the fact that $r(C_{n},K_{5})=4n-3$ for $n\geq
4$ (see [3, 10]). In addition, we use the following lemmas to arrive at the
main result.

The following four lemmas is a direct consequence of [8, 9, 7], written by
Jayawardene et al.

###### Lemma 1

([8], Lemma 2). If $G$ is a graph of order $N$ that contains no $C_{m}$ and
the independent number is less than or equal to $n-1$ then the minimal degree
is greater than or equal to $N-r(C_{m},K_{n-1})$.

###### Lemma 2

([9], Lemma 5). Any $C_{5}$-free graph of order 11 with no independent set of
4 vertices is isomorphic to one of the graphs $R_{11,1}$, $...$, $R_{11,18}$
(see Figure 1) or $R_{11,19}\cong 2K_{4}\cup K_{3}$.

$P_{11,1}$$P_{11,2}$$P_{11,3}$$P_{11,4}$$P_{11,5}$$P_{11,6}$$P_{11,7}$$P_{11,8}$$P_{11,9}$$P_{11,10}$$P_{11,11}$$P_{11,12}$$P_{11,13}$$P_{11,14}$$P_{11,15}$$P_{11,16}$$P_{11,17}$$P_{11,18}$

Figure 1. $R_{11,k},\ 1\leq k\leq 18$.

###### Lemma 3

([9], Lemma 4). Any $C_{5}$-free graph of order 12 with no independent set of
4 vertices is isomorphic to one of the graphs $R_{12,1}$, $R_{12,2}$,
$R_{12,3}$, $R_{12,4}$, $R_{12,5}$ (see the following figure) or
$R_{12,6}\cong 3K_{4}$.

$R_{12,1}$$R_{12,2}$$R_{12,3}$$R_{12,5}$$R_{12,4}$$R_{12,5}$

Figure 2. $R_{12,k},\ 1\leq k\leq 5$.

###### Lemma 4

([7], Lemma 7). Any $C_{6}$-free graph of order 15 with no independent set of
4 vertices is isomorphic to one of the graphs five critical graphs
corresponding to $K_{15}$, denoted by $R_{15,1}$, $R_{15,2}$, $R_{15,3}$,
$R_{15,4}$ or $R_{15,5}$, where $R_{15,4}\cong 3K_{5}+e$ and $R_{15,5}\cong
3K_{5}$. The other three red graphs, namely $R_{15,1}$, $R_{15,2}$,
$R_{15,3}$, are illustrated in Figure 3.

$R_{15,1}$$R_{15,2}$$R_{15,3}$

Figure 3. The graphs $R_{15,k},\ 1\leq k\leq 3$.

The following lemmas is a direct consequence of [3], written by Bollabás et
al.

###### Lemma 5

Suppose $G$ contains the cycle $(u_{1},u_{2},...,u_{n-1},u_{1})$ of length
$n-1$ but no cycle of length $n$. Let
$Y=V(G)\setminus\\{u_{1},u_{2},...,u_{n-1}\\}$. Then,

(a) No vertex $x\in Y$ is adjacent to two consecutive vertices on the cycle.

(b) If $x\in Y$ is adjacent to $u_{i}$ and $u_{j}$ then $u_{i+1}u_{j+1}\notin
E(G)$.

(c) If $x\in Y$ is adjacent to $u_{i}$ and $u_{j}$ then no vertex
$x^{\prime}\in Y$ is adjacent to both $u_{i+1}$ and $u_{j+2}$.

(d) Suppose $\alpha(G)=m-1$ where $m\leq\frac{n+3}{2}$ and
$\\{x_{1},x_{2},...,x_{m-1}\\}\subseteq Y$ is an $(m-1)$-element independent
set. Then no member of this set is adjacent to $m-2$ or more vertices on the
cycle.

###### Lemma 6

A $C_{5}$ -free graph of order $16$ with no independent set of 5 vertices
contains a isomorphic copy of $4K_{4}$.

Proof.

Let $G$ be a $C_{5}$-free graph of order 16 with no independence set of 5
vertices. First note that $\delta(G)\geq 3$ by lemma 3 as $r(C_{5},K_{4})=13$.

Remark 1: Suppose that $G$ contains a $K_{4}$, then any vertex outside of
$K_{4}$ can be adjacent to at most one vertex of the $K_{4}$. Further any two
adjacent vertices together can be adjacent to at most one vertex of a $K_{4}$.

Case 1: The minimum degree is 3.

Say $w$ is a vertex of minimum degree. Then
$G[V(G)\setminus\overline{\Gamma(w)}]$ will satisfy the conditions of lemma 3.
Thus, using all possible cases and using remark 1, any two non adjacent
vertices of $G[\Gamma(w)]$ will give rise to an independent set of size five
containing them. Therefore, $G[\Gamma(w)]\cong K_{3}$. This will result in the
required $4K_{4}$.

Case 2: The minimum degree greater than or equal to 4.

Say $w$ is a vertex of minimum degree. Then $G[V(G)\setminus
V[\overline{\Gamma(w)]}]$ will satisfy the conditions of lemma 2. Thus, using
all possible cases and using remark 1 one sees that there are no possible
extensions.

Case 3: The minimum degree greater than or equal to 5.

Say $w$ is a vertex of minimum degree. Then $G[\Gamma(w)]$ will contain a
$C_{3}\cup K_{2}$, $P_{3}\cup K_{2}$, $K_{1,4}$, $K_{1,3}\cup K_{1}$, $2K_{2}$
or at least two isolated vertices. It is worth noting that, we will get
$C_{5}$ or else an independent set of size 5 directly in all cases, other than
when $G[\Gamma(w)]=C_{3}\cup K_{2}$. In this case, let
$H=G[V(G)\setminus\overline{\Gamma(w)}]$. Then, $H$ has 10 vertices. In order
to avoid a $C_{5}$ each these three vertices of the $C_{3}$ in $G[\Gamma(w)]$
will each have to be adjacent to two vertices of $H$ and these neighborhoods
will have to be non overlapping. Select $v_{1}$, $v_{2}$ and $v_{3}$ from the
three neighborhoods. Moreover, in order to avoid a $C_{5}$ the two vertices of
the $K_{2}$ in $G[\Gamma(w)]$ will share a common neighbor in $H$, say $v$, as
illustrated in the following figure.

$v_{1}$$v$$v_{1}$$v_{2}$$v_{3}$$v$$w$$\Gamma(w)$

Figure 4. The only option left in case 3

Then in order to avoid a $C_{5}$, $\\{w,v_{1},v_{2},v_{3},v\\}$ will have to
be an independent set contrary to the assumption.

###### Lemma 7

A $C_{6}$ -free graph of order $20$ with no independent set of 5 vertices
contains a isomorphic copy of $4K_{5}$.

Proof.

Let $G$ be a $C_{5}$-free graph of order 20 with no independence set of 5
vertices. First note that, by lemma 1, $\delta(G)\geq 4$ as
$r(C_{6},K_{4})=16$.

Remark 2: Any vertex can be adjacent to one vertex of a disjoint $K_{5}$.
Further any two adjacent vertices together can be adjacent to at most one
vertex of a $K_{5}$.

Case 1: The minimum degree is 4.

Say $w$ is a vertex of minimum degree. Then
$G[V(G)\setminus\overline{\Gamma(w)}]$ will satisfy the conditions of lemma 4.
Thus, using all possible cases and using remark 2, it follows that any two non
adjacent vertices of $G[\Gamma(w)]$ will give rise to an independent set of
size five containing them. Therefore, $G[\Gamma(w)]\cong K_{4}$. This will
result in the required $4K_{5}$.

Case 2: The minimum degree greater than or equal to 5.

Suppose that $G$ is a $C_{6}$ -free graph on $20$ with no independent set of 5
vertices. Then as $r(C_{5},K_{5})=17$ (see [3, 10]) there exists a cycle
$U=(u_{l},u_{2},...,u_{5},u_{1})$ of length $5$. Let
$X=\\{u_{l},u_{2},...,u_{5}\\}$. Define $H=G[X^{c}]$ as the induced subgraph
of $G$ not containing the vertices of the cycle and $H_{1}=G[X]$. Then,
$|V(H)|=15$ and $|V(H_{1})|=5$.

Suppose that there exists an independent set $Y$ in $H$ of size 4 consisting
of the four vertices $y_{1}$, $y_{2}$, $y_{3}$ and $y_{4}$. In order to avoid
an independent set of size 5, each vertex of $X$ must be adjacent to at least
one vertex of $Y$. Clearly, no vertex of $Y$ can be adjacent to three vertices
of $X$ as two of these three adjacent vertices will have to be consecutive
vertices of the $C_{5}$ (which will result in a $C_{6}$ containing all the
vertices of $X$). Therefore, each vertex of $Y$ is adjacent to at most two
vertices of $X$ and if they are adjacent to two vertices of $X$ they must be
length 2 apart. As $|X|=5$, we get that without loss of generality $y_{1}$
will have exactly two red neighbors in $X$ length 2 apart (say $u_{1}$ and
$u_{3}$). Then without loss of generality $u_{2}$ is adjacent to $y_{2}$ and
in order to avoid a red $C_{6}$, $y_{2}$ cannot be adjacent to any other
vertex of $X$.

Next without loss of generality $\\{y_{3},y_{4}\\}$ will have either two
vertices or one vertex or no vertices that are adjacent to two vertices of
$X$. Furthermore, any vertex of $\\{y_{3},y_{4}\\}$ adjacent to 2 vertices of
$X$ must be adjacent to either $u_{3}$ and $u_{5}$ or $u_{1}$ and $u_{4}$ or
$u_{1}$ and $u_{3}$. Moreover, if $y_{3}$ is adjacent to $u_{3},u_{5}$ and
$y_{4}$ is adjacent to $u_{4},u_{1}$ then
$(u_{1},u_{5},y_{3},u_{3},u_{4},y_{4},u_{1})$ will be a cycle of length $6$,
contrary to our assumption. Also if, $y_{3}$ is adjacent to $u_{1},u_{3}$ we
will get that $y_{4}$ will be forced to be adjacent to $u_{4},u_{5}$ and then
$(u_{1},u_{2},u_{3},u_{4},y_{4},u_{5},u_{1})$ will be a cycle of length $6$,
contrary to our assumption. Therefore, without loss of generality, by
symmetry, we are left with the two possibilities where $y_{3}$ is adjacent to
$u_{5}$ and $y_{4}$ is adjacent to $u_{4}$ or else $y_{3}$ is adjacent to
$u_{3},u_{5}$ and $y_{4}$ is adjacent to $u_{4}$. In the first option, in
order to avoid an independent set of size 5, $u_{1}$ must be adjacent to
$u_{3}$. As $y_{2}$ can not be adjacent to any other vertex of $X$ it must be
adjacent to 4 vertices (as minimum degree of $G$ is greater than 5) outside of
$X\cup Y$ (say $w_{1}$,$w_{2}$,$w_{3}$ and $w_{4}$), as illustrated in the
following figure.

$y_{1}$$y_{2}$$y_{3}$$y_{4}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{1}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$

Figure 5. The first possibility

In order to avoid a independent set of size 5 consisting of
$\\{w_{1},u_{2},y_{1},y_{3},y_{4}\\}$ we get $w_{1}$ must be adjacent to
$u_{2}$. Similarly, we can conclude that all other vertices of
$W=\\{w_{1},w_{2},w_{3},w_{4}\\}$ too have to be adjacent to $u_{2}$. But then
$G[W]=K_{4}$ as otherwise any two non adjacent vertices of $W$ together with
$\\{y_{1},y_{3},y_{4}\\}$ will form an independent set of 5 vertices, contrary
to the assumption. This will give us a $C_{6}$ containing all vertices $W$,
contrary to our assumption.

$y_{1}$$y_{2}$$y_{3}$$y_{4}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{1}$$w$

Figure 6: The second possibility

In the second option, as $u_{5}$ can not be adjacent to $u_{2}$ (may be
adjacent to $u_{3}$), it will have to be adjacent to some other vertex (since
the minimum degree of $G$ is greater than 5) outside of $X\cup Y$ (say $w$),
as illustrated in the above figure. But then, $w$ can not be adjacent to any
vertex of $Y$ as any such occurrence will lead to some $C_{6}$. Therefore,
$Y\cup\\{w\\}$ will be an independent set of size 5, contrary to our
assumption.

Thus, we can conclude that the initial assumption is false. That is, there is
no independent set of order 4 in $H$. By Lemma 4, we can conclude that $H$ is
equal to one of the five graphs $R_{15,1}$, $R_{15,2}$, $R_{15,3}$, $R_{15,4}$
or $R_{15,5}$. Now consider any two vertices of $U$, say $u$ and $v$, and
suppose that $\left\\{u,v\right\\}\not\in E(G)$. Since there is no $C_{6}$ in
$G$, each of the vertices $u$ and $v$ must be adjacent to at most one vertex
of each copy of $K_{5}$ in $H$. Therefore, we can select vertex $x_{1}$ in the
first $K_{5}$, vertex $x_{2}$ in the second $K_{5}$ and vertex $x_{3}$ in the
third $K_{5}$ such that $x_{1}$, $x_{2}$ and $x_{3}$ are independent and not
adjacent to $u$ or $v$. This gives us that $\\{u,v,x_{1},x_{2},x_{3}\\}$ is an
independent set of order 5, a contradiction. Therefore,
$\left\\{u,v\right\\}\in E(G)$. Since $u,v$ are arbitrary vertices in $U$, we
can conclude that $X$ induces a $K_{5}$ as required. $\square$

###### Lemma 8

A $C_{n}$ -free graph (where $n\geq 7$) of order $4(n-1)$ with no independent
set of 5 vertices contains a isomorphic copy of $4K_{n-1}$.

Proof.

Suppose that $G$ is a $C_{n}$ -free graph on $4(n-1)$ with no independent set
of 5 vertices. Then as $r(C_{n-1},K_{5})=4n-7$ (see [3, 10]) there exists a
cycle $(u_{l},u_{2},...,u_{n-1},u_{1})$ of length $n-1$. Let
$X=\\{u_{l},u_{2},...,u_{n-1}\\}$. Define $H=G[X^{c}]$ as the induced subgraph
of $G$ not containing the vertices of the cycle and $H_{1}=G[X]$. Then,
$|V(H)|=3(n-1)$ and $|V(H_{1})|=n-1$.

Suppose that there exists an independent set $Y$ in $H$ of size 4 consisting
of the four vertices $y_{1}$, $y_{2}$, $y_{3}$ and $y_{4}$. That is,
$\alpha(G)=4$. From lemma 5(d) (as $5\leq\frac{n+3}{2}$), it follows that
every vertex $y$ is adjacent to at most two vertex of the cycle $C_{n-1}$.

Case 1: $n\geq 10$

Then as $n-1>8$, we will get a independent set of size 5, containing $Y$; a
contradiction.

Case 2: $n=9$

In order to avoid an independent set of size 5, each vertex of $X$ must be
adjacent to at least one vertex of $Y$. Therefore as $|X|=8$, we get that each
$y_{i}$ ($1\leq i\leq 4$) will have exactly two disjoint neighbors in $X$ and
without loss of generality then we have the following subcases. In the first
subcase, we assume that without loss of generality $Y$ has a vertex which is
adjacent to two vertices of $X$ which are length 2 apart in the $C_{8}$. In
the second subcase we assume that without loss of generality $Y$ has a vertex
which is adjacent to two vertices of $X$ which are length 3 apart in the
$C_{8}$. In the third subcase we assume that without loss of generality all
vertices of $Y$ are adjacent to two vertices of $X$ which are length 4 apart
in the $C_{8}$.

Subcase 2.1: $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 2 apart in the $C_{8}$.

Without loss of generality assume that $y_{1}$ is adjacent in to $u_{1}$ and
$u_{3}$ and $y_{2}$ is adjacent in to $u_{2}$. In order to avoid an
independent set of size 5 consisting of $\\{u_{1},u_{3},y_{2},y_{3},y_{4}\\}$,
we get that $(u_{1},u_{3})$ is an edge. Without loss of generality, then
$y_{2}$ is adjacent to one vertex of $\\{u_{8},u_{7},u_{6}\\}$. In the first
possibility, as $(u_{2},u_{8})$ must be an edge and therefore we will get a
cycle $(u_{3},...,u_{8},y_{2},u_{2},u_{1},u_{3})$ of length $9$, contrary to
the assumption. In the next possibility, as $(u_{2},u_{7})$ must be an edge
and therefore we will get a cycle
$(u_{3},u_{4},u_{5},u_{6},u_{7},y_{2},u_{2},u_{1},y_{1},u_{3})$ of length $9$,
contrary to the assumption. In the last possibility without loss of generality
gives rise to two scenarios as illustrated in the following two figures.

$u_{1}$$u_{4}$$v_{1,3}$$u_{2}$$u_{3}$$v_{2,3}$$v_{2,1}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$

Figure 7. The first scenario

In the first scenario, without loss of generality, $y_{3}$ is adjacent to
$u_{5}$ and $u_{7}$ and $y_{4}$ is adjacent to $u_{4}$ and $u_{8}$. Moreover,
$(u_{2},u_{6})$, $(u_{4},u_{8})$ and $(u_{5},u_{7})$ must be edges. Thus, we
get a cycle $(u_{2},u_{1},y_{1},u_{3},u_{4},u_{8},u_{7},u_{5},u_{6},u_{2})$ of
length $9$, contrary to the assumption.

In the second scenario, without loss of generality, $y_{3}$ is adjacent to
$u_{5}$ and $u_{8}$ and $y_{4}$ is adjacent to $u_{4}$ and $u_{7}$. Moreover,
$(u_{2},u_{6})$, $(u_{5},u_{8})$ and $(u_{4},u_{7})$ must be edges. Thus, we
get a cycle $(u_{1},y_{1},u_{3},u_{4},u_{7},u_{8},u_{5},u_{6},u_{2},u_{1})$ of
length $9$, contrary to the assumption.

$u_{1}$$u_{4}$$v_{1,3}$$u_{2}$$u_{3}$$v_{2,3}$$v_{2,1}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$

Figure 8. The second scenario

Subcase 2.2:  $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 3 apart in the $C_{8}$

Without loss of generality assume that $y_{1}$ is adjacent to $u_{1}$ and
$u_{4}$ and $y_{2}$ is adjacent to $u_{3}$. In order to avoid an independent
set of size 5 consisting of $\\{u_{1},u_{4},y_{2},y_{3},y_{4}\\}$, we get that
$(u_{1},u_{4})$ is an edge. Without loss of generality, then $y_{2}$ must be
adjacent to one vertex of $\\{u_{2},u_{7},u_{8},u_{6}\\}$.

The first possibility, is impossible as we get a cycle
$(u_{1},u_{2},y_{2},u_{3},...,u_{8},u_{1})$ of length $9$, contrary to the
assumption. In the second possibility we get a cycle
$(u_{7},y_{2},u_{3},u_{2},u_{1},$ $y_{1},u_{4},u_{5},u_{6},u_{7})$ of length
$9$, contrary to the assumption. In the third possibility we get a cycle
$(u_{5},u_{4},u_{1},u_{2},u_{3},y_{2},u_{8},u_{7},u_{6},u_{5})$ of length $9$,
contrary to the assumption. In the fourth possibility is without loss of
generality $y_{3}$ is adjacent to $u_{2}$. But then the only options for
$y_{3}$ to be adjacent to is to two vertices of $\\{u_{5},u_{8},u_{7}\\}$.
However, if $y_{3}$ is adjacent to $u_{2}$ and $u_{5}$ it leads to
$(u_{1},u_{4},u_{3},u_{2},y_{3},u_{5},u_{6},u_{7},u_{8},u_{1})$, a cycle of
length 9 and if $y_{3}$ is adjacent in red to $u_{2}$ and $u_{8}$ it leads to
$(u_{8},y_{3},u_{2},u_{1},u_{4},u_{3},y_{2},u_{6},u_{7},u_{8})$ a cycle of
length 9, contrary to the assumption. Therefore, we are left with the scenario
when $y_{3}$ is adjacent to $u_{2}$ and $u_{7}$. But then in order to avoid an
independent set of size 5, we get that $(u_{2},u_{7})$ and $(u_{3},u_{6})$ are
edges. This is illustrated in the following figure.

$u_{1}$$u_{4}$$v_{1,3}$$u_{2}$$u_{3}$$v_{2,3}$$v_{2,1}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$

Figure 9. The only remaining scenario

However, even in this scenario too we get a cycle
$(u_{1},u_{8},u_{7},u_{2},u_{3},u_{6},u_{5},u_{4},y_{1},u_{1})$ of length $9$,
contrary to the assumption.

Subcase 2.3: All vertices of $Y$ are adjacent to two vertices of $X$ which are
length 4 apart in the $C_{8}$

Without loss of generality assume that $y_{1}$ is adjacent in to $u_{1}$ and
$u_{5}$ and $y_{2}$ is adjacent to $u_{2}$ and $u_{6}$ and $y_{3}$ is adjacent
to $u_{4}$ and $u_{8}$

In order to avoid an independent set of size 5, we get that $(u_{1},u_{5})$,
$(u_{2},u_{6})$ and $(u_{4},u_{8})$ are edges. But then we get cycle
$(u_{3},u_{4},u_{8},u_{7},u_{6},u_{5},y_{1},u_{1},u_{2},u_{3})$ of length $9$,
contrary to the assumption.

Case 3: $n=8$

In order to avoid an independent set of size 5, each vertex of $X$ must be
adjacent to at least one vertex of $Y$. Therefore as $|X|=7$, we get that
without loss of generality each $y_{i}$ ($1\leq i\leq 2$) will have exactly
two disjoint neighbors in $X$ such that $\Gamma_{R}(x)\cap\Gamma_{R}(x)\cap
X=\emptyset$ for all $x\in\\{y_{1},y_{2}\\}$ and $y\in\\{y_{3},y_{4}\\}$. This
will give rise to the following subcases. In the first subcase, we assume that
without loss of generality $\\{y_{1},y_{2}\\}$ has a vertex which is adjacent
to two vertices of $X$ which are length 2 apart in the $C_{7}$. In the second
subcase we assume that without loss of generality both $\\{y_{1},y_{2}\\}$ are
adjacent to two vertices of $X$ which are length 3 apart in the $C_{7}$.

Subcase 3.1: $\\{y_{1},y_{2}\\}$ has a vertex which is adjacent to two
vertices of $X$ which are length 2 apart in the $C_{7}$.

Without loss of generality assume that $y_{1}$ is adjacent to $u_{1}$ and
$u_{3}$. Moreover, $y_{2}$ is adjacent to $u_{2}$ and $u_{4}$ or $y_{2}$ is
adjacent to $u_{2}$ and $u_{5}$ or else $y_{2}$ is adjacent to $u_{4}$ and
$u_{6}$. In order to avoid an independent set of size 5 consisting of
$\\{u_{1},u_{3},y_{2},y_{3},y_{4}\\}$, we get that $(u_{1},u_{3})$ is a edge.
In the first possibility we will get a cycle
$(u_{1},u_{3},u_{2},y_{2},u_{4},u_{5},u_{6},u_{7},$ $u_{1})$ of length $8$,
contrary to the assumption. In the second possibility, we will get a cycle
$(u_{1},y_{1},u_{3},u_{2},y_{2},u_{5},u_{6},u_{7},u_{1})$ of length $8$,
contrary to the assumption. Therefore, we may assume the only remaining option
that $y_{2}$ is adjacent to $u_{4}$ and $u_{6}$. In order to avoid an
independent set of size 5 consisting of $\\{u_{1},u_{3},y_{2},y_{3},y_{4}\\}$,
we get that $(u_{4},u_{6})$ is a edge. Since without loss of generality,
$y_{3}$ is adjacent to two vertices distinct from
$\\{u_{1},u_{3},u_{4},u_{6}\\}$, we get three possibilities given by $y_{3}$
is adjacent to $u_{2}$ and $u_{5}$ or $y_{3}$ is adjacent to $u_{2}$ and
$u_{7}$ or else $y_{3}$ is adjacent to $u_{5}$ and $u_{7}$. This will give a
cycles $(u_{1},u_{3},u_{2},y_{3},u_{5},u_{4},u_{6},u_{7},u_{1})$,
$(u_{4},u_{3},u_{1},u_{2},y_{3},u_{7},u_{6},u_{5},u_{4})$,
$(u_{1},u_{2},u_{3},u_{4},u_{6},u_{5},y_{3},u_{7},u_{1})$ respectively in the
three cases, contrary to the assumption.

Subcase 3.2: Both $\\{y_{1},y_{2}\\}$ are adjacent to two vertices of $X$
which are length 3 apart in the $C_{7}$.

Without loss of generality assume that $y_{1}$ is adjacent to $u_{1}$ and
$u_{4}$. By symmetry, we may assume that without loss of generality $y_{2}$ is
adjacent to $u_{2}$ and $u_{5}$ or $u_{2}$ and $u_{6}$. In order to avoid an
independent set of size 5 consisting of $\\{u_{1},u_{4},y_{2},y_{3},y_{4}\\}$,
we get that $(u_{1},u_{4})$ is an edge. In the first possibility, $y_{2}$ is
adjacent to $u_{2}$ and $u_{5}$. However, in order to avoid an independent set
of size 5, $(u_{2},u_{5})$ is an edge and thus we will get a cycle
$(u_{1},u_{4},u_{3},u_{2},y_{2},u_{5},u_{6},u_{7},u_{1})$ of length $8$,
contrary to the assumption. In the second possibility, $y_{2}$ is adjacent to
$u_{2}$ and $u_{6}$. In order to avoid an independent set of size 5 consisting
of $\\{u_{2},u_{6},y_{1},y_{3},y_{4}\\}$, we get that $(u_{2},u_{6})$ is a
edge. This scenario is illustrated in the following figure 10.

$v_{1,3}$$v_{2,3}$$v_{2,1}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$$u_{4}$$u_{3}$$u_{5}$$u_{2}$$u_{4}$$u_{6}$$u_{1}$$u_{7}$

Figure 10. The only remaining scenario of Subcase 3.2

Thus we will get a cycle
$(u_{1},y_{1},u_{4},u_{3},u_{2},y_{2},u_{6},u_{7},u_{1})$ of length $8$,
contrary to the assumption.

Case 4: $n=7$

In order to avoid an independent set of size 5, each vertex of $X$ must be
adjacent to at least one vertex of $Y$. Note that in order to avoid a $C_{7}$,
no vertex of $Y$ can be adjacent to two vertices of $X$ which are length 1
apart in the $C_{6}$. Thus, we assume that without loss of generality there
are two main subcases generated by when $Y$ has a vertex which is adjacent to
two vertices of $X$ which are length 2 or 3 apart in the $C_{6}$ and no other
vertex of $Y$ is adjacent to these two neighbors (subcase 4.1) and when such a
situation doesn’t exist (subcase 4.2).

Subcase 4.1: $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 2 or 3 apart in the $C_{6}$ and no other vertex of $Y$ is adjacent
inv to these two neighbors

Subcase 4.1.1: $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 2 apart in the $C_{6}$ and no other vertex of $Y$ is adjacent to
these two neighbors

As $Y$ has a vertex which is adjacent to two vertices of $X$ which are length
2 apart in the $C_{6}$, without loss of generality, assume that $y_{1}$ is
adjacent to $u_{1}$ and $u_{3}$ and no other vertex of $Y$ is adjacent to
$u_{1}$ and $u_{3}$. Then, either $y_{2}$ is adjacent to $u_{2}$ and $u_{4}$
or $y_{2}$ is adjacent to $u_{2}$ and $u_{5}$ or else $y_{2}$ is adjacent to
$u_{4}$ and $u_{6}$ . In order to avoid an independent set of size 5
consisting of $\\{u_{1},u_{3},y_{2},y_{3},y_{4}\\}$, we get that
$(u_{1},u_{3})$ is an edge. In the first possibility, we will get a cycle
$(u_{1},u_{3},u_{2},y_{2},u_{4},u_{5},u_{6},u_{1})$ of length $7$, contrary to
the assumption. In the second possibility we get a cycle
$(u_{1},y_{1},u_{3},u_{2},y_{2},u_{5},u_{6},u_{1})$ of length $7$, contrary to
the assumption. In the last option, we get that $y_{2}$ is adjacent to $u_{4}$
and $u_{6}$. Next note that, $y_{3}$ can not be adjacent to both $u_{2}$ and
$u_{5}$ as then we will get a cycle
$(u_{1},y_{1},u_{3},u_{2},y_{2},u_{5},u_{6},u_{1})$ of length $7$, contrary to
the assumption. Similarly, $y_{4}$ can not be adjacent to both $u_{2}$ and
$u_{5}$. Therefore, without loss of generality (excluding the posibilities we
have already discused in case 4.1.1), we get that $y_{3}$ is adjacent to
$u_{5}$ and $y_{4}$ is adjacent to $u_{2}$. Moreover, one can observe that in
order to avoid a $C_{7}$ and the cases already discussed in case 4.1.1 both
$y_{3}$ and $y_{4}$ can not be adjacent to no more vertices of $X$. In order
to avoid an independent set of size 5, we get that $(u_{4},u_{6})$ is an edge.
Also in the induced subgraph of $X$, in order to avoid a $C_{7}$, the only
other possible edge is either $(u_{1},u_{4})$ or $(u_{3},u_{6})$, but not
both. Therefore, in the graph of $G[X\cup Y]$ illustrated in the following
figure 11. Without loss of generality $(u_{3},u_{6})$ is marked as a broken
edge to indicate that it is a possible edge (see figure 5) and its worth
noting that $\\{y_{1},y_{2},u_{2},u_{5}\\}$ forms an independent set of size
4.

$v_{1,3}$$v_{2,3}$$v_{2,1}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$$u_{4}$$u_{3}$$u_{5}$$u_{2}$$u_{4}$$u_{6}$$u_{1}$

Figure 11. The structure of the graph induced by $G[X\cup Y]$

The graph $G$ is an order 24 graph with no $C_{7}$ and no independent set of
size 5. Therefore, by applying lemma 1, we get that the degree of each of the
vertices of $G$ is greater than or equal to 5. Therefore, $u_{4}$ has to be
adjacent to some vertex outside $X\cup Y$ (say $w$). In order to avoid an
independent set of size 5 consisting of $\\{w,y_{1},y_{2},u_{2},u_{5}\\}$, we
get that $w$ must be adjacent to one of the vertices of
$\\{y_{1},y_{2},u_{2},u_{5}\\}$. This will give a $C_{7}$ containing $w$,
contrary to the assumption.

Subcase 4.1.2: $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 3 apart in the $C_{6}$ and no other vertex of $Y$ is adjacent to
these two neighbors

Without loss of generality, assume that $y_{1}$ is adjacent to $u_{1}$ and
$u_{4}$ and no other vertex of $Y$ is adjacent $u_{1}$ and $u_{4}$. In order
to avoid an independent set of size 5, we get that $(u_{1},u_{4})$ is an edge.
Hence, one of the vertices in $\\{y_{2},y_{3},y_{4}\\}$ (say $y_{2}$), must be
adjacent to either $u_{2}$ and $u_{5}$ or $u_{2}$ and $u_{6}$ or $u_{3}$ and
$u_{5}$ or else $u_{3}$ and $u_{6}$. However, if $y_{2}$ is adjacent to
$u_{2}$ and $u_{5}$ (see figure 12), we will get a cycle
$(u_{1},u_{4},u_{3},u_{2},y_{2},u_{5},u_{6},u_{1})$ of length $7$, contrary to
the assumption. Similarly, if $y_{2}$ is adjacent to $u_{2}$ and $u_{6}$ , we
will get a cycle $(u_{4},y_{1},u_{1},u_{6},y_{2},u_{2},u_{3},u_{4})$ and if
$y_{2}$ is adjacent to $u_{3}$ and $u_{5}$, we will get a cycle
$(u_{1},y_{1},u_{4},u_{3},y_{2},u_{5},u_{6},u_{1})$ and if $y_{2}$ is adjacent
to $u_{3}$ and $u_{6}$, we will get a cycle
$(u_{1},u_{4},u_{5},u_{6},y_{2},u_{3},u_{2},u_{1})$, contrary to the
assumption.

$v_{1,3}$$v_{2,3}$$v_{2,1}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$$u_{4}$$u_{3}$$u_{5}$$u_{2}$$u_{4}$$u_{6}$$u_{1}$

Figure 12. In subcase 4.2 when $y_{2}$ is adjacent to $u_{2}$ and $u_{5}$

Subcase 4.2: $Y$ has a vertex which is adjacent to two vertices of $X$ which
are length 2 or 3 apart in the $C_{6}$ and some other vertex of $Y$ is
adjacent in to at least one of these two neighbors

Without loss of generality, assume that $y_{1}$ is adjacent to $u_{1}$ and $w$
length 2 or 3 apart. If one other vertex in $Y$ is adjacent to only one vertex
$\\{u_{1},w\\}$ or both vertices of $\\{u_{1},w\\}$ and not adjacent to any
other vertex in $X$ outside $\\{u_{1},w\\}$ it would lead to one of the
previous two subcases. Therefore, without loss of generality we may assume
that, $y_{1}$ is adjacent to $u_{1}$ and $u_{3}$ and $y_{2}$ is adjacent to
$u_{1}$ and $u_{4}$ or else $y_{1}$ is adjacent to $u_{1}$ and $u_{3}$ and
$y_{2}$ is adjacent to $u_{1}$ and $u_{5}$. In the first possibility, in order
to avoid the previous subcases, without loss of generality the only option
left is for $y_{3}$ to be adjacent to $u_{2}$ and $u_{5}$ or $y_{3}$ is
adjacent to $u_{2}$ and $u_{6}$. If $y_{3}$ to be adjacent to $u_{2}$ and
$u_{5}$, we get a cycle $(u_{1},u_{6},u_{5},y_{3},u_{2},u_{3},y_{1},u_{1})$ of
length $7$ and if $y_{3}$ to be adjacent to $u_{2}$ and $u_{6}$, we get a
cycle $(u_{4},y_{2},u_{1},u_{6},y_{3},u_{2},u_{3},u_{4})$ of length $7$,
contrary to the assumption. In the second possibility, in order to avoid a
$C_{7}$, we get $\\{u_{2},u_{4},u_{6}\\}$ will induce an independent set of
size 3. But then $\\{y_{1},y_{2},u_{2},u_{4},u_{6}\\}$ will induce an
independent set of size 5 contrary to the assumption.

Now continuing with the proof of the lemma for all four cases we may assume
that $H$ is a $C_{n}$ -free graph of order $3(n-1)$ with no independent set of
size 4. By [7], we can deduce that $H$ is equal to $3K_{3n-3,1}$,
$3K_{3n-3,2}$, …,$2K_{3n-3,6}$, as $n\geq 5$. In any case $H$ contains a copy
of a $3K_{n-1}$. Now consider any two vertices of $V(C_{n-1})$ say $u$ and
$v$. Since there is no $C_{n}$ in $G$, each of the vertices $u$ and $v$ must
be adjacent to at most one vertex each of the three copies of $K_{4}$ in $H$.
Also there can be at most two edges connecting a given $K_{n-1}$ in the copy
of the $3K_{n-1}$ to the remaining $2K_{n-1}$ subgraphs. Therefore, as $n>5$,
we can select three vertices $x_{1}$, $x_{2}$ and $x_{3}$ in first $K_{n-1}$,
second $K_{n-1}$ and third $K_{n-1}$ respectively, such that $x_{1}$, $x_{2}$
and $x_{3}$ and are not adjacent to $u$ or $v$. As
$\\{u,v,x_{1},x_{2},x_{3}\\}$ cannot be an independent set of size 5, this
will force $(u,v)\in E(G)$. Therefore, $V(C_{n})$ will induce a $K_{n-1}$,
since $u,v$ are arbitrary elements of $V(C_{n})$. Hence the lemma.

##  4 MAIN RESULT

###### Theorem 1

If $n\geq 4$, then

$r_{*}(C_{n},K_{5})=\begin{cases}$ $13&\text{if }n=4,\\\ \hskip 20.0pt&\\\ $
$3n-1&\text{if }n\geq 5.\\\ \end{cases}$

Proof. We break up the proof into two cases.

Case $n=4$

Let $R_{13}$ (see Figure 13) represent the unique Ramsey critical
$(C_{4},K_{5})$ graph (cf.[8]).

$x$$y_{1}$$y_{2}$$y_{3}$

Figure 13. The unique $r(C_{4},K_{5})$ \- critical graph $R_{13}$

Let $R_{13}^{*}$ represent the graph of order 14, obtained from $R_{13}$ by
adding a vertex $y$ and connecting it to the vertices $y_{1},y_{2},y_{3}$.
Color the edges of $K_{13}\sqcup K_{1,12}\cong K_{14}-e$, using red and blue
such that the red graph is isomorphic to $R_{13}^{*}$. Then the blue graph
will be is isomorphic to the complement of the graph $R_{13}^{*}$ in
$K_{14}-e$ where $e=(x,y)$.

$x$$y$$y_{1}$$y_{2}$$y_{3}$

Figure 14. A graph isomorphic to the red coloring of $K_{14}-e$ which contains
no $C_{4}$ and which contains no $K_{5}$ in the complement with respect to
$K_{14}-e$. Notice the missing edge between the nodes labeled $y$ and $x$ is
represented by $e$.

Case $n\geq 5$

Color the graph $K_{4(n-1)+1}\setminus K_{n-2}$ using red and blue colors,
such that the red graph consists of a $3K_{n-1}\cup(K_{n-1}\sqcup K_{1,1})$ as
illustrated in the following figure.

$x_{1},x_{2},x_{3},$ $...$ $,x_{n-1}$$x_{n},...$$x_{2n-1},...$red degree 1blue
degree$3(n-1)$$K_{n-1}$$K_{n-1}$$K_{n-1}$redredred$K_{n-1}$red$x_{3n-2},...,x_{4(n-1)}$

Figure 15. A coloring of $K_{4(n-1)+1}-K_{n-2}$ which contains no red $C_{n}$
and no blue $K_{5}$

Therefore, $r_{*}(C_{n},K_{5})\geq 3n-1$. Next to show that,
$r_{*}(C_{n},K_{5})\leq 3n-1$, consider any red/blue coloring of a graph
$G=K_{4(n-1)+1}\setminus K_{n-2}$ contains no red $C_{n}$ and no blue $K_{5}$.
Let $H$ be the graph obtained by deleting the vertex of degree $3n-1$ (say
$v$) from $G$.

Then $H$ is a graph on $4(n-1)$ vertices such that it contains no red $C_{n}$
or a blue $K_{4}$. Therefore, by lemma 6, lemma 7 and lemma 8 we get that $H$
with a red $4K_{n-1}$. Let us denote the sets of vertices of the four
connected components by $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$ respectively.
Since there is no red $C_{n}$ in the coloring, $v$ has at most one red
neighbor in each of the four sets $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$.

Case 1: $v$ is adjacent to at exactly three vertices of some $V_{i}$ ($1\leq
i\leq 4$).

Without loss of generality, we may assume that $v$ is adjacent to all the
vertices of $V_{1}$, $V_{2}$ and $V_{3}$. That is, $v$ is adjacent to at least
5 vertices of each $V_{i}$ ($1\leq i\leq 3$). Select $v_{1}\in V_{1}$,
$v_{2}\in V_{2}$ and $v_{3}\in V_{3}$ such that $v_{1}$ has no red neighbors
in $G[V_{2}\cup V_{3}\cup V_{4}\cup\\{v\\}]$, $v_{2}$ has no red neighbors in
$G[V_{1}\cup V_{3}\cup V_{4}\cup\\{v\\}]$ and $v_{3}$ has no red neighbors in
$G[V_{1}\cup V_{2}\cup V_{4}\cup\\{v\\}]$ (this is possible because each
$V_{i}$ can have at most 4 vertices with red neighbors outside $V_{i}$).
Because there are no red $C_{n}$ ’s in the coloring, we can find a $v_{4}\in
V_{4}$ such that $\\{v,v_{4}\\}$ is colored blue. Then,
$\\{v,v_{1},v_{2},v_{3},v_{4}\\}$ will induce a blue $K_{5}$, a contradiction.

Case 2: $v$ is adjacent to exactly two vertices of some $V_{i}$ (say $V_{4}$).

Without loss of generality, we may assume that $v$ is adjacent to all the
vertices of $V_{1}$, $V_{2}$ and all but one vertex of $V_{3}$. That is, $v$
is adjacent to at least 5 vertices of each $V_{i}$ ($1\leq i\leq 2$) and at
least 4 vertices of $V_{3}$. Since there are at least two vertices of $V_{4}$
adjacent to $v$ in blue, select $v_{4}\in V_{4}$ such that $v_{3}$ has no red
neighbors in $G[V_{3}\cup\\{v\\}]$. Next select any vertex $v_{3}\in V_{3}$
such that $(v_{3},v)$ is colored blue. Then, $\\{v,v_{3},v_{4}\\}$ will induce
a blue $K_{3}$. Finally select $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$ such that
$v_{1}$ has no red neighbors in $G[V_{2}\cup V_{3}\cup V_{4}\cup\\{v\\}]$ and
$v_{2}$ has no red neighbors in $G[V_{1}\cup V_{3}\cup V_{4}\cup\\{v\\}]$
(this is possible because each $V_{i}$ can have at most 4 vertices with red
neighbors outside $V_{i}$). Then, $\\{v,v_{1},v_{2},v_{3},v_{4}\\}$ will
induce a blue $K_{5}$, a contradiction.

Case 3: Both case 1 and 2, do not hold.

Without loss of generality, we may assume that $v$ is adjacent to at least 5
vertices of each $V_{1}$ and at least 4 vertices of ($2\leq i\leq 4$). Since
there are at least three vertices of $V_{4}$ adjacent to $v$ in blue, select
$v_{4}\in V_{4}$ such that $v_{4}$ has no red neighbors in $G[V_{2}\cup
V_{3}\cup\\{v\\}]$. Next select $v_{2}\in V_{2}$ and $v_{3}\in V_{3}$ such
that $(v_{2},v)$, $(v_{3},v)$ $(v_{2},v_{3})$ are colored blue. Then,
$\\{v,v_{2},v_{3},v_{4}\\}$ will induce a blue $K_{4}$. Finally select
$v_{1}\in V_{1}$ such that $v_{1}$ has no red neighbors in $G[V_{2}\cup
V_{3}\cup V_{4}\cup\\{v\\}]$ (this is possible because each $V_{i}$ can have
at most 4 vertices with red neighbors outside $V_{i}$). Then,
$\\{v,v_{1},v_{2},v_{3},v_{4}\\}$ will induce a blue $K_{5}$, a contradiction.

Hence $r_{*}(C_{n},K_{4})\leq 3n-1$. Therefore, $r_{*}(C_{n},K_{4})=3n-1$.

##  5 ALL RAMSEY $(C_{n},K_{5})$ CRITICAL GRAPHS WHEN $n\geq 4$

The thirty graphs $R_{4n-4,1}$, $...$ ,$R_{4n-4,30}$ are illustrated in the
following figure.

$R_{4n-4,3}$$R_{4n-4,4}$$R_{4n-4,5}$$R_{4n-2,6}$$R_{4n-2,7}$$R_{4n-2,8}$$R_{4n-4,9}$$R_{4n-4,10}$$R_{4n-4,11}$$R_{4n-4,13}$$R_{4n-4,12}$$R_{4n-4,14}$$R_{4n-4,15}$$R_{4n-4,16}$$R_{4n-4,17}$$R_{4n-4,18}$$R_{4n-4,19}$$R_{4n-4,20}$$R_{4n-4,21}$$R_{4n-4,22}$$R_{4n-4,23}$$R_{4n-4,24}$$R_{4n-4,25}$$R_{4n-4,26}$$R_{4n-4,27}$$R_{4n-4,28}$$R_{4n-4,29}$$R_{4n-4,30}$

Figure 16. The red graphs $R_{4n-4,1}$, $R_{4n-4,2}$, $...$ ,$R_{4n-4,30}$
when $n\geq 6$

###### Lemma 9

When $n>3$, all $r(C_{n},K_{5})$ critical graphs will be generated by one of
the following.

(a) One critical generated when $n=4$, with the red graph, of the red/blue
coloring, corresponding to $R_{13}$ (see Figure 13).

(b) Thirty critical graph generated when $n=5$, with the red graph, of the
red/blue coloring, corresponding to $R_{16,1}$, $R_{16,2}$, $...$ ,$R_{16,30}$
(Figure 15).

(c) Nineteen critical graph generated when $n=6$, with the red graph, of the
red/blue coloring, corresponding to $R_{20,1}$, $R_{20,2}$, $...$ ,$R_{20,19}$
(Figure 15).

(d) Eighteen critical graph generated when $n=7$, with the red graph, of the
red/blue coloring, corresponding to $R_{24,1}$, $R_{24,2}$, $...$ ,$R_{24,18}$
(Figure 15).

(e) Seventeen critical graph generated when $n\geq 8$, with the red graph, of
the red/blue coloring, corresponding to $R_{4n-4,1}$, $R_{4n-4,2}$, $...$
,$n_{4n-4,16}$ or $R_{4n-4,17}$ (Figure 15).

Proof. (a) When $n=4$ the result follows from ([8], Lemma 11) and the fact
$r(C_{4},K_{5})=14$ (cf. [8]).

(b)-(e) When $n\geq 8$, for critical $r(C_{n},K_{5})$ the red graph of the
red/blue coloring corresponding to $K_{4(n-1)}$, must contain a $4K_{n-1}$ (by
Lemma 8). Note that in order to avoid a $C_{n}$ there can be at most one red
edge between any two of the red $K_{n-1}$ graphs. We see that these graphs are
generated by the 6 connected subgraphs on 4 vertices ($R_{4n-4,k}$ for
$k\in\\{5,10,11,12,16,17\\}$), 5 disconnected subgraphs on 5 vertices
($R_{4n-4,k}$ for $k\in\\{1,2,3,8,9\\}$), 5 possible spliting of vertices of
trees ($R_{4n-4,k}$ for $k\in\\{4,6,7,13,14\\}$), and one possible splitting
of vertices of a $K_{1,3}+e$ ($R_{4n-4,15}$). Thus, we see that there are only
17 distinct colorings and the corresponding red graphs are given by
$R_{4n-4,k}$ for $1\leq k\leq 17$. Next, note that $R_{24,18}$ is the only
possible $C_{7}$-free graph which contains a $C_{8}$ and has independence
number less than 5. It is generated by splitting of 4 distinct vertices of the
$C_{4}$ ($R_{24,18}$). Thus, for $n=7$ there are only 18 distinct colorings
and the corresponding red graphs are given by $R_{24,k}$ for $1\leq k\leq 18$.
Next, note that $R_{20,19}$ is the only possible $C_{6}$-free graph which
contains a $C_{7}$ and has independence number less than 5. It is generated by
splitting of 3 distinct vertices of the $C_{4}$ ($R_{20,19}$). Thus, we see
that for $n=6$ there are only 19 distinct colorings and the corresponding red
graphs are given by $R_{20,k}$ for $1\leq k\leq 19$. Finally, note that
$R_{16,k}$ for $20\leq k\leq 30$ are the only possible $C_{5}$-free graphs
which contains a $C_{6}$ and has independence number less than 5 (each one of
them is generated by appropriate vertex splittings of subgraphs containing a 3
or 4 cycle). Thus, we see that for $n=5$ there are 30 distinct colorings and
the corresponding red graphs are given by $R_{16,k}$ for $1\leq k\leq 30$.

## References

  * [1] J. A. Bondy and P. Erdös, Ramsey number for cycles in graphs, Journal of Combinatorial Theory Series B, 14, (1973), 46-54.
  * [2] E.T. Baskoro, H. Surahmat and H.J. Broersma, The Ramsey numbers of fans versus $K_{4}$, Bulletin of the Institute of Combinatorial Applications, 43 (2005), 96-102.
  * [3] B. Bollabás, C. J. Jayawardene, Yang Jian Sheng, Huang Yi Ru, C. C. Rousseau and Zhang Ke Min, On a conjecture involving cycle-complete graph Ramsey numbers, The Australasian Journal, 22, (2000), 63-71.
  * [4] S. Haghi, H.R. Maimani and A. Seify, Star-critical Ramsey number of $F_{n}$ vs $K_{4}$, Discrete Applied Mathematics, 217: P2, (2017), 203-209.
  * [5] J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Thesis, Lehigh University, (2010).
  * [6] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Applied Mathematics, 159, (2011), 328-334.
  * [7] C.J. Jayawardene, D. Narvaez and S.P. Radziszowski, The star-critical Ramsey Number for any Cycle vs. a $K_{4}$, Discussiones Mathematicae Graph theory to appear.
  * [8] C. J. Jayawardene and C. C. Rousseau , The Ramsey number for quadrilateral vs. a complete graph on six vertices, Congressus Numerantium, 123, (1997), 97-108.
  * [9] C.J. Jayawardene and C.C. Rousseau, The Ramsey Number for a Cycle of Length Five vs. a Complete Graph of Order Six, Journal of Graph Theory, 35 (2000) 99–108.
  * [10] S.P. Radziszowski, Small Ramsey numbers, Electronic Journal of Combinatorics 14, (2014), DS1.
  * [11] Wu Yali, Sun Yongqi and S.P. Radziszowski, Wheel and star-critical Ramsey numbers for quadrilaterals Discrete Applied Mathematics, 185, (2015) 260-271.