# Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square Two-
tower model, HNSW, Sign Cauchy Projections

Ping Li, Weijie Zhao, Chao Wang, Qi Xia, Alice Wu, Lijun Peng  LinkedIn Ads
{pinli, weijzhao, cowang, qixia, aiwu<EMAIL_ADDRESS>
###### Abstract.

111This work was initially presented in Microsoft Research in Feb 2023.

Sparse data are common. The traditional “handcrafted” features are often
sparse. Embedding vectors from trained models can also be very sparse, for
example, embeddings trained via the “ReLu” activation function. In this paper,
we report our exploration of efficient search in sparse data with graph-based
ANN algorithms (e.g., HNSW, or SONG which is the GPU version of HNSW), which
are popular in industrial practice, e.g., search and ads (advertising).

We experiment with the proprietary ads targeting application, as well as
benchmark public datasets. For ads targeting, we train embeddings with the
standard “cosine two-tower” model and we also develop the “chi-square two-
tower” model. Both models produce (highly) sparse embeddings when they are
integrated with the “ReLu” activation function. In EBR (embedding-based
retrieval) applications, after we the embeddings are trained, the next crucial
task is the approximate near neighbor (ANN) search for serving. While there
are many ANN algorithms we can choose from, in this study, we focus on the
graph-based ANN algorithm (e.g., HNSW-type).

Sparse embeddings should help improve the efficiency of EBR. One benefit is
the reduced memory cost for the embeddings. The other obvious benefit is the
reduced computational time for evaluating similarities, because, for graph-
based ANN algorithms such as HNSW, computing similarities is often the
dominating cost. In addition to the effort on leveraging data sparsity for
storage and computation, we also integrate “sign cauchy random projections”
(SignCRP) to hash vectors to bits, to further reduce the memory cost and speed
up the ANN search. In NIPS’13, SignCRP was proposed to hash the chi-square
similarity, which is a well-adopted nonlinear kernel in NLP and computer
vision. Therefore, the chi-square two-tower model, SignCRP, and HNSW are now
tightly integrated.

chi-square similarity, two-tower model, sparse data, graph-based approximate
near neighbor search, sign cauchy random projections

††copyright: rightsretained

##  1\. Introduction

Embedding has become the standard component in deep learning. Embedding models
including BERT (Devlin et al., 2019), GLOVE (Pennington et al., 2014), GPT-3
(Brown et al., 2020) etc. have been widely adopted in practice in NLP,
knowledge graphs, computer vision, information retrieval, etc. (Karpathy et
al., 2014; Yu et al., 2018; Huang et al., 2019; Chang et al., 2020; Giorgi et
al., 2021; Yu et al., 2022; Spillo et al., 2022; Lanchantin et al., 2021;
Neelakantan et al., 2022). The two-tower model (Huang et al., 2013) has become
the standard neural architecture for generating embeddings which can be
subsequently used for retrievals and other downstream applications. The two-
tower model is the foundation for the “embedding-based retrieval” (EBR), which
has been broadly adopted in the (search and advertising) industry, for
example, for efficiently generating quality candidates as input to (e.g.,) the
subsequent advertisements (ads) ranking algorithm (Fan et al., 2019) or video
recommendation algorithm (Covington et al., 2016).

Figure 1. Left: the cosine two-tower model. Right: the chi-square two-tower
model (which requires to use ReLU).

Figure 1 (left panel) provides a simplified illustration of the two-tower
model. The top-layer of two-tower model computes the inner product of the two
embeddings (which are typically normalized to have the unit $l_{2}$ norm) of
the two towers. After the model has been trained, the embeddings can be
directly used for matching: given a query embedding, searching for the item
embeddings with the highest cosine similarity to the query embedding. In
recent years, graph-based ANN methods such as HNSW (Malkov and Yashunin, 2020)
or SONG (Zhao et al., 2020), which is the GPU version of HNSW, are often
adopted to speed up the search process.

The cosine similarity between two $d$-dimensional embeddings (vectors)
$u,v\in\mathbb{R}^{d}$ is defined as

(1) $\displaystyle\rho=\sum_{i=1}^{d}u_{i}v_{i},\hskip
14.45377pt\sum_{i=1}^{d}u_{i}^{2}=\sum_{i=1}^{d}v_{i}^{2}=1,$

if we assume the vectors are pre-normalized to have the unit $l_{2}$ norm. In
this study, we propose the “chi-square two-tower” model which only slightly
modifies the common “cosine two-tower” model, by replacing the inner product
with the following chi-square similarity:

(2)
$\displaystyle\rho_{\chi^{2}}=\sum_{i=1}^{d}\frac{2u_{i}v_{i}}{u_{i}+v_{i}},\hskip
14.45377ptu_{i}\geq 0,\hskip 7.22743ptv_{i}\geq 0,\hskip
7.22743pt\sum_{i=1}^{d}u_{i}=\sum_{i=1}^{d}v_{i}=1$

As shown in the right panel of Figure 1, in combination with the “ReLU”
activation function (Fukushima, 1975; Nair and Hinton, 2010; Glorot et al.,
2011), the embedding vectors are naturally non-negative. The sum-to-one
constraint is easy to be enforced in the neural network training process. In
fact, the sum-to-one constraint is the same as the $l_{1}$ (lasso) constraint
in non-negative data (Tibshirani, 1996). When we use the ReLU activation, we
observe that both the cosine two-tower model and the chi-square two-tower
model produce sparse embeddings, as expected (Fukushima, 1975; Nair and
Hinton, 2010; Glorot et al., 2011). We are aware of other existing works which
aim to produce sparse embeddings (Trifonov et al., 2018; Liang et al., 2021).

There are notable advantages with sparse embeddings. The storage cost can be
substantially reduced if the embeddings are highly sparse. For example, if the
sparsity (i.e., the number of nonzero entries divided by the vector length) is
$<10\sim 20\%$, we can expect a considerable saving in storage using a sparse
format. Also, we expect the cost for similarity computations can be
substantially reduced if the embeddings are highly sparse. We will illustrate
these advantages via extensive experiments on HNSW for fast approximate near
neighbor search. After the graph is built, the major cost of HNSW is spent on
computing similarities on the fly while walking on the graph to search for
nodes with highest similarities.

The chi-square similarity (2), as a nonlinear kernel, is popular in NLP and
computer vision (Chapelle et al., 1999; Hein and Bousquet, 2005; Jiang et al.,
2007; Wang et al., 2009; Alexe et al., 2010; Vempati et al., 2010; Vedaldi and
Zisserman, 2012). Typically those applications used the “chi-square distance”
$d_{\chi^{2}}$ instead of $\rho_{\chi^{2}}$:

$\displaystyle d_{\chi^{2}}=$
$\displaystyle\sum_{i=1}^{d}\frac{(u_{i}-v_{i})^{2}}{u_{i}+v_{i}}=\sum_{i=1}^{d}\frac{(u_{i}+v_{i})^{2}-4u_{i}v_{i}}{u_{i}+v_{i}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{d}u_{i}+\sum_{i=1}^{d}v_{i}-2\sum_{i=1}^{d}\frac{2u_{i}v_{i}}{u_{i}+v+i}=2-2\rho_{\chi^{2}}$

since $\sum_{i=1}^{d}u_{i}=\sum_{i=1}^{d}v_{i}=1$. In this study, it is not
our major focus to demonstrate the advantage of the chi-square over the
cosine. In the experiments, we will show that the chi-square two-tower model
produces even more sparse embeddings than the cosine two-tower model, and the
chi-square similarity achieves similar (in some cases even better) accuracy
(recall, classification error, etc). We apply the chi-square two-tower model
for a proprietary ads targeting task, and we also conduct HNSW experiments on
public datasets.

To conclude this introduction section, we shall point out the well-known
limitation of the standard two-tower model. This model does not sufficiently
consider interactions between queries and items. The rising field of “neural
ranking” is a promising direction (Zhu et al., 2018, 2019; Tan et al., 2020;
Zhuo et al., 2020; Gao et al., 2020; Tan et al., 2021b; Yu et al., 2022; Zhao
et al., 2022b), which however does not have the convenience of the two-tower
model, because neural ranking models cannot directly use the popular ANN
algorithms. In the industry practice, the two-tower model is still very
popular especially as a retrieval model, and practitioners should be aware of
the limitations.

Next, we review HNSW and the graph-based ANN search.

##  2\. Graph-based ANN Search

Graph index. Graph-based ANN search constructs a proximity graph as index,
where a vertex in the graph corresponds to an item embedding and an edge
connects two “neighboring vertices”. The neighborhood relationship is defined
on various constraints to make the graph index applicable for the ANN problem.
For instance, graph constraints like Delaunay Graphs (Aurenhammer, 1991)
ensure that there exists a path with monotonic increasing similarity to the
query embedding from any starting vertex. NSW (Malkov et al., 2014), NSG (Fu
et al., 2019), HNSW (Malkov and Yashunin, 2020) and SONG (Zhao et al., 2020)
(which is the GPU version of HNSW) approximate the Delaunay Graph to reduce
the proximity graph construction complexity to subquadratic time. The graph
construction is realized by inserting vertices iteratively, i.e., finding the
nearest neighbors using the graph searching methods on the current graph and
connecting the new vertex with them. Recently, there have been a wide range of
research activities based on HNSW, for example, efficiently
maintaining/updating the graphs (Xu et al., 2022), integrating constraints
(such as geo-filtering or other filtering mechanisms) with ANN search (Zhao et
al., 2022a), using HNSW for the maximum inner product search (MIPS) (Morozov
and Babenko, 2018; Zhou et al., 2019; Tan et al., 2021a), etc.

1: Initialize a priority queue $q$; $\textit{res}\leftarrow\emptyset$

2:
$q.\textit{insert}(\textit{start\\_vertex},\textit{similarity}(\textit{start\\_vertex},\textit{query}))$

3: while true do

4: $\textit{curr\\_idx, curr\\_similarity}\leftarrow
q.\textit{pop\\_highest\\_similarity}()$

5: if curr_similarity cannot improve the $L^{\textit{th}}$ similarity in res
then

6: break

7: end if

8:
$\textit{res}\leftarrow\textit{res}\cup\\{(curr\\_idx,curr\\_similarity)\\}$

9: for each  neighbor $x$ of curr do

10: if x is not visited then

11: $q.\textit{insert}(x,\textit{similarity}(x,\textit{query}))$

12: end if

13: end for

14: end while

15: return res

Algorithm 1 Graph Searching Algorithm

Graph searching. Once a graph is (partially) constructed, ANN search can be
performed by traversing the graph. At each step, the algorithm chooses the
neighbor that is closest to the query point and continues the search in that
direction. This process is repeated until a stopping criterion is met, i.e.,
no neighbors can improve the current found $L$ nearest neighbors, where $L$ is
a parameter that controls the trade-off between searching time. The larger $L$
generates more accurate nearest neighbors but consumes more time. The graph
searching is similar to an A* heuristic search (Hart et al., 1968), where the
priority is the similarity to the query embedding. The details of the
searching is illustrated in Algorithm 1. A priority queue $q$ is initialized
from the similarity of the starting vertex (e.g., vertex $1$) and the query.
Then, in each iteration, we extract the vertex curr_idx from the priority
queue with the highest similarity, check the stopping criterion, and explore
its unvisited neighbors.

Figure 2. Illustration of the graph searching algorithm. When $L=2$, the
searching follows the white arrows and stops by returning vertices $2$ and $3$
and results; when $L=3$, the searching continues (following with the hatched
arrows) and eventually returns $2$, $5$, and $3$. If our goal is to find top-2
neighbors of the query vector, it might not be sufficient to use $L=2$ (it
misses the true neighbor $5$). A greater $L$ helps to return more accurate
results.

Figure 2 depicts an example. Consider a query vector at the space of the
dotted circle. We start the search from vertex $1$. With $L=2$, the searching
stops after exploring vertex $3$ because vertex $4$ cannot improve the
currently found top-$2$ results ($2$ and $3$). However, the true top-2 result
of the query should be $2$ and $5$. Using a greater $L$, e.g., $L=3$, will let
the search continue and successfully locate $5$. Therefore, the $L$ should be
chosen properly and should be tuned with the data.

##  3\. EBR for Ads Targeting

We illustrate the effectiveness of the chi-square two-tower model using an
example from ads targeting, for which we learn member and campaign embeddings
from a two-tower model trained on ads engagement tasks, and then use it to
retrieve matching campaigns for members based on relevance (similarity) scores
computed from those embeddings. For the training, we use various features -
member demographics features (e.g., geo location, degree, title), user
behavioral features, contextual features and campaign features. All input
features first go through a shared embedding layer, where numerical,
categorical, textual and id features are mapped to a dense embedding vector.
We then explore the effectiveness of different similarity measures in the two-
tower model training in terms of top-K ranking metrics and retrieval
efficiency. The model was trained with 4.5 billion records from data collected
on a social network.

Figure 3. The neural architecture for using the chi-square two-tower model for
ads targeting.

Figure 3 illustrates the neural architecture for training the embeddings. It
is a simple model and we believe the simplicity allows us to clearly
demonstrate the effectiveness of using the chi-square similarity to replace
the standard cosine similarity inside the model. Basically, the normalization
layer in Figure 3 enforces the sum-to-one constraint. The (top) matching layer
applies the usual cross-entropy loss with the standard bias and temperature
terms. For the comparison, we use essentially the same architecture to train
the cosine two-tower model by replacing the chi-square similarity with cosine
and the sum-to-one normalization with the $l_{2}$ normalization.

,

Figure 4. Average sparsity values of the embeddings. In this paper, “sparsity”
is defined as the fraction of non-zero entries, i.e., the number of non-zero
entries divided by the embedding dimension.

Figure 4 visualizes the (average) sparsity values for embedding sizes varying
from $k=128$ to $k=2048$. As the cosine two-tower model also uses the ReLU
activation function, we can see that the model is also quite sparse especially
for large embedding size $d$. Nevertheless, the embeddings from the chi-square
two-tower model are substantially more sparse. For example, at $d=1024$, the
sparsity for the cosine two-tower model is about $5.4\%$, and for the chi-
square two-tower model is about $2.8\%$. In fact, when $d=2048$, the sparsity
values are $3.6\%$ and $0.6\%$ respectively for the cosine and the chi-square
model. It would be interesting to understand the limit of sparsity by keeping
increasing $d$, but we have not conducted such an investigation for $d>2048$.
The AUC evaluations are pretty close for both models. For smaller $d$, the AUC
scores increase with increasing $d$, and we do not observe improvement after
$d\geq 512$.

After the two-tower models have been trained, we compute the campaign and
member embeddings. Then we use member embeddings to search for the most
similar campaign embeddings, using the popular graph-based (HNSW) ANN
algorithm. Figure 5 reports the top-1 and top-10 recalls for $d=256$ and
$d=1024$. Recall that in HNSW the critical parameter is $L$, which controls
the trade-off between the search quality and the search time. We observe from
the experiments that for both models, the number of retrieved data points at
the same $L$ is very close (also see Figure 7). We thus use $L$ as a
convenient measure for comparisons (at the same $L$).

Figure 5. Recalls at different $L$ values. Recall in Section 2, the searching
stops when the current searching vertices cannot improve current found $L$
nearest neighbors.

Figure 5 confirms the high-quality of HNSW in that it does not need to search
many points (i.e., small $L$ values) in order to achieve a reasonable recall
say 0.9. Another interesting observation is that using larger embeddings can
be actually faster for this application. For example, with $d=1024$, we just
need $L=5$ to achieve a top-1 recall of 0.9, while we need $L=30$ to achieve
0.9 if $d=256$.

We should mention that, with our chi-square model, the number of nonzeros at
$d=256$ is actually more than the number of nonzeros at $d=1024$ (i.e., 41
versus 29). This set of experiments suggests that it might be better to use
larger and sparser embeddings instead of shorter embeddings, as far as the
search quality/efficiency is concerned. We will also report similar results on
public data.

Figure 6. Ratios of distance computing times for the chi-square two-tower
model: time for using dense format over the time for using sparse format.

Figure 6 reports the saving in time by using sparse data format in the
implementation of HNSW. Typically, in EBR applications, embedding vectors are
stored with dense representations. With our chi-square two-tower model, as the
sparsity is merely $2.8\%$ at $d=1024$, we obtain a huge saving in memory
using sparse format. Figure 6 shows that we achieve a 3-fold reduction in time
for computing similarities by using the sparse format when $d=1024$.

##  4\. Experiments on Public Data

To further understand the difference between chi-square and cosine
similarities in the context of approximate near neighbor search, we conduct
HNSW experiments on four public datasets. The dataset specifications are shown
in Table 1.

Table 1. Summary statistics of four public datasets. dataset | # queries | # vectors | # dim | # nonzero | Sparsity
---|---|---|---|---|---
Webspam | 5,000 | 345,000 | 16.6M | 3,720 | $0.02\%$
News20 | 3,993 | 15,935 | 62,061 | 79.9 | $0.13\%$
RCV1 | 15,564 | 518,571 | 47,236 | 64.6 | $0.14\%$
MNIST | 10,000 | 60,000 | 784 | 149.9 | $19.12\%$

Figure 7. The number of retrieved data vectors with respect to the HNSW
parameter $L$.

For all four datasets, we conduct ANN experiments separately for two different
ground-truths: the cosine similarity and the chi-square similarity. Figure 7
reports the number of retrieved vectors with respect to the parameter $L$ in
HNSW. We can see that the numbers are essentially proportional to $L$ and do
not differ much between chi-square and cosine. Figure 7 confirms that it is
appropriate to use $L$ for measuring/comparing the performance of HNSW
experiments.

Figure 8. For Webspam, $>90\%$ of the search time in HNSW is spent on
computing similarities. For MNIST and News20, computing similarities counts
for $40\%\sim 50\%$ of the search time. For News20, if we use the dense
format, then computing similarities would take more than $95\%$ of the total
time.

Figure 9. Recalls for retrieving top-10 similar vectors, for all four
datasets, and for both cosine and chi-square similarities, with respect to the
HNSW parameter $L$.

Figure 8 reports the proportions of the times for computing similarities
within the total search times. For Webspam, as the average number of nonzeros
is high, $>90\%$ of the search time is spent on computing similarities. For
News20, the average number of nonzeros is small and only $40\%$ of the search
time is spent on computing similarities. If we use dense format for News20,
then $>95\%$ of the search time would be spent on computing similarities.

Figure 9 presents the top-10 recalls for all four datasets with respect to
$L$, for both the cosine and the chi-square similarities. Figure 10 reports
the classification accuracy based using 10-NN (10 nearest neighbors) from the
retrieved vectors. These results confirm that the chi-square similarity can be
a good similarity measure to use for machine learning as well as retrieval.

Figure 10. Classification accuracy using the retrieved top-10 similar vectors
(i.e., 10-NN), with respect to the HNSW parameter $L$. The chi-square performs
better on these datasets.

##  5\. Sign Cauchy Random Projections

Before concluding the paper, we also report a solution for potentially further
reducing the memory consumption of EBR in particular for the chi-square
similarity. For example, for Webspam, even though the vectors are highly
sparse, the absolute number of nonzeros is still high (3720). We propose to
use “sign cauchy random projections” (Li et al., 2013) to reduce each vector
to $k$ bits. Specifically, let $x_{j}=\sum_{i=1}^{d}u_{i}r_{ij}$ and
$y_{j}=\sum_{i=1}^{d}v_{i}r_{ij}$, $j=1$ to $k$, where $\\{r_{ij}\\}$ is a
random matrix with entries $r_{ij}$ sampled i.i.d. from the standard cauchy
distribution. It was shown in (Li et al., 2013) that the collision probability
$P(sign(x_{j})=sign(y_{j}))$ is proportional to the chi-square similarity.
This is the foundation of “sign cauchy random projections”.

Figure 11. Ratios of similarity computing times: original chi-square over $k$
sign cauchy projections.

Figure 11 reports the experiments on Webspam, which has 3720 nonzeros per
vector. With $k=1024$ sign cauchy projections for estimating the original chi-
square in HNSW, we only need 1024/32 = 32 (4-byte) integers. To achieve the
same 0.9 recall (respectively 0.9 classification accuracy), HNSW with the
original data would need 12x (respectively 18x) more time for computing
similarities. In addition, note that having greater $k$ yields better time for
the same recall level. The reason is that a greater $k$ better approximates
the original chi-square. Although it takes a slightly longer time to compute
the hamming distance for greater $k$, a smaller $L$ is required to obtain the
same recall, which still saves the entire searching cost.

##  6\. Conclusion

The core contribution of this study is the integration of several techniques
including the chi-square two-tower model, sign cauchy random projections
(SignCRP), graph-based approximate near neighbor (ANN) search, and HNSW. These
techniques are needed in part because the search data are often very sparse.
We demonstrate these aspects through an industrial application in ads
targeting.

For many search applications, the data can be from the traditional
“handcrafted” features, and data can also be generated from the trained deep
learning models via (e.g.,) the two-tower models. In addition to the standard
“cosine two-tower” model, in this study we also develop the “chi-square two-
tower” model. Both models produce sparse embeddings when the “ReLU” activation
function is used. The chi-square similarity or chi-square loss function were
very popular in the “pre-deep-learning era”, for histogram-based features
common in NLP and computer vision applications. It is a good exploration to
bring the chi-square similarity to deep learning.

Approximate near neighbor (ANN) search is a critical component in modern
recommender systems. Among many ANN algorithms, the graph-based methods such
as HNSW or SONG (which is a GPU version of HNSW) become increasingly popular
owing to the excellent performance. We focus on HNSW in this study. After the
graph has been built, the major computational cost of HNSW is the evaluation
of distance/similarity on the fly. Typically the HNSW implementations assume
dense data. Our study provides two solutions. The first (and obvious) solution
is to use sparse representations for the storage as well as similarity
computations.

The second (and less obvious) solution is to apply “sign cauchy random
projections” (SignCRP) to produce highly compact bits representations of the
data and then leverage extremely efficient bit-wise operations to estimate the
chi-square similarity (which is proportional to the number of matched bits).
This strategy has been implemented and well-integrated into HNSW (and SONG).
Experiments have confirmed the effectiveness of the proposed methods.

## References

  * (1)
  * Alexe et al. (2010) Bogdan Alexe, Thomas Deselaers, and Vittorio Ferrari. 2010\.  What is an object?. In _Proceedings of the Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. San Francisco, CA, 73–80.
  * Aurenhammer (1991) Franz Aurenhammer. 1991\.  Voronoi diagrams—a survey of a fundamental geometric data structure.  _ACM Computing Surveys (CSUR)_ 23, 3 (1991), 345–405.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners. In _Advances in Neural Information Processing Systems (NeurIPS)_. virtual, 1877–1901.
  * Chang et al. (2020) Wei-Cheng Chang, Felix X. Yu, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. 2020\.  Pre-training Tasks for Embedding-based Large-scale Retrieval. In _Proceedings of the 8th International Conference on Learning Representations (ICLR)_. Addis Ababa, Ethiopia.
  * Chapelle et al. (1999) Olivier Chapelle, Patrick Haffner, and Vladimir Vapnik. 1999\.  Support vector machines for histogram-based image classification.  _IEEE Trans. Neural Networks_ 10, 5 (1999), 1055–1064.
  * Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016\.  Deep Neural Networks for YouTube Recommendations. In _Proceedings of the 10th ACM Conference on Recommender Systems (RecSys)_. Boston, MA, 191–198.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_. Minneapolis, MN, 4171–4186.
  * Fan et al. (2019) Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li. 2019\.  MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_. Anchorage, AK, 2509–2517.
  * Fu et al. (2019) Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019\.  Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.  _Proc. VLDB Endow._ 12, 5 (2019), 461–474.
  * Fukushima (1975) Kunihiko Fukushima. 1975\.  Cognitron: A self-organizing multilayered neural network.  _Biological cybernetics_ 20, 3-4 (1975), 121–136.
  * Gao et al. (2020) Weihao Gao, Xiangjun Fan, Chong Wang, Jiankai Sun, Kai Jia, Wenzhi Xiao, Ruofan Ding, Xingyan Bin, Hui Yang, and Xiaobing Liu. 2020\.  Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations.  _arXiv preprint arXiv:2007.07203_ (2020).
  * Giorgi et al. (2021) John M. Giorgi, Osvald Nitski, Bo Wang, and Gary D. Bader. 2021\.  DeCLUTR: Deep Contrastive Learning for Unsupervised Textual Representations. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP_. Virtual Event, 879–895.
  * Glorot et al. (2011) Xavier Glorot, Antoine Bordes, and Yoshua Bengio. 2011\.  Deep Sparse Rectifier Neural Networks. In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS)_. Fort Lauderdale, FL, 315–323.
  * Hart et al. (1968) Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968\.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE transactions on Systems Science and Cybernetics_ 4, 2 (1968), 100–107.
  * Hein and Bousquet (2005) Matthias Hein and Olivier Bousquet. 2005.  Hilbertian Metrics and Positive Definite Kernels on Probability Measures. In _Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS)_. Bridgetown, Barbados.
  * Huang et al. (2013) Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry P. Heck. 2013\.  Learning deep structured semantic models for web search using clickthrough data. In _Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM)_. San Francisco, CA, 2333–2338.
  * Huang et al. (2019) Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. 2019\.  Knowledge Graph Embedding Based Question Answering. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (WSDM)_. Melbourne, Australia, 105–113.
  * Jiang et al. (2007) Yu-Gang Jiang, Chong-Wah Ngo, and Jun Yang. 2007\.  Towards optimal bag-of-features for object categorization and semantic video retrieval. In _Proceedings of the 6th ACM International Conference on Image and Video Retrieval (CIVR)_. Amsterdam, The Netherlands, 494–501.
  * Karpathy et al. (2014) Andrej Karpathy, Armand Joulin, and Li Fei-Fei. 2014\.  Deep Fragment Embeddings for Bidirectional Image Sentence Mapping. In _Advances in Neural Information Processing Systems (NIPS)_. Montreal, Canada, 1889–1897.
  * Lanchantin et al. (2021) Jack Lanchantin, Tianlu Wang, Vicente Ordonez, and Yanjun Qi. 2021\.  General Multi-Label Image Classification With Transformers. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. virtual, 16478–16488.
  * Li et al. (2013) Ping Li, Gennady Samorodnitsky, and John E. Hopcroft. 2013\.  Sign Cauchy Projections and Chi-Square Kernel. In _Advances in Neural Information Processing Systems (NIPS)_. Lake Tahoe, NV, 2571–2579.
  * Liang et al. (2021) Paul Pu Liang, Manzil Zaheer, Yuan Wang, and Amr Ahmed. 2021\.  Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies. In _Proceedings of the 9th International Conference on Learning Representations, (ICLR)_. Virtual Event.
  * Malkov et al. (2014) Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014.  Approximate nearest neighbor algorithm based on navigable small world graphs.  _Information Systems_ 45 (2014), 61–68.
  * Malkov and Yashunin (2020) Yury A. Malkov and Dmitry A. Yashunin. 2020.  Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.  _IEEE Trans. Pattern Anal. Mach. Intell._ 42, 4 (2020), 824–836.
  * Morozov and Babenko (2018) Stanislav Morozov and Artem Babenko. 2018.  Non-metric Similarity Graphs for Maximum Inner Product Search. In _Advances in Neural Information Processing Systems (NeurIPS)_. Montreal, Canada, 4726–4735.
  * Nair and Hinton (2010) Vinod Nair and Geoffrey E. Hinton. 2010.  Rectified Linear Units Improve Restricted Boltzmann Machines. In _Proceedings of the 27th International Conference on Machine Learning (ICML)_. Haifa, Israel, 807–814.
  * Neelakantan et al. (2022) Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy, et al. 2022\.  Text and code embeddings by contrastive pre-training.  _arXiv preprint arXiv:2201.10005_ (2022).
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global Vectors for Word Representation. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Doha, Qatar, 1532–1543.
  * Spillo et al. (2022) Giuseppe Spillo, Cataldo Musto, Marco de Gemmis, Pasquale Lops, and Giovanni Semeraro. 2022.  Knowledge-aware Recommendations Based on Neuro-Symbolic Graph Embeddings and First-Order Logical Rules. In _Proceedings of the Sixteenth ACM Conference on Recommender Systems (RecSys)_. Seattle, WA, 616–621.
  * Tan et al. (2021a) Shulong Tan, Zhaozhuo Xu, Weijie Zhao, Hongliang Fei, Zhixin Zhou, and Ping Li. 2021a.  Norm Adjusted Proximity Graph for Fast Inner Product Retrieval. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_. Virtual Event, Singapore, 1552–1560.
  * Tan et al. (2021b) Shulong Tan, Weijie Zhao, and Ping Li. 2021b.  Fast Neural Ranking on Bipartite Graph Indices.  _Proc. VLDB Endow._ 15, 4 (2021), 794–803.
  * Tan et al. (2020) Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. 2020\.  Fast Item Ranking under Neural Network based Measures. In _Proceedings of the Thirteenth ACM International Conference on Web Search and Data Mining (WSDM)_. Houston, TX, 591–599.
  * Tibshirani (1996) Robert Tibshirani. 1996\.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ 58, 1 (1996), 267–288.
  * Trifonov et al. (2018) Valentin Trifonov, Octavian-Eugen Ganea, Anna Potapenko, and Thomas Hofmann. 2018.  Learning and evaluating sparse interpretable sentence embeddings. In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_. Brussels, Belgium, 200–210.
  * Vedaldi and Zisserman (2012) Andrea Vedaldi and Andrew Zisserman. 2012.  Efficient Additive Kernels via Explicit Feature Maps.  _IEEE Trans. Pattern Anal. Mach. Intell._ 34, 3 (2012), 480–492.
  * Vempati et al. (2010) Sreekanth Vempati, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar. 2010.  Generalized RBF feature maps for Efficient Detection. In _Proceedings of the British Machine Vision Conference (BMVC)_. Aberystwyth, UK, 1–11.
  * Wang et al. (2009) Gang Wang, Derek Hoiem, and David A. Forsyth. 2009.  Building text features for object image classification. In _Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)_. Miami, FL, 1367–1374.
  * Xu et al. (2022) Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, and Ping Li. 2022.  Proximity Graph Maintenance for Fast Online Nearest Neighbor Search.  _arXiv preprint arXiv:2206.10839_ (2022).
  * Yu et al. (2018) Chaojian Yu, Xinyi Zhao, Qi Zheng, Peng Zhang, and Xinge You. 2018.  Hierarchical Bilinear Pooling for Fine-Grained Visual Recognition. In _Proceedings of the 15th European Conference on Computer Vision (ECCV), Part XVI_. Munich, Germany, 595–610.
  * Yu et al. (2022) Tan Yu, Jie Liu, Yi Yang, Yi Li, Hongliang Fei, and Ping Li. 2022\.  EGM: Enhanced Graph-based Model for Large-scale Video Advertisement Search. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_. Washington, DC, 4443–4451.
  * Zhao et al. (2020) Weijie Zhao, Shulong Tan, and Ping Li. 2020.  SONG: Approximate Nearest Neighbor Search on GPU. In _Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE)_. Dallas, TX, 1033–1044.
  * Zhao et al. (2022a) Weijie Zhao, Shulong Tan, and Ping Li. 2022a.  Constrained Approximate Similarity Search on Proximity Graph.  _arXiv preprint arXiv:2210.14958_ (2022).
  * Zhao et al. (2022b) Weijie Zhao, Shulong Tan, and Ping Li. 2022b.  GUITAR: Gradient Pruning toward Fast Neural Ranking.  _arXiv preprint arXiv_ (2022).
  * Zhou et al. (2019) Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. 2019\.  Möbius Transformation for Fast Inner Product Search on Graph. In _Advances in Neural Information Processing Systems (NeurIPS)_. Vancouver, Canada, 8216–8227.
  * Zhu et al. (2019) Han Zhu, Daqing Chang, Ziru Xu, Pengye Zhang, Xiang Li, Jie He, Han Li, Jian Xu, and Kun Gai. 2019\.  Joint Optimization of Tree-based Index and Deep Model for Recommender Systems. In _Advances in Neural Information Processing Systems (NeurIPS)_. Vancouver, Canada, 3973–3982.
  * Zhu et al. (2018) Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. 2018.  Learning Tree-based Deep Model for Recommender Systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_. London, UK, 1079–1088.
  * Zhuo et al. (2020) Jingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu, Han Li, Jian Xu, and Kun Gai. 2020\.  Learning Optimal Tree Models under Beam Search. In _Proceedings of the 37th International Conference on Machine Learning (ICML)_. Virtual Event, 11650–11659.


# The optimal $\chi$-bound for $(P_{7},C_{4},C_{5})$-free graphs

Shenwei Huang College of Computer Science, Nankai University, Tianjin 300350,
China. Email<EMAIL_ADDRESS>Supported by the National Natural
Science Foundation of China (12171256).

(December 10, 2022)

###### Abstract

In this paper, we give an optimal $\chi$-binding function for the class of
$(P_{7},C_{4},C_{5})$-free graphs. We show that every
$(P_{7},C_{4},C_{5})$-free graph $G$ has
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$. To prove the result, we use a
decomposition theorem obtained in [K. Cameron and S. Huang and I. Penev and V.
Sivaraman, The class of $({P}_{7},{C}_{4},{C}_{5})$-free graphs:
Decomposition, algorithms, and $\chi$-boundedness, Journal of Graph Theory 93,
503–552, 2020] combined with careful inductive arguments and a nontrivial use
of the König theorem for bipartite matching.

##  1 Introduction

All graphs in this paper are finite and simple. For general graph theory
notation we follow [1]. A _$q$ -coloring_ of a graph $G$ assigns a color from
$\\{1,\ldots,q\\}$ to each vertex of $G$ such that adjacent vertices are
assigned different colors. We say that a graph $G$ is _$q$ -colorable_ if $G$
admits a $q$-coloring. The _chromatic number_ of a graph $G$, denoted by
$\chi(G)$, is the minimum number $q$ for which $G$ is $q$-colorable. The
clique number of $G$, denoted by $\omega(G)$, is the size of a largest clique
in $G$. A graph $G$ is _perfect_ if $\chi(H)=\omega(H)$ for each induced
subgraph $H$ of $G$

Let $P_{n}$, $C_{n}$ and $K_{n}$ denote the path, cycle and complete graph on
$n$ vertices, respectively. For a set $\mathcal{H}$ of graphs, we say that $G$
is $\mathcal{H}$-free if $G$ contains no induced subgraph isomorphic to
$H\in\mathcal{H}$. If $\mathcal{H}=\\{H_{1},\ldots,H_{p}\\}$, we simply write
$G$ is $(H_{1},\ldots,H_{p})$-free instead. A graph class is hereditary if it
is $\mathcal{H}$-free for some set $\mathcal{H}$ of graphs. A hereditary graph
class $\mathcal{G}$ is _$\chi$ -bounded_ if there is a function $f$ such that
$\chi(G)\leq f(\omega(G))$ for every $G\in\mathcal{G}$. The function $f$ is
called a _$\chi$ -binding function_ for $\mathcal{G}$. If $f$ can be chosen to
be a polynomial function, then $\mathcal{G}$ is called polynomially
$\chi$-bounded. It is easy to see that a necessary condition for the class of
$H$-free graphs to be $\chi$-bounded is that $H$ is a forest. Gyárfás
conjectured that this condition is also sufficient.

######  Conjecture 1 (Gyárfás [7]).

For every forest $T$, the class of $T$-free graphs is $\chi$-bounded.

Gyárfás [8] proved the conjecture for $T=P_{t}$: every $P_{t}$-free graph $G$
has $\chi(G)\leq(t-1)^{\omega(G)-1}$. Note that this $\chi$-binding function
is exponential in $\omega(G)$. Esperet asked whether every $\chi$-bounded
hereditary class is polynomially $\chi$-bounded. Recently, this question was
answered negatively by Briański, Davies and Walczak [3]. However, the question
is still wide open for $P_{t}$-free graphs.

The answer is trivial for $t\leq 4$ (since $P_{4}$-free graphs are perfect).
For $t=5$, there is a recent result by Scott, Seymour and Spirkl [11] that
gives a quasi-polynomial bound. Apart from these, not much is known.
Therefore, researchers started to investigate subclasses of $P_{t}$-free
graphs. One interesting line is to consider $P_{t}$-free graphs without
certain induced cycles. For instance, any $(P_{5},C_{3})$-free graph is
3-colorable (the bound is attained by $C_{5}$) [12], and any
$(P_{5},C_{4})$-free graph has $\chi(G)\leq\lceil\frac{5}{4}\omega(G)\rceil$
(the equal-size blowups of $C_{5}$ shows that the bound is optimal) [5]. For
$t=6$, optimal bounds have been obtained for $C_{3}$ and $C_{4}$ as well [2,
9]. For $t\geq 7$, Gravier, Hoàng and Maffray [6] showed that every
$(P_{t},C_{3})$-free graph $G$ has $\chi(G)\leq t-2$. However, it is not known
whether this is optimal. Recently, Kathie et al. [4] showed that any
$(P_{7},C_{4},C_{5})$-free $G$ has $\chi(G)\leq\frac{3}{2}\omega(G)$.

### Our Contribution

In this paper, we give an optimal $\chi$-bound for the class of
$(P_{7},C_{4},C_{5})$-free graphs. In particular, we prove the following
theorem.

######  Theorem 1.

Let $G$ be a $(P_{7},C_{4},C_{5})$-free graph. Then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

To prove the theorem, we use a decomposition theorem obtained in [4] combined
with careful inductive arguments and a nontrivial use of the König theorem for
bipartite matching. It is shown in [4] that for every positive integer $k$
there is a $(P_{7},C_{4},C_{5})$-free graph $G_{k}$ such that
$\omega(G_{k})=3k$ and $\chi(G_{k})\geq\frac{11}{9}\omega(G_{k})$. Therefore,
our result gives an optimal bound.

##  2 Preliminaries

Let $G=(V,E)$ be a graph. The _neighborhood_ of a vertex $v$ is denoted by
$N(v)=\\{u\;|\;uv\in E\\}$ and its degree by $d(v)=|N(v)|$. The closed
neighborhood of $v$, denoted by $N[v]$, is $N(v)\cup\\{v\\}$. For a set
$X\subseteq V$, we write $N(X)=\bigcup_{v\in X}N(v)\setminus X$. For $x\in V$
and $S\subseteq V$, we let $N_{S}(x)$ be the set of neighbors of $x$ that are
in $S$, that is, $N_{S}(x)=N_{G}(x)\cap S$. Define $d_{S}(v)=|N_{S}(v)|$. A
vertex $u$ is _universal_ in $G$ if $d_{G}(u)=|G|-1$.

For $S\subseteq V$, the subgraph _induced_ by $S$, is denoted by $G[S]$. The
complement of $G$ is the graph $\overline{G}$ with vertex set $V$ and edge set
$\\{uv\;|\;uv\notin E\\}$. A clique $K\subseteq V$ is a _clique cutset_ if
$G-K$ has more connected components than $G$. A clique $K$ is maximal if for
any $v\notin K$, $K\cup\\{v\\}$ is not a clique. A subset is stable if no two
vertices in the set are adjacent. A stable set $S$ is strong if it intersects
every maximum clique of $G$, i.e., $\omega(G-S)=\omega(G)-1$.

For $X,Y\subseteq V$, we say that $X$ is _complete_ (resp. _anticomplete_) to
$Y$ if every vertex in $X$ is adjacent (resp. non-adjacent) to every vertex in
$Y$. Given a graph $G=(\\{v_{1},\ldots,v_{t}\\},E(G))$ of order $t$ and graphs
$H_{1},\ldots,H_{t}$, we say that a substitution of $G$ using
$H_{1},\ldots,H_{t}$ is the graph obtained from $G$ by replacing $v_{i}$ with
a copy of $H_{i}$ such that $V(H_{i})$ and $V(H_{j})$ are complete if
$v_{i}v_{j}\in E(G)$, and anticomplete if $v_{i}v_{j}\notin E(G)$. A _blowup_
of $G$ is a substitution of $G$ using complete graphs
$K_{s_{1}},\ldots,K_{s_{t}}$ of size $s_{1},\ldots,s_{t}\geq 0$, respectively.
Note that in the definition of blowup we allow complete graphs of size 0,
which is equivalent to the operation of removing the corresponding vertex.
Therefore, any proper induced subgraph of $G$ is a blowup of $G$ under our
definition. If $s_{i}\geq 1$ for each $1\leq i\leq t$, we say the resulting
graph is a nonempty blowup of $G$. If $s_{1}=\cdots=s_{t}=x$, we denote the
resulting graph by $G[K_{x}]$ and call $G[K_{x}]$ an equal-size blowup of $G$.

##  3 The Main Result

In this section, we prove Theorem 1. For that purpose, we need a decomposition
theorem for $(P_{7},C_{4},C_{5})$-free graphs. To state the decomposition
theorem, we need to introduce two special graphs called the emerald and
7-bracelets. The emerald is a 11-vertex 4-regular graph shown in Figure 1. We
denote this graph by $E$.

1234567981110 Figure 1: The emerald $E$.
$A_{5}$$A_{4}$$A_{3}$$A_{3}^{-}$$A_{3}^{0}$$A_{6}$$A_{6}^{+}$$A_{6}^{0}$$A_{2}$$A_{2}^{-}$$A_{2}^{0}$$A_{7}$$A_{7}^{+}$$A_{7}^{0}$$A_{1}$$A_{1}^{+}$$A_{1}^{-}$$A_{1}^{0}$
Figure 2: Diagram for 7-bracelet. The thick line means the two sets are
complete, no lines means anticompleteness, and the blue line means that the
edges between the two sets are arbitrary subject to the constraint that the
resulting graph is $(P_{7},C_{4},C_{5})$-free graphs.

We say that $G$ is a 7-bracelet if $V(G)$ can be partition into 7 nonempty
cliques $A_{1},\ldots,A_{7}$ such that

$\bullet$ For each $1\leq i\leq 7$, $A_{i}$ is complete to $A_{i+1}\cup
A_{i-1}$ and anticomplete to $A_{i+3}\cup A_{i-3}$;

$\bullet$ For $i\notin\\{7,1,2\\}$, $A_{i+1}$ and $A_{i-1}$ are anticomplete;

$\bullet$ $A_{1}$ can be partitioned into three (possibly empty) subsets
$A_{1}^{0},A_{1}^{+},A_{1}^{-}$, $A_{i}$ can be partitioned into two (possibly
empty) subsets $A_{i}^{0},A_{i}^{-}$ for $i\in\\{2,3\\}$ and $A_{i}$ can be
partitioned into two (possibly empty) subsets $A_{i}^{0},A_{i}^{+}$ for
$i\in\\{6,7\\}$ such that

  1. 1.

$A_{i}^{0}$ is anticomplete to $A_{i+2}\cup A_{i-2}$ for each
$i\in\\{6,7,1,2,3\\}$;

  2. 2.

$A_{1}^{+}$ is anticomplete to $A_{6}$ and $A_{1}^{-}$ is anticomplete to
$A_{3}$;

  3. 3.

Every vertex in $A_{7}^{+}$ has a neighbor in $A_{2}^{-}$ and every vertex in
$A_{2}^{-}$ has a neighbor in $A_{7}^{+}$;

  4. 4.

Every vertex in $A_{1}^{+}$ has a neighbor in $A_{3}^{-}$ and every vertex in
$A_{3}^{-}$ has a neighbor in $A_{1}^{+}$, and every vertex in $A_{1}^{-}$ has
a neighbor in $A_{6}^{+}$ and every vertex in $A_{6}^{+}$ has a neighbor in
$A_{1}^{-}$.

See Figure 2 for the diagram of a 7-bracelet.

######  Theorem 2 ([4]).

Let $G$ be a $(P_{7},C_{4},C_{5})$-free graph. Then $G$ contains a clique
cutset or a universal vertex, or is isomorphic to a nonempty blowup of the
emerald (see Figure 1) or a 7-bracelet.

It is well-known that clique cutsets and universal vertices preserve any
$\chi$-binding function. Therefore, it suffices to consider blowups of the
emerald and 7-bracelets.

######  Theorem 3.

If $G$ is a 7-bracelet, then $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

######  Theorem 4.

If $G$ is a blowup of the emerald, then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

###### Proof of Theorem 1 (assuming Theorem 3 and Theorem 4).

We use induction on $|G|$. We may assume that $G$ is connected, for otherwise
we apply the inductive hypothesis on each connected component. If $G$ contains
a clique cutset $K$ that disconnects $H_{1}$ from $H_{2}$, let
$G_{i}=G[H_{i}\cup K]$ for $i=1,2$. Then the inductive hypothesis implies that
$\chi(G_{i})\leq\lceil\frac{11}{9}\omega(G_{i})\rceil$ for $i=1,2$. Note that
$\chi(G)=\max\\{\chi(G_{1}),\chi(G_{2})\\}$ and so
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$. If $G$ contains a strong
stable set $S$, then applying the inductive hypothesis to $G-S$ implies that
$\chi(G-S)\leq\lceil\frac{11}{9}\omega(G-S)\rceil$. Since
$\omega(G-S)\leq\omega(G)-1$, it follows that
$\chi(G)\leq\chi(G-S)+1\leq\lceil\frac{11}{9}\omega(G)\rceil$. So $G$ has no
clique cutsets or strong stable sets. In particular, $G$ has no universal
vertices. It follows then from Theorem 2 that $G$ is a blowup of the emerald
or a 7-bracelet. Now the theorem follows from Theorem 3 and Theorem 4. ∎

We prove Theorem 3 and Theorem 4 in the next two sections.

##  4 Color 7-bracelets

Let $G$ be a 7-bracelet with notations introduced in Figure 2. By the
definition of 7-bracelet, $A_{7}^{+}=\emptyset$ if and only if
$A_{2}^{-}=\emptyset$, $A_{6}^{+}=\emptyset$ if and only if
$A_{1}^{-}=\emptyset$, $A_{1}^{+}=\emptyset$ if and only if
$A_{3}^{-}=\emptyset$. If $A_{6}^{+}=A_{3}^{-}=\emptyset$, we call $G$ a
7-bracelet with one uncertain pair.

For a graph $G$, let $\beta(G)$ and $\tau(G)$ be the maximum size of a
matching and minimum size of a vertex cover, respectively. The following is a
famous theorem due to König.

######  Lemma 1 (see for example [1]).

For any bipartite graph $G$, $\beta(G)=\tau(G)$.

We first color 7-bracelets with one uncertain pair.

######  Lemma 2 (Equal-size 7-bracelet with one uncertain pair).

Let $G$ be a 7-bracelet $(A_{1},\ldots,A_{7})$ such that

$\bullet$ $|A_{i}|=x$ for each $1\leq i\leq 7$, where $x$ is a positive
integer;

$\bullet$ $A_{6}^{+}=A_{3}^{-}=\emptyset$;

$\bullet$ $\omega(G[A_{7}^{+}\cup A_{2}^{-}])\leq x$.

Then $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Since $A_{6}^{+}=A_{3}^{-}=\emptyset$, $A_{i}=A_{i}^{0}$ for
$i\in\\{6,1,3\\}$. Note that $\omega(G)=2x$ since $\omega(G[A_{7}^{+}\cup
A_{2}^{-}])\leq x$. We give a coloring of $G$ using
$\lceil\frac{7}{6}\omega(G)\rceil=\lceil\frac{7}{3}x\rceil$ colors. Consider
the following coloring $\phi$ of $G$: color vertices in $A_{i}$ using colors
$(i-1)x+1,(i-1)x+2,\ldots,(i-1)x+x$ for each $i$, where colors are taken
modulo $\lceil\frac{7x}{3}\rceil$. Clearly, $\phi$ is a proper coloring of
$G-F$, where $F$ is the set of edges between $A_{7}^{+}$ and $A_{2}^{-}$.

It remains to show that it is possible to assign colors in $\phi(A_{2})$ to
the vertices of $A_{2}$ and assign colors in $\phi(A_{7})$ to the vertices of
$A_{7}$ in such a way that no edge between $A_{7}^{+}$ and $A_{2}^{-}$ is
monochromatic. If a color $c\in\phi(A_{2})\cap\phi(A_{7})$ is assigned to a
vertex in $A_{2}^{0}$, then it can be assigned to any vertex in $A_{7}^{+}$.
Similarly, if a color $c\in\phi(A_{2})\cap\phi(A_{7})$ is assigned to a vertex
in $A_{7}^{0}$, then it can be assigned to any vertex in $A_{2}^{-}$. However,
if a color $c\in\phi(A_{2})\cap\phi(A_{7})$ is not assigned to a vertex in
$A_{2}^{0}\cup A_{7}^{0}$, it must be used on a non-edge between $A_{7}^{+}$
and $A_{2}^{-}$.

Let $t=|A_{2}^{0}|+|A_{7}^{0}|$. Then $G^{\prime}:=G[A_{2}^{-}\cup A_{7}^{+}]$
has order $2x-t$. Since $\omega(G^{\prime})\leq x$,
$\alpha(\overline{G^{\prime}})\leq x$. By König Theorem,
$\beta(\overline{G^{\prime}})=\tau(\overline{G^{\prime}})$. Since
$\alpha(\overline{G^{\prime}})+\tau(\overline{G^{\prime}})\geq|G^{\prime}|$,
it follows that

$\displaystyle\beta(\overline{G^{\prime}})$
$\displaystyle\geq|G^{\prime}|-\alpha(\overline{G^{\prime}})$
$\displaystyle\geq x-t$ $\displaystyle\geq|\phi(A_{2})\cap\phi(A_{7})|-t.$

Now consider the following assignment of colors to $A_{2}\cup A_{7}$ from
$\phi(A_{2})\cup\phi(A_{7})$.

$\bullet$ Color the vertices in $A_{2}^{0}\cup A_{7}^{0}$ using colors in
$\phi(A_{2})\cap\phi(A_{7})$;

$\bullet$ For each $c\in\phi(A_{2})\cap\phi(A_{7})$ not used on $A_{2}^{0}\cup
A_{7}^{0}$ , assign $c$ to a non-edge $e_{c}$ between $A_{7}^{+}$ and
$A_{2}^{-}$. Since
$\beta(\overline{G^{\prime}})\geq|\phi(A_{2})\cap\phi(A_{7})|-t$, it is
possible to choose $e_{c}$ so that $e_{c}\cap e_{c^{\prime}}=\emptyset$ for
$c,c^{\prime}\in\phi(A_{2})\cap\phi(A_{7})$ and $c\neq c^{\prime}$.

$\bullet$ Color the remaining vertices in $A_{2}$ and $A_{7}$ in an arbitrary
way.

It is routine to verify that this is a proper coloring of $G$. ∎

######  Lemma 3 (Equal-size 7-bracelet).

Let $G$ be a 7-bracelet such that

$\bullet$ $|A_{i}|=x$ for each $1\leq i\leq 7$, where $x$ is a positive
integer;

$\bullet$ $\omega(G[A_{6}^{+}\cup A_{1}^{-}]),\omega(G[A_{1}^{+}\cup
A_{3}^{-}]),\omega(G[A_{7}^{+}\cup A_{2}^{-}])\leq x$.

Then $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Note that $\omega(G)=2x$ since $\omega(G[A_{6}^{+}\cup
A_{1}^{-}]),\omega(G[A_{1}^{+}\cup A_{3}^{-}]),\omega(G[A_{7}^{+}\cup
A_{2}^{-}])\leq x$. We give a coloring of $G$ using
$\lceil\frac{7}{6}\omega(G)\rceil=\lceil\frac{7}{3}x\rceil$ colors. Consider
the following coloring $\phi$ of $G$: color vertices in $A_{i}$ using colors
$(i-1)x+1,(i-1)x+2,\ldots,(i-1)x+x$ for each $i$, where colors are taken
modulo $\lceil\frac{7x}{3}\rceil$. Let $F_{61}$ ($F_{13}$) be the set of edges
between $A_{6}$ ($A_{3}$) and $A_{1}$. By Lemma 2, $\phi$ is a proper coloring
of $G-(F_{61}\cup F_{13})$. It remains to show that it is possible to assign
colors from $\phi(A_{1}),\phi(A_{3}),\phi(A_{6})$ to vertices in
$A_{1},A_{3},A_{6}$ respectively so that the resulting coloring is a proper
coloring of $G$.

For clarity, we assume that $x=3k$ for some $k\geq 1$ (and the cases that
$x=3k+1$ or $x=3k+2$ are similar). Note that $\phi(A_{1})=\\{1,\ldots,3k\\}$,
$\phi(A_{3})=\\{6k+1,\ldots,1,\ldots,2k\\}$,
$\phi(A_{6})=\\{k+1,\ldots,4k\\}$. Then
$C:=\phi(A_{1})\cup\phi(A_{3})\cup\phi(A_{6})$ has size $5k$. Let

$\displaystyle C_{6}=C\setminus(\phi(A_{1})\cup\phi(A_{3}));$ $\displaystyle
C_{61}=(\phi(A_{1})\cap\phi(A_{6}))\setminus\phi(A_{3});$ $\displaystyle
C_{613}=\phi(A_{1})\cap\phi(A_{6})\cap\phi(A_{3});$ $\displaystyle
C_{13}=(\phi(A_{1})\cap\phi(A_{3}))\setminus\phi(A_{6});$ $\displaystyle
C_{3}=C\setminus(\phi(A_{1})\cup\phi(A_{6})).$

Note that $C=C_{6}\cup C_{61}\cup C_{613}\cup C_{13}\cup C_{3}$ and
$|C_{6}|=|C_{61}|=|C_{613}|=|C_{13}|=|C_{3}|=k$.

If $|A_{1}^{+}|\leq k$, then color vertices in $A_{1}^{+}$ using colors from
$C_{61}$. Since $C_{61}\cap\phi(A_{3})=\emptyset$, $A_{3}$ can be colored in
an arbitrary way. By Lemma 2, it is possible to assign colors from
$\phi(A_{1})$ and $\phi(A_{6})$ to vertices in $A_{1}$ and $A_{6}$ such that
vertices in $A_{1}^{+}$ are colored with colors from $C_{61}$ and the
resulting coloring is a proper coloring of $G$. So $|A_{1}^{+}|>k$. By
symmetry, $|A_{1}^{-}|>k$.

For every two vertices $x,y\in A_{1}^{-}$, $N_{A_{6}^{+}}(x)\subseteq
N_{A_{6}^{+}}(y)$ or $N_{A_{6}^{+}}(y)\subseteq N_{A_{6}^{+}}(x)$, since $G$
is $C_{4}$-free. Let $A_{1}^{--}\subseteq A_{1}^{-}$ be a set of $k$ vertices
consisting of the largest $k$ vertices of $A_{1}^{-}$ (with respect to the
neighborhood in $A_{6}^{+}$). Let $A_{1}^{++}\subseteq A_{1}^{+}$ be a set of
$k$ vertices consisting of the largest $k$ vertices of $A_{1}^{+}$ (with
respect to the neighborhood in $A_{3}^{-}$). Color $A_{1}^{--}$ using $k$
colors in $C_{13}$ and $A_{1}^{++}$ using $k$ colors in $C_{61}$. We now
consider two cases.

Case 1. $|R_{1}^{-}|\leq|A_{6}^{0}|$. In this case, color $R_{1}^{-}$ using
colors in $C_{613}$ and these colors can also be used to color $|R_{1}^{-}|$
vertices in $A_{6}^{0}$. Then color $A_{6}^{+}$ using the remaining colors in
$\phi(A_{6})$. It is easy to see that the coloring of $A_{6}$ and the coloring
of $A_{1}$ are proper. Since in this coloring all colors used on $A_{1}^{-}$
belong to $\phi(A_{1})\cap\phi(A_{3})$, it is possible to extend this coloring
to a proper coloring of $G$ by Lemma 2.

Case 2. $|R_{1}^{-}|>|A_{6}^{0}|$. By symmetry, $|R_{1}^{+}|>|A_{3}^{0}|$.
Since $|A_{1}^{--}|,|A_{1}^{++}|=k$ and $|A_{1}|=3k$,
$|R_{1}^{-}|+|R_{1}^{+}|+|A_{1}^{0}|=k$. So

$|A_{6}^{0}|<|R_{1}^{-}|\leq k.$

This implies that $|A_{6}^{+}|>2k$ and so $|A_{6}^{+}|+|A_{1}^{--}|>3k$. By
symmetry, $|A_{3}^{-}|>2k$ and $|A_{3}^{-}|+|A_{1}^{++}|>3k$.

We claim that for each $r\in R_{1}^{-}$, $r$ has a non-neighbor $f(r)$ in
$A_{6}^{+}$. Moreover, we can choose $f$ to be injective. We prove this by
induction on $|R_{1}^{-}|$. The base case is $|R_{1}^{-}|=\\{r_{1}\\}$. If
$r_{1}$ is complete to $A_{6}^{+}$, then $A_{6}^{+}\cup
A_{1}^{--}\cup\\{r_{1}\\}$ is a clique of size larger than $3k$ by the
definition of $A_{1}^{--}$. This contradicts that
$\omega(G[A_{6}^{+},A_{1}^{-}])\leq 3k$. So $r_{1}$ has a non-neighbor $s_{1}$
in $A_{6}^{+}$. Now suppose that $|R_{1}^{-}|=i\geq 2$ and let $r_{j}$ be the
$j$th largest vertex in $R_{1}^{-}$ for $1\leq j\leq i$, and that we have
found distinct non-neighbors $s_{1},\ldots,s_{i-1}$ of $r_{1},\ldots,r_{i-1}$.
If $r_{i}$ is complete to $A_{6}^{+}\setminus\\{s_{1},\ldots,s_{i-1}\\}$, then
$(A_{6}^{+}\setminus\\{s_{1},\ldots,s_{i-1}\\})\cup\\{r_{1},\ldots,r_{i}\\}\cup
A_{1}^{--}$ is a clique of $G[A_{6}^{+}\cup A_{1}^{-}]$ of size larger than
$3k$. This contradicts that $\omega(G[A_{6}^{+}\cup A_{1}^{-}])\leq 3k$. So
$r_{i}$ must have a non-neighbor $s_{i}\in
A_{6}^{+}\setminus\\{s_{1},\ldots,s_{i-1}\\}$. This proves the claim. By
symmetry, for each $r\in R_{1}^{+}$, $r$ has a non-neighbor $g(r)$ in
$A_{3}^{-}$. Moreover, we can choose $g$ to be injective.

Now we can have a desired coloring as follows.

$\bullet$ Color $R_{1}^{-},R_{1}^{+},A_{1}^{0}$ using the $k$ colors in
$C_{613}$ in any way.

$\bullet$ For each color $i$ assigned to some vertex $r\in R_{1}^{-}$, color a
non-neighbor $f(r)\in A_{6}^{+}$ of $r$ with $i$, and color the remaining
vertices in $A_{6}$ in any way.

$\bullet$ For each color $i$ assigned to some vertex $r\in R_{1}^{+}$, color a
non-neighbor $g(r)\in A_{3}^{-}$ of $r$ with $i$, and color the remaining
vertices in $A_{3}$ in any way. ∎

Now we are ready to prove Theorem 3.

###### Proof of Theorem 3.

Let $G$ be a 7-bracelet $(A_{1},\ldots,A_{7})$. We prove by induction on
$|G|$. If $G$ has a strong stable set $S$, we are done by applying the
inductive hypothesis to $G-S$. So we assume that $G$ has no strong stable set.
Let $K_{61}$, $K_{13}$ and $K_{72}$ be any maximum clique of $G[A_{6}^{+}\cup
A_{1}^{-}]$, $G[A_{1}^{+}\cup A_{3}^{-}]$, and $G[A_{7}^{+}\cup A_{2}^{-}]$,
respectively. Observe that the possible maximum cliques of $G$ are $A_{i}\cup
A_{i+1}$, $K_{61}\cup A_{7}$, $K_{13}\cup A_{2}$ or $K_{72}\cup A_{1}$. We
claim that

$A_{i}\cup A_{i+1}\text{ is a maximum clique of }G\text{ for each }i.$ (1)

Since $G$ is $C_{4}$-free and each vertex in $A^{+}_{6}$ has a neighbor in
$A_{1}^{-}$, there exits a vertex in $A_{1}^{-}$ that is complete to
$A_{6}^{+}$. Let $a_{1}^{-}$ be such a vertex. Note that $a_{1}^{-}$ is
universal in $G[A^{+}_{6}\cup A^{-}_{1}\cup A_{7}]$ and so is in every maximum
clique of $G[A^{+}_{6}\cup A^{-}_{1}\cup A_{7}]$. The vertices
$a_{6}^{+},a_{7}^{+},a_{2}^{-},a_{1}^{+},a_{3}^{-}$ can be defined similarly.
If $A_{i}\cup A_{i+1}$ is not maximum, we can find a strong stable set $S$ of
$G$ as follows, which is a contradiction. For $1\leq i\leq 7$, let $a_{i}\in
A_{i}$.

$\bullet$ If $A_{4}\cup A_{5}$ is not a maximum clique, then
$S=\\{a_{1},a_{6}^{+},a_{3}^{-}\\}$ is a desired set.

$\bullet$ If $A_{5}\cup A_{6}$ is not a maximum clique, then
$S=\\{a_{4},a_{2}^{-},a_{7}^{+}\\}$ is a desired set. The case $A_{4}\cup
A_{3}$ is symmetric.

$\bullet$ If $A_{6}\cup A_{7}$ is not a maximum clique, then
$S=\\{a_{5},a_{3}^{-},a_{1}^{-}\\}$ is a desired set. The case $A_{2}\cup
A_{3}$ is symmetric.

$\bullet$ If $A_{1}\cup A_{7}$ is not a maximum clique, then
$S=\\{a_{4},a_{2}^{-},a_{6}^{+}\\}$ is a desired set. The case $A_{2}\cup
A_{1}$ is symmetric.

This proves (1). Therefore, $|A_{i}|=x\geq 1$ for each $1\leq i\leq 7$ and
$\omega(G[A_{6}^{+}\cup A_{1}^{-}]),\omega(G[A_{1}^{+}\cup
A_{3}^{-}]),\omega(G[A_{7}^{+}\cup A_{2}^{-}])\leq x$. It now follows from
Lemma 3 that $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$. ∎

##  5 Color Blowup of the Emerald

Let $G$ be a blowup of the emerald. For each $i\in V(E)$ (see Figure 1), let
$L_{i}$ be the clique that substitutes the vertex $i$. Define
$p(G)=\min_{1\leq i\leq 11}|L_{i}|$. The overall strategy is to consider the
blowups of a sequence of proper induced subgraphs (starting from $C_{7}$) of
the emerald. We prove the bounds on the blowups of the larger induced subgraph
using the results on blowups of the smaller induced subgraph as the base case
for induction. In the end, we are able to show that the
$\lceil\frac{11}{9}\omega(G)\rceil$ bound holds when $p(G)\leq 2$ (Lemma 13)
and $p(G)\geq 3$ (Lemma 15), which together imply Theorem 4.

We start with a famous lemma due to Lovász.

######  Lemma 4 ([10]).

Any blowup of a perfect graph is still a perfect graph.

We now determine the chromatic number of equal-size blowups of $C_{7}$.

######  Lemma 5 (Equal-size blowup of $C_{7}$).

For any integer $t\geq 1$,
$\chi(C_{7}[K_{t}])=\lceil\frac{7}{6}\omega(C_{7}[K_{t}])\rceil$.

###### Proof.

Let $G=C_{7}[K_{t}]$ where $t\geq 1$. Note first that
$\chi(G)\geq\lceil\frac{7t}{3}\rceil=\lceil\frac{7}{6}\omega(G)\rceil$. Next
we show that $\chi(G)\leq\lceil\frac{7t}{3}\rceil$. Let $L_{i}$ be the clique
that substitutes the vertex $i\in V(C_{7})$ for $1\leq i\leq 7$. Consider the
following coloring $\phi$ of $G$: color vertices in $L_{i}$ using colors
$(i-1)t+1,(i-1)t+2,\ldots,(i-1)t+t$ for each $i$, where colors are taken
modulo $\lceil\frac{7t}{3}\rceil$. It is routine to verify that $\phi$ is a
proper coloring of $G$. ∎

1234567$v$ Figure 3: The graph $C_{7}+v$.

######  Lemma 6 (Blowup of $C_{7}+v$).

If $G$ is a blowup of $C_{7}+v$ shown in Figure 3, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Let $G$ be a blowup of $C_{7}+v$ shown in Figure 3. Suppose that $L_{u}$ is
the clique that substitutes the vertex $u\in V(C_{7}+v)$. If $L_{i}=\emptyset$
for some $i\in\\{1,2,\ldots,7\\}$, then $G$ is perfect and
$\chi(G)=\omega(G)$. Therefore, we may assume that $L_{i}\neq\emptyset$ for
each $i\in\\{1,2,\ldots,7\\}$. Hence, $t:=\min_{1\leq i\leq 7}|L_{i}|\geq 1$.
For each $i\in\\{1,2,\ldots,7\\}$, let $L^{\prime}_{i}\subseteq L_{i}$ be a
set of size $t$. Denote by $H$ the subgraph of $G$ induced by
$\bigcup_{i=1}^{7}L^{\prime}_{i}$. Note that $G-V(H)$ is perfect and
$\omega(G-H)\leq\omega(G)-2t$. It follows from Lemma 5 that

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-H)+\chi(H)$
$\displaystyle\leq(\omega(G)-2t)+\lceil\frac{7}{3}t\rceil$
$\displaystyle=\omega(G)+\lceil\frac{t}{3}\rceil.$

Since $t\leq\frac{\omega(G)}{2}$,
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$. ∎

1$x_{1}$2$x_{3}$3$x_{1}$4$x_{1}$5$x_{1}$6$x_{1}$7$x_{2}$$t_{7}$$x_{3}$$t_{2}$$x_{2}$
Figure 4: The graph $C_{7}+2t$. The label outside a vertex $u$ represents
$|L_{u}|$.

######  Lemma 7 (Blowup of $C_{7}+2t$).

If $G$ is a blowup of $C_{7}+2t$ shown in Figure 4, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

We prove by induction on $|G|$. Suppose that $L_{u}$ is the clique that
substitutes the vertex $u\in V(C_{7}+2t)$. If $L_{u}=\emptyset$ for some $u\in
V(C_{7}+2t)$, then either $G$ is perfect or $G$ is a blowup of $C_{7}+v$.
Hence, we are done by Lemma 6. Therefore, we may assume that
$L_{u}\neq\emptyset$ for each $u\in V(C_{7}+2t)$. For every maximal clique $K$
of $C_{7}+2t$, there is an stable set $S_{K}$ such that $S_{K}$ meets every
maximal clique of $C_{7}+2t$ except $K$. This implies that if $\bigcup_{u\in
K}L_{u}$ is not a maximum clique of $G$ for some maximal clique $K$ of
$C_{7}+2t$, then $\omega(G-S_{K})\leq\omega(G)-1$. We are then done by
applying the inductive hypothesis to $G-S_{K}$. Therefore, $\bigcup_{u\in
K}L_{u}$ is a maximum clique of $G$ for every maximal clique of $C_{7}+2t$.
Hence, the sizes of $L_{u}$ must be the ones shown in Figure 4, where
$x_{1},x_{2},x_{3}$ are positive integers with $x_{1}=x_{2}+x_{3}$. Note that
$\omega(G)=2(x_{2}+x_{3})$.

For each clique $L_{u}$ with $|L_{u}|=x_{1}$ or $|L_{u}|=x_{2}$, let
$L^{\prime}_{u}\subseteq L_{u}$ be a set of size $x_{2}$. Denote by $H$ the
subgraph of $G$ induced by the union of those $L^{\prime}_{u}$. Since
$x_{1}=x_{2}+x_{3}$, $H=C_{7}[K_{x_{2}}]$ and $G-H=C_{7}[K_{x_{3}}]$. It
follows from Lemma 5 that,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(H)+\chi(G-H)$
$\displaystyle=\lceil\frac{7}{6}(2x_{2})\rceil+\lceil\frac{7}{6}(2x_{3})\rceil$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil,$

unless $x_{2},x_{3}\equiv 1\pmod{3}$. If $x_{2}=x_{3}=1$, then it is easy to
see that $\omega(G)=4$ and $\chi(G)=5=\lceil\frac{7}{6}\omega(G)\rceil$. By
symmetry, we now assume that $x_{2}\equiv 1\pmod{3}$ and $x_{2}\geq 4$. For
each $u\in V(C_{7}+2v)$ with $|L_{u}|\in\\{x_{2},x_{1}\\}$, let
$L^{\prime}_{u}\subseteq L_{u}$ of size 3. Denote by $H$ the subgraph of $G$
induced by those $L^{\prime}_{u}$. Then $H=C_{7}[K_{3}]$ and
$\omega(G-H)\leq\omega(G)-6$. By the inductive hypothesis and Lemma 5,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-H)+\chi(H)$
$\displaystyle\leq\lceil\frac{7}{6}(\omega(G)-6)\rceil+7$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil.$

This completes the proof. ∎

1234567$f_{2}$$f_{7}$ Figure 5: The graph $C_{7}+2f$.

######  Lemma 8 (Blowup of $C_{7}+2f$).

If $G$ is a blowup of $C_{7}+2f$ shown in Figure 5, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Suppose that $L_{u}$ is the clique that substitutes the vertex $u\in
V(C_{7}+2f)$. Let $t=\min\\{|L_{1}|,|L_{f_{2}}|,|L_{f_{7}}|\\}$. If $t=0$,
then $G$ is either perfect or a blowup of $C_{7}+v$. We are done by Lemma 6.
Therefore, we assume that $t\geq 1$. For each $u\in\\{1,f_{2},f_{7}\\}$, let
$L^{\prime}_{u}\subseteq L_{u}$ be a set of size $t$. Let
$G^{\prime}=G[L^{\prime}_{1}\cup L^{\prime}_{f_{2}}\cup L^{\prime}_{f_{7}}]$.
Note that $\omega(G-G^{\prime})\leq\omega(G)-t$. Moreover, $G-G^{\prime}$ is
either perfect or blowup of a $C_{7}+v$. By Lemma 6,
$\chi(G-G^{\prime})\leq\lceil\frac{7}{6}(\omega(G)-t)\rceil$. It follows that

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-G^{\prime})+\chi(G^{\prime})$
$\displaystyle\leq\lceil\frac{7}{6}(\omega(G)-t)\rceil+t$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil.$

This completes the proof. ∎

######  Lemma 9 (Blowup of emerald minus two vertices).

If $G$ is a blowup of a proper induced subgraph of $H=E-8$ shown in Figure 1,
then $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Note that there are five symmetric pairs
$\\{1,2\\},\\{3,6\\},\\{7,9\\},\\{10,11\\},\\{4,5\\}$ in $H$. Let $G$ be a
blowup of $H-v$ where $v$ is a vertex in one of the five pairs.

$\bullet$ Observe that $H-1$ and $H-10$ are perfect. By Lemma 4, any blowup of
$H-1$ or $H-10$ is perfect. If $v\in\\{1,2,10,11\\}$, then
$\chi(G)=\omega(G)$.

$\bullet$ Observe that $H-5$ is isomorphic to $C_{7}+v$ (see Figure 3). By
Lemma 6, $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$ if $v\in\\{4,5\\}$.

$\bullet$ Observe that $H-6$ is isomorphic to $C_{7}+2t$ (see Figure 4). By
Lemma 7, $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$ if $v\in\\{3,6\\}$.

$\bullet$ Note that $H-7$ is isomorphic to $C_{7}+2f$ shown in Figure 5. By
Lemma 8, $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$ if $v\in\\{7,9\\}$. ∎

1$x_{1}$2$x_{1}$3$x_{3}$4$x_{2}$5$x_{3}$6$x_{2}$7$x_{3}$9$x_{2}$11$x_{1}$10$x_{1}$
Figure 6: The graph $E-8$. The label outside a vertex $u$ represents
$|L_{u}|$.

######  Lemma 10 (Blowup of the emerald minus one vertex).

If $G$ is a blowup of $E-8$ shown in Figure 6, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.

###### Proof.

Let $H=E-8$. We prove by induction on $|G|$. Suppose that $L_{u}$ is the
clique that substitutes the vertex $u\in V(H)$. If $L_{u}=\emptyset$ for some
$u\in V(E-8)$, then $G$ is a blowup of a proper induced subgraph of $H$. It
follows from Lemma 9 that $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$.
Therefore, we assume that $|L_{u}|\geq 1$ for each $u\in V(H)$. Note that for
each maximal clique $K$ of $H$, there exists an stable set $S_{K}$ of $H$ of
size 3 such that $S$ meets every maximal clique of $H$ except $K$.

Case 1. There exists a maximal clique $K$ of $H$ such that $\bigcup_{u\in
K}L_{u}$ is not a maximum clique of $G$. Then there exsits an stable set $S$
of $G$ of size 3 such that $\omega(G-S)\leq\omega(G)-1$. By the inductive
hypothesis,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-S)+1$
$\displaystyle\leq\lceil\frac{7}{6}(\omega(G)-1)\rceil+1$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil.$

Case 2. For every maximal clique $K$ of $H$, $\bigcup_{u\in K}L_{u}$ is a
maximum clique of $G$. Then the sizes of $L_{u}$ must be the ones shown in
Figure 6, where $x_{1},x_{2},x_{3}$ are positive integers and
$x_{1}=x_{2}+x_{3}$. For each clique $L_{u}$ with $|L_{u}|=x_{1}$ or
$|L_{u}|=x_{2}$, let $L^{\prime}_{u}\subseteq L_{u}$ be a set of size $x_{2}$.
Denote by $G^{\prime}$ the subgraph of $G$ induced by the union of those
$L^{\prime}_{u}$. Since $x_{1}=x_{2}+x_{3}$, $G^{\prime}=C_{7}[K_{x_{2}}]$ and
$G-G^{\prime}=C_{7}[K_{x_{3}}]$. Note that $\omega(G)=2(x_{2}+x_{3})$. It
follows from Lemma 5 that,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G^{\prime})+\chi(G-G^{\prime})$
$\displaystyle=\lceil\frac{7}{6}(2x_{2})\rceil+\lceil\frac{7}{6}(2x_{3})\rceil$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil,$

unless $x_{2},x_{3}\equiv 1\pmod{3}$. If $x_{2}=x_{3}=1$, then it is easy to
see that $\omega(G)=4$ and $\chi(G)=5=\lceil\frac{7}{6}\omega(G)\rceil$. By
symmetry, we now assume that $x_{2}\equiv 1\pmod{3}$ and $x_{2}\geq 4$. For
each $u\in V(E-8)$ with $|L_{u}|\in\\{x_{2},x_{1}\\}$, let
$L^{\prime}_{u}\subseteq L_{u}$ of size 3. Denote by $H$ the subgraph of $G$
induced by those $L^{\prime}_{u}$. Then $H=C_{7}[K_{3}]$ and
$\omega(G-H)\leq\omega(G)-6$. By the inductive hypothesis and Lemma 5,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-H)+\chi(H)$
$\displaystyle\leq\lceil\frac{7}{6}(\omega(G)-6)\rceil+7$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil.$

This completes the proof. ∎

1$x$23$x$4$x$5$x$6$x$7$t_{7}$$t_{2}$$x+2$$x+2$$\leq x+2$ Figure 7: The graph
$G_{x}$, where $|L_{7}|+|L_{t_{7}}|=|L_{2}|+|L_{t_{2}}|=x+2$ and
$|L_{t_{7}}|+|L_{t_{2}}|\leq x+2$.

We need the following lemma to handle certain subgraphs of blowups of the
emerald in the subsequent proof.

######  Lemma 11.

Let $G_{x}$ be a nonempty blowup of the graph in Figure 7, where $L_{i}$ is
the clique that substitutes the vertex $i\in\\{1,2,3,4,5,6,7,t_{2},t_{7}\\}$.
Suppose that $x\geq 1$, $|L_{7}|+|L_{t_{7}}|=|L_{2}|+|L_{t_{2}}|=x+2$ and
$|L_{t_{7}}|+|L_{t_{2}}|\leq x+2$. Then
$\chi(G_{x})\leq\lceil\frac{7}{6}(2x+1)\rceil$.

###### Proof.

We prove by induction on $x$. It is routine to verify that the lemma is true
for $1\leq x\leq 6$. Now suppose that $x\geq 7$. Suppose that
$|L_{7}|,|L_{t_{2}}|\geq 4$. For each $u\in\\{1,t_{2},3,4,5,6,7\\}$, let
$L^{\prime}_{u}\subseteq L_{u}$ be a set of size 3 and $H$ be the union of
those $L^{\prime}_{u}$. Then $H=C_{7}[K_{3}]$ and $G-H$ is isomorphic to
$G_{x-3}$. By induction and Lemma 5,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(H)+\chi(G-H)$
$\displaystyle\leq\lceil\frac{7}{6}(2(x-3)+1)\rceil+7$
$\displaystyle=\lceil\frac{7}{6}(2x+1)\rceil.$

So $|L_{7}|\leq 3$ or $|L_{t_{2}}|\leq 3$. If $|L_{7}|\leq 3$, then
$|L_{t_{7}}|\geq x-1$, $|L_{t_{2}}|\leq 3$ and $|L_{2}|\geq x-1$. Since $x\geq
7$, $|L_{t_{7}}|,|L_{2}|\geq 6$ and the same argument applies. So
$|L_{t_{2}}|\leq 3$. By symmetry, $|L_{t_{7}}|\leq 3$. This implies that
$|L_{2}|,|L_{7}|\geq x-1\geq 6$. For $u=1,2,\ldots,7$, let
$L^{\prime}_{u}\subseteq L_{u}$ be a set of size 3 and $H$ be the union of
those $L^{\prime}_{u}$. Then $H=C_{7}[K_{3}]$. Since
$|L_{t_{2}}|+|L_{t_{7}}|\leq 6\leq(x-3)+2$, $G-H=G_{x-3}$. So we are done by
applying the inductive hypothesis to $G-H$. ∎

The next lemma gives a near optimal bound on the chromatic number of blowups
$G$ of the emerald with $p(G)\leq 2$.

######  Lemma 12.

If $G$ is a blowup of the emerald with $p(G)\leq 2$, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$.

###### Proof.

We prove the lemma by induction on $|G|$. Suppose that $L_{i}$ is the clique
that substitutes the vertex $i\in V(E)$. We assume that $i\in L_{i}$ for
$1\leq i\leq 11$. Let $p=p(G)$. Since $E$ is vertex-transitive, we may assume
that $|L_{8}|=p$. If $p\leq 1$, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$ by Lemma 10. So $p=2$. If
$G=E[K_{2}]$, then $\chi(G)=8,\omega(G)=6$ and
$\chi(G)=\lceil\frac{7}{6}\omega(G)\rceil+1$. Now assume that $G$ is not
$E[K_{2}]$ and the lemma holds for any blowup $G^{\prime}$ of the emerald such
that $|G^{\prime}|<|G|$ and $p(G^{\prime})\leq 2$. In the following, we assume
that $G$ has no strong stable sets for otherwise we are done by the inductive
hypothesis.

We say that a vertex $i\in V(E)$ is minimum if $|L_{i}|=p$. A triangle
$\\{i,j,k\\}$ in the emerald is maximum if
$|L_{i}|+|L_{j}|+|L_{k}|=\omega(G)$. Let $T(E)$ be the triangle graph of $E$
whose vertices are all triangles of $E$ and two triangles are adjacent in
$T(E)$ if and only if they share an edge in $E$. Note that $T(E)=C_{11}$. The
distance of two triangles in the emerald is their distance in $T(E)$. We
proceed with a sequence of claims.

######  Claim 1.

If a triangle in the emerald is not maximum, then any triangle of distance 1
or 4 to that triangle is maximum.

###### Proof of Claim 1.

By symmetry, assume that $\\{1,2,8\\}$ is not maximum. If $\\{1,7,8\\}$ is not
maximum, then $\\{4,6,9\\}$ is a strong stable set. If $\\{5,6,11\\}$ is not
maximum, then $\\{4,7,9\\}$ is a strong stable set. In either case, it
contradicts that $G$ has no strong stable set. ∎

For a vertex $i\in V(E)$, $N_{E}(i)$ induces a $P_{4}$. The middle triangle of
$i$ is the triangle consisting of the middle edge of the $P_{4}$ and $i$. The
other two triangles containing $i$ are called end triangles.

######  Claim 2.

The middle triangle of a minimum vertex is maximum.

###### Proof.

Suppose that $T=\\{1,2,8\\}$ is not maximum. By Claim 1,

$\text{triangles }\\{1,7,8\\},\\{2,8,9\\},\\{5,6,11\\},\\{3,4,10\\}\text{ are
maximum}.$

This implies that $|L_{6}|=|L_{3}|=p$ and $\\{1,6,7\\},\\{2,3,9\\}$ are
maximum, which in turn implies that $|L_{4}|=|L_{5}|=p$ and
$\\{4,5,10\\},\\{4,5,11\\}$ are maximum. Therefore, $|L_{10}|=|L_{11}|$,
$|L_{1}|\geq|L_{11}|$, and $|L_{2}|\geq|L_{10}|$. It follows that
$|L_{1}|+|L_{2}|+|L_{8}|\geq|L_{10}|+|L_{11}|+p=\omega(G)$. This contradicts
that $T$ is not maximum. ∎

######  Claim 3.

If both end triangles of a minimum vertex are not maximum, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$.

###### Proof.

By Claim 2, $T=\\{1,2,8\\}$ is maximum. Suppose that $\\{1,7,8\\}$ and
$\\{2,8,9\\}$ are not maximum. By Claim 1, triangles
$\\{2,3,9\\},\\{1,6,7\\},\\{3,9,10\\},\\{6,7,11\\},\\{4,5,10\\},\\{4,5,11\\}$
are maximum. Therefore, $|L_{1}|=|L_{2}|=|L_{4}|=|L_{5}|$. Let $x=|L_{1}|$,
$y=|L_{4}|$ and $z=|L_{5}|$. Note that $\omega(G)=2x+2$, $y+z=x+2$ and $G$ is
the graph shown in Figure 8, where $r,s$ are nonnegative integers.

1$x$2$x$3$z-s$4$y$5$z$6$y-r$7$z+r$9$y+s$8$p$11$x$10$x$ Figure 8: A special
emerald with parameters $x,y,z,r,s$. The label outside the vertex $i$
represents the size of $L_{i}$.

Since $\\{2,8,9\\}$ and $\\{1,7,8\\}$ are not maximum, $y-r,z-s\geq 3$. Hence,
$y,z\geq 3$ and $x\geq 4$. Suppose first that $r\geq 3$. For each vertex
$i\in\\{1,2,4,7,9,10,11\\}$, let $L^{\prime}_{i}\subseteq L_{i}$ be a set of
size 3. Note that $H:=G[L^{\prime}_{1}\cup L^{\prime}_{2}\cup
L^{\prime}_{4}\cup L^{\prime}_{7}\cup L^{\prime}_{9}\cup L^{\prime}_{10}\cup
L^{\prime}_{11}]$ is isomorphic to $C_{7}[K_{3}]$. By Lemma 5, $\chi(H)=7$.
Since $r\geq 3$, $|L_{6}|+|L_{5}|+|L_{11}|\leq\omega(G)-3$ and so
$\omega(G-H)\leq\omega(G)-6$. By the inductive hypothesis,

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G-H)+\chi(H)$
$\displaystyle\leq\lceil\frac{7}{6}(\omega(G)-6)\rceil+1+7$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil+1.$

Therefore, $r\leq 2$. By symmetry, $s\leq 2$.

Suppose that $y+s<x-2$. For each vertex $i\in\\{1,2,3,5,7,10,11\\}$, let
$L^{\prime}_{i}\subseteq L_{i}$ be a set of size 3. Note that
$H:=G[L^{\prime}_{1}\cup L^{\prime}_{2}\cup L^{\prime}_{3}\cup
L^{\prime}_{5}\cup L^{\prime}_{7}\cup L^{\prime}_{10}\cup L^{\prime}_{11}]$ is
isomorphic to $C_{7}[K_{3}]$. Since $y+s<x-2$,
$|L_{2}|+|L_{8}|+|L_{9}|\leq\omega(G)-3$ and so $\omega(G-H)\leq\omega(G)-6$.
By the inductive hypothesis, $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$.
Therefore, $y+s\geq x-2$ and thus $z-s=(x+2)-(y+s)\leq 4$. It follows that
$z-4\leq s\leq 2$, i.e., $z\leq 6$. By symmetry, $y\leq 6$ and so $x\leq 10$.
We consider two cases depending on the parity of $x$.

Case 1. $x$ is odd.

For $i\in\\{1,2\\}$, let $L^{\prime}_{i}\subseteq L_{i}$ be a set of size
$t=\frac{x+1}{2}$ and let $v\in L_{8}$. Let

$H=G[L_{7}\cup L_{6}\cup L_{5}\cup L_{4}\cup L_{3}\cup L_{9}\cup
L^{\prime}_{1}\cup L^{\prime}_{2}\cup\\{v\\}].$

Note that $G-H$ is a perfect graph with $\omega(G-H)=x$. If $\chi(H)\leq
x+2+t$, then

$\displaystyle\chi(G)$ $\displaystyle\leq(x+2+t)+x$
$\displaystyle=\omega(G)+t$ $\displaystyle=\frac{5}{4}\omega(G).$

Since $x\in\\{5,7,9\\}$,
$\lfloor\frac{5}{4}\omega(G)\rfloor\leq\lceil\frac{7}{6}\omega(G)+1\rceil$ and
we are done.

Therefore, it remains to show $\chi(H)\leq x+2+t$. Note that
$\omega(H)=x+2+t$. We first show that

$(z+r)+(y+s)\leq(x+2)+(t-1)=\omega(H)-1.$ (2)

Recall that $r,s\leq 2$. If $x=9$, then $t=5$ and (2) holds. If $x=7$, then
$t=4$. If (2) does not hold, then $r=s=2$. Since $y-r,z-s\geq 3$, it follows
that $y,z\geq 5$ and so $y+z=10$. This contradiction that $y+z=x+2$. If $x=5$,
then $t=3$. If (2) does not hold, then $r+s\geq 3$. It follows that $y+z\geq
6+(r+s)>x+2$. Therefore, (2) is proved.

Now we show

$\text{There is a proper }\omega(H)\text{-coloring }\phi\text{ of
}L^{\prime}_{1}\cup L^{\prime}_{2}\cup L_{7}\cup L_{9}\cup\\{v\\}\text{ with
}\phi(L_{7})\cap\phi(L_{9})=\emptyset.$ (3)

We consider three cases.

If $y+s,z+r\leq t$,

$\bullet$ color the clique $L^{\prime}_{1}\cup L^{\prime}_{2}\cup\\{v\\}$
using $|L^{\prime}_{1}\cup L^{\prime}_{2}\cup\\{v\\}|\leq\omega(H)$ colors;

$\bullet$ color $L_{7}$ using the colors in $\phi(L^{\prime}_{2})$ and color
$L_{9}$ using the colors in $\phi(L^{\prime}_{1})$.

If $y+s\leq t,z+r\geq t$,

$\bullet$ color the clique $L^{\prime}_{1}\cup L_{7}\cup\\{v\\}$ using
$|L^{\prime}_{1}\cup L_{7}\cup\\{v\\}|\leq\omega(H)$ colors;

$\bullet$ color $L^{\prime}_{2}$ using the colors in $\phi(L_{7})$ and color
$L_{9}$ using the colors in $\phi(L^{\prime}_{1})$.

If $y+s,z+r\geq t$,

$\bullet$ color $L_{7}$ and $L_{9}$ with disjoint sets of colors. By (2), it
is possible to choose a color from $\\{1,2,\ldots,\omega(H)\\}$ to color $v$;

$\bullet$ color $L^{\prime}_{1}$ using the colors in $\phi(L_{9})$ and color
$L^{\prime}_{2}$ using the colors in $\phi(L_{7})$.

In all cases, $\phi$ is the desired coloring and (3) is proved.

Let $\phi$ be a coloring of $L^{\prime}_{1}\cup L^{\prime}_{2}\cup L_{7}\cup
L_{9}\cup\\{v\\}$ guaranteed by (3). We now extend $\phi$ to a coloring of $H$
as follows.

$\bullet$ Color $L_{6}$ with colors from
$\\{1,\ldots,\omega(H)\\}\setminus(\phi(L^{\prime}_{1})\cup\phi(L_{7}))$ and
color $L_{3}$ with colors from
$\\{1,\ldots,\omega(H)\\}\setminus(\phi(L^{\prime}_{2})\cup\phi(L_{9}))$.

$\bullet$ Color $L_{5}$ using $|L_{5}|$ colors from $\phi(L_{7})$ and color
$L_{4}$ using $|L_{4}|$ colors from $\phi(L_{9})$.

Since $|L_{7}|\geq|L_{5}|$, $|L_{9}|\geq|L_{4}|$ and
$\phi(L_{7})\cap\phi(L_{9})$ are disjoint, it follows that the above coloring
is a proper $\omega(H)$-coloring of $H$.

Case 2. $x$ is even.

Case 2.1 $x\in\\{4,6\\}$.

For $i\in\\{1,2\\}$, let $L^{\prime}_{i}\subseteq L_{i}$ be a set of size
$t=\frac{x}{2}+1$. Let

$H=G[L_{7}\cup L_{6}\cup L_{5}\cup L_{4}\cup L_{3}\cup L_{9}\cup
L^{\prime}_{1}\cup L^{\prime}_{2}].$

Note that $G-H$ is a perfect graph with $\omega(G-H)=x$. Moreover, $H$ is a
perfect graph with $\omega(H)=x+2+t$. Since $2x+2=\omega(G)$, it follows that

$\displaystyle\chi(G)$ $\displaystyle\leq(x+2+t)+x$
$\displaystyle=\frac{5}{4}\omega(G)+\frac{1}{2}.$

Since $x\in\\{4,6\\}$,
$\lfloor\frac{5}{4}\omega(G)+\frac{1}{2}\rfloor\leq\lceil\frac{7}{6}\omega(G)\rceil+1$.

Case 2.2 $x\in\\{8,10\\}$.

For $i\in\\{1,2\\}$, let $L^{\prime}_{i}\subseteq L_{i}$ be a set of size
$t=\frac{x}{2}$. Let

$H=G[L_{7}\cup L_{6}\cup L_{5}\cup L_{4}\cup L_{3}\cup L_{9}\cup
L^{\prime}_{1}\cup L^{\prime}_{2}\cup L_{8}].$

Note that $G-H$ is a perfect graph with $\omega(G-H)=x$. If $\chi(H)\leq
x+2+t$,

$\displaystyle\chi(G)$ $\displaystyle\leq(x+2+t)+x$
$\displaystyle=\lceil\frac{7}{6}\omega(G)\rceil+1.$

Therefore, it remains to show that $\chi(H)\leq x+2+t$. Since $r,s\leq 2$ and
$t=\frac{x}{2}\geq 4$, $(z+r)+(y+s)\leq\omega(H)$. Moreover, if
$(z+r)+(y+s)\geq\omega(H)-1$, then $r+s\geq 3$. Consequently, there is a
proper $\omega(H)$-coloring $\phi$ of $L^{\prime}_{1}\cup L^{\prime}_{2}\cup
L_{7}\cup L_{8}\cup L_{9}$ such that $|\phi(L_{7})\cap\phi(L_{9})|\leq 2$, and
if $|\phi(L_{7})\cap\phi(L_{9})|\geq 1$, then $r+s\geq 3$. Hence, it is easy
to see that one can extend $\phi$ to a proper coloring of $G$ by avoiding the
colors in $\phi(L_{7})\cap\phi(L_{9})$ on $L_{1}\cup L_{2}\cup L_{4}\cup
L_{5}$. ∎

######  Claim 4.

If an end triangle of a minimum vertex is not maximum, then
$\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$.

###### Proof.

Suppose that $\\{2,8,9\\}$ is not maximum. By Claim 2 and Claim 3,
$\\{1,2,8\\}$ and $\\{1,7,8\\}$ are maximum. It follows that $|L_{6}|=2$ and
$\\{1,6,7\\}$ are maximum. By Claim 2, $\\{6,7,11\\}$ are maximum. By Claim 1,
$\\{2,3,9\\}$ and $\\{4,5,10\\}$ are maximum. Since $|L_{6}|=\min$,
$|L_{4}|+|L_{5}|+|L_{11}|\geq|L_{6}|+|L_{5}|+|L_{11}|$ and so $\\{4,5,11\\}$
is maximum by Claim 1.

Suppose first that $\\{3,9,10\\}$ is maximum. It follows that
$|L_{1}|=|L_{2}|=|L_{7}|=|L_{10}|=|L_{11}|$. Let $x=|L_{1}|$. Note that
$\omega(G)=2x+2$, $|L_{4}|+|L_{5}|=x+2$ and $|L_{3}|+|L_{9}|=x+2$. Then
$G-(L_{6}\cup L_{8})$ is isomorphic to the graph $G_{x}$ in Figure 7. By Lemma
11,

$\displaystyle\chi(G)$ $\displaystyle\leq\lceil\frac{7}{6}(2x+1)\rceil+2$
$\displaystyle=\lceil\frac{7}{6}(\omega(G)-1)\rceil+2$
$\displaystyle\leq\lceil\frac{7}{6}\omega(G)\rceil+1.$

Now suppose that $\\{3,9,10\\}$ is not maximum. By Claim 3, 9 is not a minimum
vertex and so $|L_{9}|\geq 3$. By Claim 1, $\\{3,4,10\\}$ is maximum and so
$|L_{4}|>|L_{9}|\geq 3$. This implies that $\\{5,6,11\\}$ is not maximum. Now
$\\{2,4,7\\}$ is a strong stable set, a contradiction. ∎

By Claim 2 and Claim 4, every triangle containing a minimum vertex is maximum.
This implies that $G=E[K_{2}]$, a contradiction. ∎

We now show that Theorem 4 is true for blowups $G$ of the emerald with
$p(G)\leq 2$.

######  Lemma 13.

If $G$ is a blowup of the emerald and $p(G)\leq 2$, then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

###### Proof.

By Lemma 12, $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil+1$. Note that
$\lceil\frac{7}{6}\omega(G)\rceil+1\leq\lceil\frac{11}{9}\omega(G)\rceil$
unless $\omega(G)\in\\{3,4,7,8,9,13\\}$. Next we show directly that
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$ when
$\omega(G)\in\\{3,4,7,8,9,13\\}$. Moreover, $p(G)\geq 1$ by Lemma 10.

Case 1. $\omega(G)=3$. It follows that $G=E$ and
$\chi(G)=4=\lceil\frac{11}{9}\omega(G)\rceil$.

Case 2. $\omega(G)=4$. Let $I$ be the set of vertices $i$ such that
$|L_{i}|=2$. Since $1\leq|L_{i}|\leq 2$ for each $i\in V(E)$, $I$ is a stable
set of $E$. For each $i\in I$, take a vertex $u_{i}\in L_{i}$ and let $S$ be
the union of those vertices. Note that $G-S=E$. It follows that $\chi(G)\leq
5=\lceil\frac{11}{9}\omega(G)\rceil$.

Case 3. $\omega(G)\in\\{7,8\\}$. Note that
$\lceil\frac{11}{9}\omega(G)\rceil=\omega(G)+2$. A vertex $i\in V(E)$ is said
to be a $t$-vertex if $|L_{i}|=t$. Since each $L_{i}$ is nonempty, $G$ has no
$i$-vertex for $i\geq\omega(G)-1$. We now prove the following.

######  Claim 5.

If $G$ has an $i$-vertex where
$i\in\\{\omega(G)-4,\omega(G)-3,\omega(G)-2\\}$, then
$\chi(G)\leq\omega(G)+2$.

###### Proof.

By symmetry, assume that
$|L_{8}|=i\in\\{\omega(G)-4,\omega(G)-3,\omega(G)-2\\}$. It follows that
$|L_{1}|+|L_{7}|\leq 4$ and $|L_{2}|+|L_{9}|\leq 4$. Suppose first that
$|L_{1}|=1$. Take a vertex $u_{i}\in L_{i}$ for each $i\in\\{1,2,7,9\\}$. Let
$S=\\{u_{1},u_{2},u_{7},u_{9}\\}$ and $G^{\prime}=G-S$. Note that
$d_{G^{\prime}}(v)\leq\omega(G)-1$ for each $v\in L_{8}$. Therefore,
$G^{\prime}$ is $\omega(G)$-colorable if and only if $G^{\prime}-L_{8}$ is.
Since $G^{\prime}-L_{8}$ is perfect,
$\chi(G^{\prime}-L_{8})=\omega(G^{\prime}-L_{8})\leq\omega(G)$. This implies
that $\chi(G)\leq\chi(G^{\prime})+2\leq\omega(G)+2$.

Now suppose that $|L_{1}|,|L_{2}|\geq 2$. So $i=\omega(G)-4$ and
$|L_{1}|=|L_{2}|=2$. If $|L_{7}|=|L_{9}|=1$, then for every $v\in L_{8}$,
$d_{G}(v)=\omega(G)+1$. So $G$ is $\omega(G)+2$-colorable if and only if
$G-L_{8}$ is. By Lemma 10,
$\chi(G-L_{8})\leq\lceil\frac{7}{6}\omega(G)\rceil=\omega(G)+2$ and thus
$\chi(G)\leq\omega(G)+2$. Therefore, we may assume that $|L_{7}|\geq 2$. Let
$L^{\prime}_{7}\subseteq L_{7}$ be a set of size 2. Let
$G^{\prime}=G-(L_{2}\cup L^{\prime}_{7})$. For every $v\in L_{8}$,
$d_{G^{\prime}}(v)\leq\omega(G)-1$. Since $G^{\prime}-L_{8}$ is perfect,
$\chi(G^{\prime})\leq\omega(G)$ and thus $\chi(G^{\prime})\leq\omega(G)$. This
implies that $\chi(G)\leq\omega(G)+2$. ∎

By Claim 5, we may assume that $G$ has no $i$-vertex for $i\geq\omega(G)-4$.
If $\omega(G)=7$, then $|L_{i}|\leq 2$ for every $i\in V(E)$ by Claim 5. This
implies that $\omega(G)\leq 6$, a contradiction. So $\omega(G)=8$. Since the
lemma holds for any graph $G^{\prime}$ with $\omega(G^{\prime})=7$, We may
assume that $G$ has no strong stable set.

######  Claim 6.

If $G$ has a 3-vertex, $\chi(G)\leq 10$.

###### Proof.

By symmetry, assume that $|L_{8}|=3$. Since $\omega(G)=8$,
$|L_{1}|+|L_{7}|\leq 5$ and $|L_{2}|+|L_{9}|\leq 5$. Let $v\in L_{8}$. If
$|N_{G}[v]|\leq 10$, we are done. So assume that $|N_{G}[v]|\geq 11$. By
symmetry, $(|L_{1}|+|L_{7}|,|L_{2}|+|L_{9}|)\in\\{(5,5),(5,4),(5,3),(4,4)\\}$.
Suppose first that $(|L_{1}|+|L_{7}|,|L_{2}|+|L_{9}|)\neq(5,5)$. Note that
$|N_{G}[v]|\leq 12$ for any $v\in L_{8}$. Similar to the proof of Claim 5,
$|L_{1}|,|L_{2}|\geq 2$. If $|L_{1}|=|L_{2}|=2$, then one of $|L_{7}|$ and
$|L_{9}|$ is of size at least 2, say $|L_{7}|$. Then $G-(L_{2}\cup L_{7})$ is
8-colorable and so $\chi(G)\leq 10$. Now by symmetry $|L_{1}|=3$ and
$|L_{2}|=2$. If $|L_{7}|\geq 2$, then $G-(L_{2}\cup L_{7})$ is 8-colorable and
so $\chi(G)\leq 10$. So $|L_{7}|=1$ and thus
$|L_{1}|+|L_{7}|+|L_{8}|=7<\omega(G)$. Since $G$ has no strong stable set,
$\\{1,6,7\\}$ must be maximum and so $|L_{6}|=4$, a contradiction.

Now assume that $|L_{1}|+|L_{7}|=5$ and $|L_{2}|+|L_{9}|=5$. Since $G$ has no
4-vertex, no $L_{i}$ is of size 1 for $i\in\\{1,2,7,9\\}$. By symmetry,
$(|L_{7}|,|L_{1}|,|L_{2}|,|L_{9}|)\in\\{(2,3,2,3),(3,2,2,3)\\}$. Suppose first
that $(|L_{7}|,|L_{1}|,|L_{2}|,|L_{9}|)=(2,3,2,3)$. Since 1 is a 3-vertex,
$|L_{6}|=3$. Suppose that $|L_{3}|=2$. Since $|L_{9}|=3$, it follows that
$|L_{10}|=3$. Since $\\{2,3,9\\}$ is not maximum, $\\{4,5,11\\}$ is maximum.
It follows that $|L_{4}|=3$. The fact that $\omega(G)=8$ implies that
$|L_{11}|=3$ and $|L_{5}|=2$. Let $S=L_{2}\cup L_{5}\cup L_{7}$. It is easy to
see that $\chi(G-S)=8$ (by modulo 8 coloring) and so $\chi(G)\leq 10$. Now
suppose that $|L_{3}|=3$. Since $|L_{2}|=2$ and $|L_{9}|=3$, $|L_{10}|=2$ and
$|L_{4}|=3$. Moreover, $(|L_{11}|,|L_{5}|)\in\\{(2,3),(3,2)\\}$. In either
case, it is easy to see $\chi(G)\leq 10$. So far we have proved that for every
3-vertex $i$, the neighbors of $i$ must have sizes $(3,2,2,3)$. It then
implies that $|L_{4}|=2$ and $|L_{4}|=3$, a contradiction. ∎

Now $|L_{i}|\leq 2$ for each $i\in V(E)$. This shows that $\omega(G)\leq 6$, a
contradiction. This completes the proof for $\omega(G)=8$.

Case 4. $\omega(G)\in\\{9,13\\}$. Since the lemma holds for graphs with clique
number $\in\\{8,12\\}$, we may assume that $G$ has no strong stable set.
Similar to the proof of Lemma 12, the following two claims hold.

######  Claim 7.

If a triangle in the emerald is not maximum, then any triangle of distance 1
or 4 to that triangle is maximum.

######  Claim 8.

The middle triangle of a minimum vertex must be maximum.

Now we prove the statements analogous to Claim 3 and Claim 4.

######  Claim 9.

If both end triangle of a minimum vertex are not maximum, then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

###### Proof.

Suppose that $|L_{8}|=p$. By Claim 8, $T=\\{1,2,8\\}$ is maximum. Suppose that
$\\{1,7,8\\}$ and $\\{2,8,9\\}$ are not maximum. By Claim 7,

$\displaystyle\text{ triangles
}\\{2,3,9\\},\\{1,6,7\\},\\{3,9,10\\},\\{6,7,11\\},\\{4,5,10\\},\\{4,5,11\\}\text{
are maximum.}$

Then $L_{1},L_{2},L_{4},L_{5}$ have the same size, say $x$. Note that
$\omega(G)=2x+p$. Since $\omega(G)$ is odd, $p=1$ and
$x=\frac{\omega(G)-1}{2}$. Let $|L_{4}|=y$ and $|L_{5}|=z$. Then $y+z=x+1$ and
$G$ is the graph shown in Figure 8, where $r,s$ are nonnegative integers. It
is easy to show that $\chi(G)\leq 11$ if $\omega(G)=9$ and $\chi(G)\leq 16$ if
$\omega(G)=13$. ∎

######  Claim 10.

If one end triangle of a minimum vertex is not maximum, then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

###### Proof.

Suppose that 8 is a minimum vertex and $\\{2,8,9\\}$ is not maximum. By Claim
8 and Claim 9, $\\{1,2,8\\}$ and $\\{1,7,8\\}$ are maximum. It follows that
$|L_{6}|=p$ and $\\{1,6,7\\}$ are maximum. By Claim 8, $\\{6,7,11\\}$ are
maximum. By Claim 7, $\\{2,3,9\\}$ and $\\{4,5,10\\}$ are maximum. Since
$|L_{6}|=p$, $|L_{4}|+|L_{5}|+|L_{11}|\geq|L_{6}|+|L_{5}|+|L_{11}|$. By Claim
7, $\\{4,5,11\\}$ is maximum.

If $\\{3,9,10\\}$ is maximum, then $|L_{1}|=|L_{2}|=|L_{10}|=|L_{11}|=x$,
$\omega(G)=2x+p$, and so $p=1$. Moreover, $|L_{4}|+|L_{5}|=x+1$ and
$|L_{3}|+|L_{9}|=x+1$. Then $G-(L_{6}\cup L_{8})$ is isomorphic to a blowup of
the graph in Figure 9 with $x\in\\{4,6\\}$. It is easy to verify that
$\chi(G-(L_{6}\cup L_{8}))\leq\lceil\frac{11}{9}\omega(G)\rceil-1$. So
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$. Now $\\{3,9,10\\}$ is not
maximum. By Claim 9, $|L_{9}|>p$. By Claim 7, $\\{3,4,10\\}$ is maximum and
thus $|L_{4}|\geq|L_{9}|>p=|L_{6}|$. So $\\{5,6,11\\}$ is not maximum. Now
$\\{2,4,7\\}$ is a strong stable set, a contradiction. ∎

Now every triangle containing a minimum vertex is maximum. This implies that
$G=E[K_{p}]$ and so $\omega(G)\leq 6$. This is a contradiction. This completes
the proof of Case 4 and hence the lemma. ∎

1$x$23$x$4$x$5$x$6$x$7$t_{7}$$t_{2}$$x+1$$x+1$$\leq x+1$ Figure 9: A blowup of
a 9-vertex graph, where $|L_{i}|=x$ for $i\in\\{1,3,4,5,6\\}$,
$|L_{7}|+|L_{t_{7}}|=|L_{2}|+|L_{t_{2}}|=x+1$ and $|L_{t_{7}}|+|L_{t_{2}}|\leq
x+1$.

######  Lemma 14 (Equal-size blowup of the emerald).

$\chi(E[K_{3}])=11$.

###### Proof.

Let $G=E[K_{3}]$. Since $|G|=33$ and $\alpha(G)=3$, $\chi(G)\geq 11$. Next we
show that $\chi(G)\leq 11$. Observe that an 11-coloring of $G$ is equivalent
to a set of 11 stable sets of size 3 such that each vertex of the emerald (see
Figure 1) is contained in exactly three stable sets. It is routine to verify
that the following is a desired set of 11 stable sets:

$\displaystyle\\{1,3,5\\},\\{2,5,7\\},\\{4,9,11\\},\\{1,3,11\\},$
$\displaystyle\\{3,6,8\\},\\{6,8,10\\},\\{2,4,6\\},\\{4,7,9\\},$
$\displaystyle\\{1,5,9\\},\\{2,7,10\\},\\{8,10,11\\}.$

This completes the proof. ∎

Now we show Theorem 4 for blowups $G$ of the emerald with $p(G)\geq 3$.

######  Lemma 15.

If $G$ is a blowup of the emerald with $p(G)\geq 3$, then
$\chi(G)\leq\lceil\frac{11}{9}\omega(G)\rceil$.

###### Proof.

We prove by induction on $|G|$. The base case is $G=E[K_{3}]$ and the lemma
holds. So we assume that the lemma holds for every blowup of the emerald
$G^{\prime}$ with $p(G^{\prime})\geq 3$ and $|G^{\prime}|<|G|$. For each $u\in
V(E)$, let $L^{\prime}_{u}\subseteq L_{u}$ be a set of size 3 and
$H=G[\bigcup_{u\in V(E)}L^{\prime}_{u}]$. Then $H=E[K_{3}]$ and
$G^{\prime}:=G-H$ is a blowup of the emerald. If $p(G^{\prime})\leq 2$, then
$\chi(G^{\prime})\leq\lceil\frac{11}{9}\omega(G^{\prime})\rceil$ by Lemma 13.
If $p(G^{\prime})\geq 3$, then
$\chi(G^{\prime})\leq\lceil\frac{11}{9}\omega(G^{\prime})\rceil$ by the
inductive hypothesis. Since $\omega(G^{\prime})\leq\omega(G)-9$, it follows
from Lemma 14 that

$\displaystyle\chi(G)$ $\displaystyle\leq\chi(G^{\prime})+\chi(H)$
$\displaystyle\leq\lceil\frac{11}{9}(\omega(G)-9)\rceil+11$
$\displaystyle=\lceil\frac{11}{9}\omega(G)\rceil.$

This completes the proof. ∎

Finally, we are ready to prove Theorem 4.

###### Proof of Theorem 4.

It follows directly from Lemma 13 and Lemma 15 ∎

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph Theory.  Springer, 2008.
  * [2] A. Brandstädt, T. Klembt, and S. Mahfud.  $P_{6}$\- and triangle-free graphs revisited: structure and bounded clique-width.  Discrete Mathematics and Theoretical Computer Science, 8:173–188, 2006.
  * [3] M. Briański, J. Davies, and B. Walczak.  Separating polynomial $\chi$-boundedness from $\chi$-boundedness.  arXiv:2201.08814v2 [math.CO], 2022.
  * [4] K. Cameron, S. Huang, I. Penev, and V. Sivaraman.  The class of $({P}_{7},{C}_{4},{C}_{5})$-free graphs: Decomposition, algorithms, and $\chi$-boundedness.  Journal of Graph Theory, 93:503–552, 2020.
  * [5] S. A. Choudum, T. Karthick, and M. A. Shalu.  Perfectly coloring and linearly $\chi$-bound $P_{6}$-free graphs.  J. Graph Theory, 54:293–306, 2007.
  * [6] S. Gravier, C. T. Hoàng, and F. Maffray.  Coloring the hypergraph of maximal cliques of a graph with no long path.  Discrete Math., 272:285–290, 2003.
  * [7] A. Gyárfás.  On Ramsey covering numbers.  Coll. Math. Soc. János Bolyai, 10:801–816, 1973.
  * [8] A. Gyárfás.  Problems from the world surrounding perfect graphs.  Zastosowania Matematyki, XIX:413–441, 1987.
  * [9] T. Karthick and F. Maffray.  Square-free graphs with no six-vertex induced path.  SIAM J. Discrete Math., 33:874–909, 2019.
  * [10] L. Lovász.  A characterization of perfect graphs.  Journal of Combinatorial Theory, Series B, 13:95–98, 1972.
  * [11] A. Scott, P. Seymour, and S. Spirkl.  Polynomial bounds for chromatic number. IV. a near-polynomial bound for excluding the five-vertex path.  Combinatorica, to appear, 2022.
  * [12] G. J. Woeginger and J. Sgall.  The complexity of coloring graphs without long induced paths.  Acta Cybernetica, 15:107–117, 2001.