# Graph Mining under Data scarcity

Appan Rakaraddi  Nanyang Technological University
Singapore
<EMAIL_ADDRESS>Lam Siew-Kei  Nanyang Technological University
Singapore
<EMAIL_ADDRESS>Mahardhika Pratama  University of South Australia
Australia
<EMAIL_ADDRESS>Marcus de Carvalho  Nanyang Technological
University
Singapore
<EMAIL_ADDRESS>
###### Abstract

Multitude of deep learning models have been proposed for node classification
in graphs. However, they tend to perform poorly under labeled-data scarcity.
Although Few-shot learning for graphs has been introduced to overcome this
problem, the existing models are not easily adaptable for generic graph
learning frameworks like Graph Neural Networks (GNNs). Our work proposes an
Uncertainty Estimator framework that can be applied on top of any generic GNN
backbone network (which are typically designed for supervised/semi-supervised
node classification) to improve the node classification performance. A neural
network is used to model the Uncertainty Estimator as a probability
distribution rather than probabilistic discrete scalar values. We train these
models under the classic episodic learning paradigm in the $n$-way, $k$-shot
fashion, in an end-to-end setting.

Our work demonstrates that implementation of the uncertainty estimator on a
GNN backbone network improves the classification accuracy under Few-shot
setting without any meta-learning specific architecture. We conduct
experiments on multiple datasets under different Few-shot settings and
different GNN-based backbone networks. Our method outperforms the baselines,
which demonstrates the efficacy of the Uncertainty Estimator for Few-shot node
classification on graphs with a GNN.

###### Index Terms:

Data scarcity, Uncertainty, Graph Neural Networks

##  I Introduction

Graphs are among the most ubiquitous form of data representation that are not
constrained by the Euclidean geometry; and hence development of algorithms for
graph mining is an active research area [37]. Plethora of deep learning
frameworks specifically crafted for graph-type topological structures, classed
together as Graph Neural Networks (GNNs) [24, 11] have found applications in
many domains like physics [18], chemistry [2], Computer vision [28, 15],
Natural Language Processing [1], Transfer/Continual learning [21, 17], and
many other wide-range of areas [26, 16]. But the most popular flavours of GNNs
require copious amount of labeled training data for model generalization on
unseen tasks, which raises a barrier for training the model on many real-world
applications.

Scarcity of labeled training data for tuning the neural network models
pioneered the research in Few-shot learning [6, 19, 20] to optimize the model
with a relatively limited number of training data samples. Although these
methods were originally proposed for image and language-based data
classification, they have subsequently been extended to the graph domain with
suitable adaptations. Three types of Few-shot learning on graphs include: node
classification, edge classification and graph classification [34]. We focus
specifically on node classification in this work. The existing works for node
classification under Few-shot settings [36, 9, 13, 25, 3] use metric learning,
optimization-based learning and hybrid architectures.

Metric learning based methods [3, 31] map the raw data into an embedding
space, and similarity measure such as the Euclidean distance or the Cosine
Similarity compares the embedding distance between the support and query node
embeddings for node classification. Optimization-based learning methods [36,
13] primarily leverage meta-learning approaches like MAML [6], which is a
model-agnostic task optimizer that can adapt to unseen tasks with the multi-
level gradient descent during the training. The hybrid architectures [25, 9]
use a combination of the aforementioned methods to account for other graph
topological information. Despite showing great performance under labeled-data
scarcity conditions, these models use a specialised/specific architecture that
cannot be easily adapted in combination with generic semi-supervised learning
models. For example, let’s consider a scenario where we are training a graph
learning model for node classification across a series of $n$ tasks i.e.,
$\\{\mathcal{T}_{1},\mathcal{T}_{2},...,\mathcal{T}_{n}\\}$ with all tasks
having sufficiently labelled data, except for some task $\mathcal{T}_{i}\
(i\in[1,n])$. It may become computationally expensive and impractical to build
a new model specifically for the task $\mathcal{T}_{i}$ under Few-shot
settings, especially if the model has a lot of trainable parameters.

To mitigate this, our work proposes an additional training module called
Uncertainty on Graph Networks (UGN), that can be applied on top of any generic
base model, which can be trained under Few-shot settings for the data-scarce
task. This eliminates the need to develop an extensive model for data-scarce
conditions, which leads to a more resource-efficient model. The data scarce
task has a classification uncertainty arising with it and may lead to
overfitting. Also, the common issue with overfitting is high variance values
in the classification predictions between the training and the test sets. The
UGN module which is applied on top of the base model estimates the class
prediction uncertainty, which can effectively reduce overfitting problem.

In summary, our work presents an uncertainty estimator framework called UGN
for node classification on graphs under labeled training data scarcity, which
can be applied on top of any generic graph embedding/GNN model to improve the
classification accuracy. Although there are some existing works on uncertainty
estimation [35, 32], to the best of our knowledge, our work is the first to
extend this method to graphs for node classification. Our contributions are
listed as follows:

  * •

We propose an uncertainty estimator framework called UGN for Few-shot node
classification, that can be applied on top of any generic GNN for meta-
learning.

  * •

We conduct experiments on multiple datasets under different Few-shot settings
as well as on different GNN variants to demonstrate the model adaptability and
scalability.

  * •

Our model outperforms the baseline methods, which demonstrates its
effectiveness over the state-of-the-art.

##  II Related Work

In this section, we review the literature that are relevant to our work.

###  II-A Graph Neural Networks

The most common variant of graph learning methods are the Graph Neural
Networks (GNNs), which map a graph’s node and edge features into a low
dimensional space, enabling a cost-efficient data mining. The most common form
of GNNs are the message-passing GNNs (MP-GNNs) like GCN [12], GraphSAGE [8],
GAT [24], SGC [29], GIN [30] and many other frameworks. These MP-GNNs differ
from each other depending on the way the nodes and edges features are gathered
and mixed together. Apart from the MP-GNNs, other methods have been proposed
based on the WL-test [10], which have proven to be more effective than the
simple MP-GNNs. This is so because MP-GNNs in certain cases have failed to
distinguish 2 different graphs and have produced the same feature
representations for both of them[30]. GNNs have also deployed transformers-
based framework [23] to accommodate the graph heterogeneity [33]. Also, the
incorporation of the positional/structural encoding [4] in the GNNs has been
shown to produce higher quality embedding.

###  II-B Few-shot Learning on Graphs

Meta-GNN [36] proposes a method for Few-shot node classification using MAML
[6] for graph-structured data. Graph Prototypical Networks (GPN) [3] is
another method proposed for Few-shot node classification with two components
connected back-to-back: Network Encoder and Network Valuator. The Network
Encoder generates the node representation embeddings using GNNs, while the
Network Valuator estimates the node importance scores through a score
aggregation layer. This entire network is optimized via Metric-learning
similar to the Prototypical Networks [19]. G-Meta [9] performs Few-shot node
classification by converting every node in the graph into a subgraph from the
local neighbouring nodes. These embeddings of the subgraphs are used to
generate the class prototypes and this model is optimized via MAML [6].

###  II-C Uncertainty Learning

Uncertainty-based learning has gained traction for dealing with scarce data-
samples classification tasks. UAFS [35] proposed an uncertainty based method
for estimating the classification uncertainty in Few-shot learning for image
data. It utilizes a GNN to model the probability uncertainty as a Gaussian
distribution. UCN [32] proposes an uncertainty modeling of the classification
outputs of the images using mutual information between the augmented query
sample scores. The support and query sets are data augmented with $m$
different augmentation variants, and the query instance’s classification
probability are calculated using a metric-based approach for each of the
augmentation. The uncertainty associated with the classification is modeled
via Shannon-entropy function.

##  III Preliminaries

Given a graph $\mathcal{G}(V,E,X,C)$, let $V\in\mathbb{R}^{|V|}$ represent the
set of nodes, $E\in\mathbb{R}^{|V|\times|V|}$ denote the edge set,
$X\in\mathbb{R}^{|V|\times d}$ represent the node features matrix and
$C\in\mathbb{R}^{|V|}$ represent the set of node classes.

Problem statement:  The node classes $C=C_{train}\cup C_{novel}$ is split into
$C_{train}$ (nodes seen during meta-training stage) and $C_{novel}$ (nodes
seen during meta-testing stage) such that $C_{train}\cap C_{novel}=\emptyset$.
The objective of Few-shot node classification is to train the model on the
sufficiently labeled $C_{train}$ classes and adapting it to classify the
sparsely labeled $C_{novel}$ classes. Episodic learning is a popular paradigm
employed for this training, where the model training is transformed as a
series of tasks called episodes. In each episode, the classes are sampled from
the $C_{train}$ and $C_{novel}$ sets during the meta-training and meta-testing
stages respectively. Each episode $i$ is split into support set $\mathcal{S}$
and query set $\mathcal{Q}$. The support set $\mathcal{S}$ consists of $n$
classes with $k$ node samples from each class, and the query set $\mathcal{Q}$
consists of the same $n$ classes with $m$ node samples from each of the $n$
classes. This is called n-way k-shot learning.

Let $\mathcal{S}_{j}$ represent the set of nodes belonging to the class $j$ in
the support set $\mathcal{S}$. Then given a graph embedding network (e.g., a
GNN) $f_{\theta}(.)$ with parameters $\theta$, the class prototype embedding
of class $j$ is represented as:

$c_{j}=\frac{1}{|\mathcal{S}_{j}|}\sum_{u\in\mathcal{S}_{j}}f_{\theta}(u)$ (1)

where $|\mathcal{S}_{j}|$ depicts the number of support node samples belonging
to class $j$. So in Metric-based learning, the probability of a query node $x$
belonging to the class $j$ is defined as:

$p(j|x)=\frac{\exp\big{(}-d(f_{\theta}(x),c_{j})\big{)}}{\sum_{i}^{n}\exp\big{(}-d(f_{\theta}(x),c_{i})\big{)}}$
(2)

where $d(.)$ is a distance metric function like the Euclidean distance measure
or the Cosine distance measure. The distance function is also often
substituted with the similarity function $sim(.)$ (such as Cosine similarity)
with appropriate sign change. This is written as:

$p(j|x)=\frac{\exp\big{(}sim(f_{\theta}(x),c_{j})\big{)}}{\sum\limits_{i=1}^{n}\exp\big{(}sim(f_{\theta}(x),c_{i})\big{)}}$
(3)

In our work, we use the Cosine similarity for the similarity function
$sim(.)$.

##  IV Model Architecture

Figure 1: Model architecture of UGN: The graph is fed into the encoder, which
is a generic MP-GNN model to generate the node embedding. The embedding is fed
into the UGN layer to generate the class prototype similarity graph for each
of the $m$ query samples. The deployment of the UGN layer to generate a
probability distribution instead of training the model based on just on the
Encoder probability outputs increases the average classification accuracy
under labeled data scarcity conditions.

Our model UGN comprises of two cascaded components: Encoder and Uncertainty
Estimator.

###  IV-A Encoder

In our work, we have used a MP-GNN to embed the node features. We designed the
Encoder as the backbone network with different variants of GNNs. For a given
node $u$, the MP-GNN iteratively aggregates features of its neighbouring
nodes, given by $\mathcal{N}(u)$, and combines them together to generate the
node $u$’s new embedded feature representation in the low-dimensional space.
This is formally expressed as:

$\textbf{h}_{u}^{(k)}=\text{{{\footnotesize
UPDATE}}}\left(\textbf{h}_{u}^{(k-1)},\text{\footnotesize{AGGREGATE}}\left(\\{\textbf{h}_{v}^{(k-1)},\
\forall v\in\mathcal{N}(u)\\}\right)\right)$

where $\textbf{h}_{u}^{(k)}$ represents the node embedding representation
after $k$ iterations, AGGREGATE and UPDATE represent the functions which
gather the neighbouring node features and integrate into $u$ respectively. We
represent the Encoder function as $f_{\theta}(.)$ and the embedding of a node
$u$ as $f_{\theta}(u)$.

As mentioned earlier, these embedding methods are designed for supervised
learning settings in the presence of sufficient amount of data and generally
perform poorly under labeled-data scarcity conditions. The Uncertainty
Estimator which is added on top of the Encoder is discussed in the following
section.

###  IV-B Uncertainty Estimator

Our framework adopts a similar direction as UAFS [35], which was designed for
meta-learning with uncertainty estimator on image data.

To counteract the classification uncertainty in the model predictions due to
data scarcity, the output of the Encoder which maps the nodes to their
respective classes, is represented as probability distribution instead of
probabilistic scalar values. This is achieved by coupling the output of the
Encoder with the input of the Uncertainty Estimator module. We model the
likelihood of a query node $x$ belonging to a class $j$ as a Gaussian
distribution. This assumption is valid since the class-query pairs with the
highest similarity values will have the highest probability value and the
lower similarity values will be spread apart as deviations from the mean
value.

Hence, the probability of the query node $x$ belonging to the class $j$
represented in the form of Gaussian distribution is formulated as:

$p(j|x)\sim\mathcal{N}(\mu_{(x,c_{j})},\,\sigma_{(x,c_{j})})\ $ (4)

where $\sigma_{(x,c_{j})}$ is the Standard Deviation that depicts the
uncertainty in the classification prediction of the query node $x$ to the
class $j$. The mean value $\mu_{(x,c_{j})}$ is the fixed scalar similarity
value between the query node embedding and the class prototype $c_{j}$,
expressed as:

$\mu_{(x,c_{j})}=sim(f_{\theta}(x),c_{j})$

The analytic expression represented in Equation 4 is hard to estimate
practically. So, we consider multiple discrete samples to approximate the
Gaussian distribution via Monte-Carlo methods that can easily be modeled by a
neural network $g_{\phi}(.)$. Each sample represents the similarity value
between a query embedding $f_{\theta}(x)$ and the class prototype $c_{j}$,
with $T$ number of samples obtained for each of the pairs. The
$sim_{(x,c_{j})}$ associated with the $t$-th sample is given by:

$sim_{(x,c_{j},t)}=\mu_{(x,c_{j})}+\sigma_{(x,c_{j})}\epsilon_{t},\quad\epsilon_{t}\in\mathcal{N}(0,1)$
(5)

###  IV-C Deviation Determination

Since the probabilistic uncertainty of a query $x$ belonging to a class $j$
also depends on the probabilistic uncertainty of $x$ belonging to class $i$
(as the uncertainty associated with the classification of a node may overlap
with another node’s uncertainty), it is convenient to model the
interdependence of the uncertainties as a graph. The uncertainty of $x$
belonging to a class $j$, i.e., $\sigma_{(x,c_{j})}$, is calculated between a
query and each class prototype, where a node $j_{x}$ represents the Standard
Deviation between the query sample $x$ and the class prototype $c_{j}$. To
exploit this graph type structure, the neural network $g_{\phi}(.)$ is modeled
using a GNN (in our case, we have used a GCN). We split the query embedding
$f_{\theta}(x)$ and class prototype into $L$ equal parts. The feature vector
of a class prototype node $j_{x}$ is constructed by taking the inner dot
product between each of the $L$ pairs of the query embedding $f_{\theta}(x)$
and the class prototype $c_{j}\in[1,n]$ to generate the relational-similarity
vector $\textbf{F}\in R^{n\times L}$. The edges of the graph determine the
similarity between two class prototype nodes. Following the earlier works [27,
35], we construct an edge between each pair of class prototype nodes $i_{x}$
and $j_{x}$ as:

$E(i_{x},j_{x})=\phi^{\prime}(\textbf{F})^{T}\phi(\textbf{F})$ (6)

where $\phi(.)$ and $\phi^{\prime}(.)$ are linear neural networks. The
constructed graph is passed through a 2-layer GCN $g_{\phi}(.)$ to map the
query sample $x$ and the class prototype pairings to their corresponding
Standard Deviation values.

###  IV-D Effective Similarity

To calculate the effective similarity between a query and node prototype
pairing, the mean of the normalized similarity scores is calculated. This is
represented as:

$\textbf{sim}_{(x,c_{j})}={\frac{1}{T}{\sum_{t=1}^{T}}}\left(\frac{\exp\big{(}sim_{(x,c_{j},t)}\big{)}}{{\sum_{i}^{n}}\exp\big{(}sim_{(x,c_{i},t)})}\right)$
(7)

Equation 7 is optimized via the Negative Log Loss function during joint
training of the Encoder and the Uncertainty Estimator. The entire model
consisting of the Encoder and UGN is jointly trained in an end-to-end manner
as shown in Figure 1.

##  V Experiments

We have compared our model against GCN [12], GraphSAGE [8], GAT [24], GIN
[30], SGC [29] and APPNP [7] as base models and implemented the uncertainty
layer UGN on top of these methods. All of these are trained and tested under
the $n-$way $k-$shot paradigm. As mentioned in the introductory section, we
have not compared our methods to the Few-shot specific architectures since the
advantage of using our method lies in its adaptability with any generic base
GNN architecture (that can be a part of other tasks or be a standalone task),
unlike the Few-shot methods that rely on more specialised frameworks.

TABLE I: Dataset properties and task-splitting

Dataset | Nodes # | Edges # | Features # | Classes # |  | Train/Val
---
/Test
Amazon clothing | 24,919 | 91,680 | 9,034 | 77 | 40/17/20
Amazon-Electronics | 42,318 | 43,556 | 8,669 | 167 | 90/37/40
DBLP | 40,672 | 288,270 | 7,202 | 137 | 80/27/30

We used 3 different datasets for comparison which are described below:

TABLE II: Average Accuracy values (in %) of baseline methods on different
datasets. The bold values indicate the highest accuracy values in a column.

| Amazon electronics | DBLP | Amazon clothing
---|---|---|---
| 5-way 3-shot | 5-way 5-shot | 5-way 3-shot | 5-way 5-shot | 5-way 3-shot | 5-way 5-shot
GCN | 36.7 | 25.4 | 35.0 | 23.9 | 35.3 | 27.1
GraphSAGE | 29.9 | 23.0 | 36.2 | 28.1 | 38.7 | 28.7
GAT | 32.3 | 27.0 | 57.6 | 25.5 | 58.3 | 27.2
GIN | 26.6 | 22.2 | 20.0 | 21.8 | 28.6 | 25.4
SGC | 38.6 | 26.5 | 41.5 | 27.3 | 46.9 | 31.0
APPNP | 40.6 | 30.6 | 50.4 | 44.0 | 47.2 | 43.7
UGN-GCN | 49.1 | 51.5 | 49.2 | 52.0 | 54.8 | 47.0
UGN-GraphSAGE | 46.6 | 49.7 | 54.0 | 53.8 | 47.9 | 46.7
UGN-GAT | 49.0 | 47.9 | 58.4 | 59.3 | 38.3 | 41.6
UGN-GIN | 35.4 | 24.7 | 25.6 | 21.4 | 25.9 | 20.7
UGN-SGC | 43.4 | 43.9 | 50.6 | 42.4 | 53.7 | 47.6
UGN-APPNP | 48.1 | 47.2 | 28.8 | 33.9 | 49.9 | 42.5

  * •

Amazon clothing: [14] This dataset is derived from the Amazon products
subcategory of ”Clothing, Shoes and Jewelry”, where the nodes represent the
products, and an edge exists between a pair of nodes $(u,v)$ if a user who
views product $u$ also views product $v$. The product review is described by
the product’s node feature. The node classes in the dataset are split as
40/17/20 for the train/validation/test sets.

  * •

Amazon-Electronics: [14] This dataset is derived from the Amazon products
subcategory ”Electronics”. Each node denotes the product and the product
reviews are considered as the node feature. A link exists between a pair of
nodes if the two products are bought together. The node classes of the dataset
are split as 90/37/40 for train/val/test sets.

  * •

DBLP: [22] This dataset is a subset of the heterogeneous citation network from
the DBLP computer science bibliography website. The nodes represent the
papers, and the edges represent the citations between them. The node classes
of the dataset are split as 80/27/30 for train/val/test sets.

These details are summarised in Table I.

###  V-A Implementation

Our code is implemented using PyTorch framework and the GNNs are implemented
using PyTorch-Geometric library [5]. Our work uses two-layer GNNs with the
hidden layer size of 16 nodes. We train the model for an average of 1000
episodes on each dataset. We have sampled the distribution values on an
average of 1000 times to get a more precise value. All the experiments are
carried out on 8GB GeForce GTX 1080 GPU hardware.

###  V-B Results

Figure 2: Comparison of average accuracy on the datasets under different Few-
shot settings on the Amazon clothing dataset with varying number of partitions
of the similarity vector.

We compare the results across the different baseline methods in Table II. The
comparison metric used for evaluation is the average meta-test accuracy. The
performance on each of the datasets is compared under 2 different Few-shot
settings: 5-way 3-shot learning and 5-way 5-shot learning. With the increasing
number of training classes per episode, the average meta-test accuracy drops.
It can be observed that across different base GNN models, the addition of the
Uncertainty layer has consistently shown better performance in comparison to
their counterparts, i.e., vanilla GNNs. Although we did observe a few outliers
that violated the norm of improved accuracy under certain settings, our work
in general has marked improvement in vast majority of the cases. For example,
in the Amazon electronics dataset, the addition of the UGN layer achieved a
notable improvement in performance under both 5-way 3-shot and 5-way 5-shot
settings for all different variants of GNN. For the dataset DBLP, it showed a
performance gain in all scenarios except UGN-APPNP and UGN-GIN (in 5-way
5-shot setting only). The discrepancy in the result can be partially explained
by the quality of the embedding generated by the MP-GNN and the aggregation
scheme used by it, which negatively impacts the accuracy under low labeled-
data conditions. But the accuracy in general across different datasets under
different Few-shot settings has improved in comparison to the vanilla
networks.

To demonstrate that the uncertainty layer UGN can perform effectively over any
generic GNN, we also conducted experiments using different $g_{\phi}(.)$ in
the UGN layer. Table III shows the accuracy values on the Amazon clothing
dataset when using GAT as the $g_{\phi}(.)$ network in the UGN layer. The
accuracy values have not significantly varied in comparison when using GCN for
the UGN layer. This makes the UGN model agnostic of the core GNN i.e., the
$g_{\phi}(.)$ network being used which demonstrates the universality of the
method and the choice of the GNN making little to no effect on the output
accuracy values.

TABLE III: Average Accuracy values (in %) of baseline methods on Amazon clothing dataset with GAT as the base UGN. The bold values indicate the highest accuracy values in a column. | Amazon clothing
---|---
| 5-way 3-shot | 5-way 5-shot
GCN | 35.3 | 27.1
GraphSAGE | 38.7 | 28.7
GAT | 58.3 | 27.2
GIN | 28.6 | 25.4
SGC | 46.9 | 31.0
APPNP | 47.2 | 43.7
UGN-GCN | 49.1 | 55.9
UGN-GraphSAGE | 52.0 | 47.7
UGN-GAT | 38.5 | 48.5
UGN-GIN | 22.7 | 21.5
UGN-SGC | 52.3 | 44.8
UGN-APPNP | 48.3 | 43.0

###  V-C Sensitivity Analysis

To understand the effect of the number of partitions of the relational-
similarity vector $\textbf{F}\in R^{n\times L}$ has on the accuracy values, we
conducted multiple trials with different values of $L$ as shown in Figure 2.
We partitioned the vector F into 4, 8, 16 and 32 partitions and conducted the
experiments with different GNN models on Amazon clothing dataset under 5-way
3-shot and 5-way 5-shot settings. We observe in Figure 2 that only GIN showed
peak accuracy values with 4 partitions in both 5-way 3-shot and 5-way 5-shot
settings, while the rest of them exhibit a varying behaviour. For example,
GraphSAGE shows peak accuracy value for 5-way 3-shot learning at 4 partitions
and at 8 partitions for 5-way 5-shot learning. A similar behaviour is observed
for SGC, where the peak accuracy for 5-way 3-shot learning and 5-way 5-shot
learning occur at different number of partitions. As mentioned earlier, the
variation in the accuracy values for different MP-GNNs depending on the number
of partitions is dependent on how the node neighbouring information is
aggregated. So, the impact of the partitions for Uncertainty learning has a
varying degree of effect on the meta-test accuracy dependent on base-GNN model
used.

##  VI Conclusion

Our work introduces an Uncertainty Estimator network called UGN that can be
applied on a generic GNN-backbone to achieve a significant performance gain
under Few-shot learning. We tested our model on different variants of GNNs
across multiple few-shot settings and different datasets to affirm the
effectiveness of UGN. We also performed a sensitivity analysis to understand
the effect of the number of partitions on the meta-test accuracy with
different base GNN models. In conclusion, our model effectively demonstrates
the effectiveness of UGN under Few-shot settings over a generic architecture.

## References

  * [1] Jasmijn Bastings et al.  “Graph Convolutional Encoders for Syntax-aware Neural Machine Translation”  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ Copenhagen, Denmark: Association for Computational Linguistics, 2017, pp. 1957–1967  DOI: 10.18653/v1/D17-1209
  * [2] J Bradshaw et al.  “A generative model for electron paths”, 2019
  * [3] Kaize Ding et al.  “Graph prototypical networks for few-shot learning on attributed networks”  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 295–304
  * [4] Vijay Prakash Dwivedi et al.  “Graph neural networks with learnable structural and positional representations”  In _arXiv preprint arXiv:2110.07875_ , 2021
  * [5] Matthias Fey and Jan E. Lenssen  “Fast Graph Representation Learning with PyTorch Geometric”  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019
  * [6] Chelsea Finn, Pieter Abbeel and Sergey Levine  “Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks”  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17  Sydney, NSW, Australia: JMLR.org, 2017, pp. 1126–1135
  * [7] Johannes Gasteiger, Aleksandar Bojchevski and Stephan Günnemann  “Predict then Propagate: Graph Neural Networks meet Personalized PageRank”  In _International Conference on Learning Representations (ICLR)_ , 2019
  * [8] Will Hamilton, Zhitao Ying and Jure Leskovec  “Inductive representation learning on large graphs”  In _Advances in neural information processing systems_ 30, 2017
  * [9] Kexin Huang and Marinka Zitnik  “Graph meta learning via local subgraphs”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 5862–5874
  * [10] Ningyuan Teresa Huang and Soledad Villar  “A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants”  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021, pp. 8533–8537  IEEE
  * [11] Jinwoo Kim et al.  “Pure transformers are powerful graph learners”  In _arXiv preprint arXiv:2207.02505_ , 2022
  * [12] Thomas N. Kipf and Max Welling  “Semi-Supervised Classification with Graph Convolutional Networks”  In _CoRR_ abs/1609.02907, 2016  arXiv: http://arxiv.org/abs/1609.02907
  * [13] Zemin Liu, Yuan Fang, Chenghao Liu and Steven C.H. Hoi  “Relative and Absolute Location Embedding for Few-Shot Node Classification on Graph”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 35.5, 2021, pp. 4267–4275  DOI: 10.1609/aaai.v35i5.16551
  * [14] Julian McAuley, Rahul Pandey and Jure Leskovec  “Inferring networks of substitutable and complementary products”  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , 2015, pp. 785–794
  * [15] Charles R Qi, Hao Su, Kaichun Mo and Leonidas J Guibas  “Pointnet: Deep learning on point sets for 3d classification and segmentation”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 652–660
  * [16] Appan Rakaraddi and Mahardhika Pratama  “Unsupervised Learning for Identifying High Eigenvector Centrality Nodes: A Graph Neural Network Approach”  In _2021 IEEE International Conference on Big Data (Big Data)_ , 2021, pp. 4945–4954  IEEE
  * [17] Appan Rakaraddi, Lam Siew Kei, Mahardhika Pratama and Marcus De Carvalho  “Reinforced Continual Learning for Graphs”  In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_, 2022, pp. 1666–1674
  * [18] Alvaro Sanchez-Gonzalez et al.  “Graph networks as learnable physics engines for inference and control”  In _International Conference on Machine Learning_ , 2018, pp. 4470–4479  PMLR
  * [19] Jake Snell, Kevin Swersky and Richard Zemel  “Prototypical networks for few-shot learning”  In _Advances in neural information processing systems_ 30, 2017
  * [20] Flood Sung et al.  “Learning to compare: Relation network for few-shot learning”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 1199–1208
  * [21] Binh Tang and David S. Matteson  “Graph-Based Continual Learning”  In _International Conference on Learning Representations_ , 2021
  * [22] Jie Tang et al.  “Arnetminer: extraction and mining of academic social networks”  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2008, pp. 990–998
  * [23] Ashish Vaswani et al.  “Attention is All You Need”, 2017  URL: https://arxiv.org/pdf/1706.03762.pdf
  * [24] Petar Veličković et al.  “Graph attention networks”  In _arXiv preprint arXiv:1710.10903_ , 2017
  * [25] Song Wang et al.  “Task-Adaptive Few-Shot Node Classification”  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’22  Washington DC, USA: Association for Computing Machinery, 2022, pp. 1910–1919  DOI: 10.1145/3534678.3539265
  * [26] Wenguan Wang et al.  “Zero-shot video object segmentation via attentive graph neural networks”  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 9236–9245
  * [27] Xiaolong Wang and Abhinav Gupta  “Videos as space-time region graphs”  In _Proceedings of the European conference on computer vision (ECCV)_ , 2018, pp. 399–417
  * [28] Yue Wang et al.  “Dynamic graph cnn for learning on point clouds”  In _Acm Transactions On Graphics (tog)_ 38.5 ACM New York, NY, USA, 2019, pp. 1–12
  * [29] Felix Wu et al.  “Simplifying Graph Convolutional Networks”  In _Proceedings of the 36th International Conference on Machine Learning_ PMLR, 2019, pp. 6861–6871
  * [30] Keyulu Xu, Weihua Hu, Jure Leskovec and Stefanie Jegelka  “How powerful are graph neural networks?”  In _arXiv preprint arXiv:1810.00826_ , 2018
  * [31] Huaxiu Yao et al.  “Graph few-shot learning via knowledge transfer”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 34.04, 2020, pp. 6656–6663
  * [32] Minglei Yuan et al.  “Uncertainty-Based Network for Few-Shot Image Classification”  In _2022 IEEE International Conference on Multimedia and Expo (ICME)_ , 2022, pp. 1–6  DOI: 10.1109/ICME52920.2022.9859887
  * [33] Seongjun Yun et al.  “Graph transformer networks”  In _Advances in neural information processing systems_ 32, 2019
  * [34] Chuxu Zhang et al.  “Few-Shot Learning on Graphs” Survey Track  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_ International Joint Conferences on Artificial Intelligence Organization, 2022, pp. 5662–5669  DOI: 10.24963/ijcai.2022/789
  * [35] Zhizheng Zhang et al.  “Uncertainty-Aware Few-Shot Image Classification”  In _International Joint Conference on Artificial Intelligence (IJCAI 2021)_ , 2021  URL: https://www.microsoft.com/en-us/research/publication/uncertainty-aware-few-shot-image-classification-2/
  * [36] Fan Zhou et al.  “Meta-gnn: On few-shot node classification in graph meta-learning”  In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ , 2019, pp. 2357–2360
  * [37] Jie Zhou et al.  “Graph neural networks: A review of methods and applications”  In _AI Open_ 1 Elsevier, 2020, pp. 57–81


# Hadwiger’s conjecture for some graphs with independence number two

Tong Li<EMAIL_ADDRESS>Qiang Zhou<EMAIL_ADDRESS>Academy of
Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190,
China  University of Chinese Academy of Sciences, Beijing, 100049, China

###### Abstract

Let $h(G)$ denote the largest $t$ such that $G$ contains $K_{t}$ as a minor
and $\chi(G)$ be the chromatic number of $G$ respectively. In 1943, Hadwiger
conjectured that $h(G)\geq\chi(G)$ for any graph $G$. In this paper, we prove
that Hadwiger’s conjecture holds for _H-free_ graphs with independence number
two, where $H$ is one of some specified graphs.

###### keywords:

Hadwiger’s conjecture , graph minor , independence number.

††journal: acta mathematicae applicatae sinica

##  1 Introduction

All graphs considered in this paper are finite, undirected and simple. Let
$V(G)$, $|G|$, $E(G)$, $e(G)$, $\overline{G}$, $\delta(G)$, $\Delta(G)$,
$\omega(G)$, $\alpha(G)$ and $\chi(G)$ denote the vertex set, number of
vertices, edge set, number of edges, complement, minimum degree, maximum
degree, clique number, independence number, and chromatic number of a graph
$G$, respectively. Let $e(G,H)$ denote the number of edges between two graphs
$G$ and $H$. A vertex set $A$ is _complete_ to a vertex set $B$, if every
vertex in $A$ is adjacent to every vertex in $B$. For $X\subseteq V(G)$, Let
$G[X]$ denote the subgraph of $G$ induced by $X$, $G-X$ denote the subgraph
$G[V(G)\backslash X]$ or simply $G-y$ when $X=\\{y\\}$, respectively. Let
$N_{G}(X)$ denote the set of vertices adjacent to $X$ in $G-X$. A graph $H$ is
called a _minor_ of $G$ if $H$ is obtained from $G$ by some sequence of vertex
deletions, edge deletions, and edge contractions. Let $h(G)$ denote the
largest $t$ such that $G$ contains $K_{t}$ as a minor.

In 1943, Hadwiger [7] conjectured that:

######  Conjecture 1.1 ([7])

For every graph $G$, $h(G)\geq\chi(G)$.

Hadwiger’s conjecture is one of the most famous open problems in graph theory.
The Four-color Theorem is a special case when we restrict $h(G)\leq 4$.
Hadwiger [7] and Dirac [6] proved the conjecture holds for $h(G)\leq 3$
independently. Robertson, Seymour and Thomas [16] proved this conjecture is
equivalent to the Four-color Theorem when $h(G)\leq 5$. So far, Hadwiger’s
conjecture is still open when $h(G)\geq 6$.

An equivalent statement of Hadwiger’s conjecture is that every graph with no
$K_{t+1}$ minor is $t$-colorable. Table LABEL:table1 lists some previous
studies:

Table 1:  Author(s) | Year | Results
---|---|---
Delcourt, Postle [4] | 2021 |  | Every graph with no $K_{t+1}$ minor is
---
$O(t\log\log t)$-colorable.
Wagner [20] | 1960 |  | Every graph with no $K_{5}^{-}$ (remove one
---
edge from $K_{5}$) minor is 4-colorable.
Dirac [5] | 1964 |  | Every graph with no $K_{6}^{-}$ minor is
---
5-colorable.
Jakobsen [9][8] |  | 1970
---
1971
| Every graph with no $K_{7}^{-}$ minor is
---
7-colorable;
Every graph with no $\mathcal{K}_{7}^{-2}$ (remove two
edges from $K_{7}$) minor is 6-colorable.
Rolek, Song [18] | 2017 |  | Every graph with no $K_{8}^{-}$ minor is
---
9-colorable;
Every graph with no $\mathcal{K}_{8}^{-2}$ minor is
8-colorable.
Lafferty, Song [13] | 2022 |  | Every graph with no $\mathcal{K}_{8}^{-4}$ minor is
---
7-colorable;
Every graph with no $\mathcal{K}_{9}^{-6}$ minor is
8-colorable.
Rolek [17] | 2020 |  | Every graph with no $\mathcal{K}_{9}^{-2}$ minor is
---
10-colorable.
Kostochka [10] | 2014 |  | Every graph with no $K_{s,t}$ minor is
---
$(s+t-1)$-colorable when
$t>5(200s\log_{2}(200s))^{3}$.
Kostochka, Prince [11] | 2010 |  | Every graph with no $K_{3,t}$ minor is
---
$(t+2)$-colorable when $t\geq 6300$.

Seymour [19] pointed out that graphs $G$ with $\alpha(G)=2$ are particularly
interesting. He believed that Hadwiger’s conjecture is probably true if it
holds for graphs with independence number two.

###### Problem 1.2

Does $h(G)\geq\chi(G)$ hold for every graph $G$ with $\alpha(G)\leq 2$ ?

One idea to study Problem 1.2 is to find a big complete minor, according to
the following theorem:

######  Theorem 1.3 ([15])

For every graph $G$ with $\alpha(G)\leq 2$, $h(G)\geq\chi(G)$ if and only if
$h(G)\geq\lceil|G|/2\rceil$.

Recently, Norin and Seymour [14] proved that for any graph $G$ with
$\alpha(G)\leq 2$, there exists a minor with $\lceil|G|/2\rceil$ vertices and
with fewer than $1/76$ of all possible edges missing.

We can also consider Problem 1.2 for $H$-free graphs, that is, graphs without
$H$ as an induced subgraph. Table LABEL:table2 and Figure 1 list previous
studies of Problem 1.2 for $H$-free graphs:

Table 2:  Author(s) | Year | Results
---|---|---
Plummer, Stiebitz, Toft [15] | 2003 |  |  $|H|\leq 4$, or $H=C_{5}$,
---
or $H=G_{1}$ in Figure 1.
Kriesell [12] | 2010 |  |  $|H|\leq 5$,
---
or $H=W_{5}^{-}$ in Figure 1.
Bosse [1] | 2019 |  |  $H=W_{5}$ in Figure 1,
---
or $H=\overline{K_{1,5}}$ in Figure 1,
or $H=K_{7}$.
Carter [2] | 2022+ |  |  $H$ is any of the 33 graphs in [2]
---
or $H=K_{8}$. (computer-assisted)
Carter [2] | 2022+ |  |  $H=G_{2}$, $G_{3}$ or $G_{4}$ in Figure 1.
---
Figure 1: Graph $H$ in previous studies Figure 2: Graph $H$ in this paper

In particular, Carter [2] used some algorithms to verify Problem 1.2 for
$H$-free graphs when $H$ is $K_{8}$ or any of the 33 graphs in the paper, and
proved for $H=G_{2},G_{3},G_{4}$ mathematically. In this paper, we prove
Problem 1.2 hold for more $H$ mathematically, generalize the results of
Plummer, Stiebitz, Toft, Kriesell, Bosse and Carter:

###### Theorem 1.4

Let $H=\overline{K_{1,6}}$ in Figure 2. For every $H$-free graph $G$ with
$\alpha(G)\leq 2$, $h(G)\geq\chi(G)$.

Since $\overline{K_{1,6}}$-free is equivalent to $\delta(G)\geq|G|-6$, we can
also get:

###### Corollary 1.5

For every graph $G$ with $\alpha(G)\leq 2$, if $\delta(G)\geq|G|-6$, then
$h(G)\geq\chi(G)$.

###### Theorem 1.6

Let $H=H_{7}$ in Figure 2. For every $H$-free graph $G$ with $\alpha(G)\leq
2$, $h(G)\geq\chi(G)$.

###### Theorem 1.7

For every $K_{8}$-free graph $G$ with $\alpha(G)\leq 2$, if $\delta(G)\neq
19$, then $h(G)\geq\chi(G)$.

Here we limit $\delta(G)\neq 19$ as we do not know how to handle the case when
$|G|=27$, $\delta(G)=19$, $\Delta(G)=20\ \text{or}\ 21$.

##  2 Preliminaries

The following theorems and lemmas are used in our proofs:

######  Theorem 2.8 ([1])

For every $K_{7}$-free graph $G$ with $\alpha(G)\leq 2$, $h(G)\geq\chi(G)$.

######  Theorem 2.9 ([3])

Let $G$ be a graph with $\alpha(G)\leq 2$. If

$\omega(G)\geq\begin{cases}|G|/4,&\text{if $|G|$ is even}\\\
(|G|+3)/4,&\text{if $|G|$ is odd}\end{cases},$

then $h(G)\geq\chi(G)$.

###### Lemma 2.10

Let $G$ be a minimal counterexample to Problem 1.2 with respect to
$|V(G)|+|E(G)|$, then $|G|=27$ or $|G|\geq 29$.

_Proof._ By Theorem 2.8, $G$ must contain a $K_{7}$, then by Theorem 2.9,

$7\leq\omega(G)<\begin{cases}|G|/4,&\text{if $|G|$ is even}\\\
(|G|+3)/4,&\text{if $|G|$ is odd}\end{cases},$

we have $|G|=27$ or $|G|\geq 29$.∎

An edge $e$ is a _dominating edge_ of graph $G$ if $e$ is adjacent to all
vertices in $G\backslash e$. A matching $M$ is _connected_ if its edges are
adjacent to each other. A matching $M$ is a _dominating matching_ if each edge
in $M$ is adjacent to all vertices in $G\backslash M$.(A dominating edge is a
special connected dominating matching.)

###### Lemma 2.11

Let $G$ be a minimal counterexample to Problem 1.2 with respect to
$|V(G)|+|E(G)|$, then $G$ does not contain a connected dominating matching.

_Proof._ If $G$ contains a connected dominating matching $M$, then
$G\backslash M$ has a complete minor of $\lceil|G\backslash M|/2\rceil$
vertices. Together with the contractions of every matching edges in $M$, we
get a complete minor of $\lceil|G|/2\rceil$ vertices from $G$, a
contradiction.∎

##  3 Proof of Theorem 1.4

Let $G$ be a minimal counterexample to Theorem 1.4 with respect to
$|V(G)|+|E(G)|$. That is to say, $G$ is $\overline{K_{1,6}}$-free with
$\alpha(G)\leq 2$, but $h(G)<\chi(G)$.

Since $G$ is $\overline{K_{1,6}}$-free, then we can choose a vertex $v$ with
$d_{G}(v)\geq|G|-6$. Let $A=V(G)\backslash N_{G}[v]$, then $|A|\leq 5$. For
any vertex $u\in N_{G}(v)$, $u$ is not adjacent to at least one vertex in $A$,
otherwise $e_{uv}$ is a dominating edge. By Lemma 2.10, $|G|\geq 27$, it
follows that there are at least 21 non-edges between $A$ and $N_{G}(v)$. By
pigeonhole principle, there exists a vertex $w\in A$ is not adjacent to at
least 5 vertices in $N_{G}(v)$. Since $\alpha(G)=2$, the five vertices form a
clique. Then $w$, $v$ and these 5 vertices form an induced
$\overline{K_{1,6}}$, a contradiction.

##  4 Proof of Theorem 1.6

Figure 3 lists some induced subgraphs of $H_{7}$, which are not induced
subgraphs of any graph in Figure 1.

Figure 3: Some induced subgraphs of $H_{7}$

We first prove that Theorem 1.6 holds for $H=K_{5}^{+}$. In fact, the other
three graphs are simple corollaries of this case.

Let $G$ be a minimal counterexample to Theorem 1.6 with respect to
$|V(G)|+|E(G)|$. That is to say, $G$ is $H$-free with $\alpha(G)\leq 2$, but
$h(G)<\chi(G)$. By Lemma 2.10 we have $|G|=27$ or $|G|\geq 29$.

By Theorem 1.4, $G$ contains an induced $\overline{K_{1,6}}$(actually
$\overline{K_{1,5}}$ is enough to prove Theorem 1.6). So there exists a
minimal vertex set $T$ such that $G-T$ has exactly two components $F_{1}$ and
$F_{2}$, where $F_{1}$ contains a $K_{6}$ (so $|F_{1}|\geq 6$) and
$|F_{2}|\geq 1$. $F_{1}$ and $F_{2}$ must be cliques since $\alpha(G)\leq 2$.
For any vertex $v_{T}\in T$, neither $N_{F_{1}}(v_{T})$ nor $N_{F_{2}}(v_{T})$
is empty due to the minimality of $T$.

###### Claim 4.1

For any vertex $v_{T}\in T$, $2\leq|N_{F_{1}}(v_{T})|\leq 3$.

_Proof._ If $|N_{F_{1}}(v_{T})|=1$ for some vertex $v_{T}\in T$, then
$v_{T},N_{F_{1}}(v_{T})$ and any other four vertices in $F_{1}$ form an
induced copy of $H$, a contradiction.

If $|N_{F_{1}}(v_{T})|\geq 4$ for some vertex $v_{T}\in T$, then $v_{T}$, any
four vertices in $N_{F_{1}}(v_{T})$ and any one vertex in $N_{F_{2}}(v_{T})$
form an induced copy of $H$, a contradiction.

###### Claim 4.2

$T$ is complete to $F_{2}$.

_Proof._ By Claim 4.1 and $|F_{1}|\geq 6$, any vertex in $T$ is not complete
to $F_{1}$, so $T$ is complete to $F_{2}$ since $\alpha(G)\leq 2$.

###### Claim 4.3

$1\leq|F_{2}|\leq 3$.

_Proof._ If $|F_{2}|\geq 4$, then any one vertex $v_{T}\in T$, any four
vertices in $F_{2}$ and any one vertex in $N_{F_{1}}(v_{T})$ form an induced
copy of $H$, a contradiction.

###### Claim 4.4

$|F_{1}|=6$.

_Proof._ If $|F_{1}|\geq 7$, then any two vertices in $T$ have at most six
common neighbors in $F_{1}$ by Claim 4.3. In other words, there exists one
vertex in $F_{1}$ which is not adjacent to either of these two vertices. So
these two vertices are adjacent to each other since $\alpha(G)\leq 2$. By the
arbitrary choice of these two vertices, we can get that $T$ is a clique.

Now $F_{1}$ and $T\cup F_{2}$ are two disjoint cliques in $G$ and $G=F_{1}\cup
T\cup F_{2}$. So there exists a clique of at least $\lceil|G|/2\rceil$
vertices. By Theorem 1.3, $h(G)\geq\chi(G)$, a contradiction.

Next we will divide our proof into three cases:

###### Case 1

$|F_{2}|=3$.

We first prove that for any two vertices $v_{T}$ and $v_{T}^{\prime}$ in $T$,
$N_{F_{1}}(v_{T})=N_{F_{1}}(v_{T}^{\prime})$ if and only if $v_{T}$ is
adjacent to $v_{T}^{\prime}$.

On the one hand, if $v_{T}$ is adjacent to $v_{T}^{\prime}$ but
$N_{F_{1}}(v_{T})\neq N_{F_{1}}(v_{T}^{\prime})$, then we can choose a vertex
$v\in N_{F_{1}}(v_{T})\triangle N_{F_{1}}(v_{T}^{\prime})=N_{F_{1}}(v_{T})\cup
N_{F_{1}}(v_{T}^{\prime})-N_{F_{1}}(v_{T})\cap N_{F_{1}}(v_{T}^{\prime})$.
Thus, $\\{v\\}\cup\\{v_{T}\\}\cup\\{v_{T}^{\prime}\\}\cup F_{2}$ can form an
induced copy of $H$, a contradiction.

On the other hand, if $N_{F_{1}}(v_{T})=N_{F_{1}}(v_{T}^{\prime})$ for some
$v_{T}$ and $v_{T}^{\prime}$ in $T$, then by Claim 4.1 and Claim 4.4, there
exists one vertex in $F_{1}$ which is not adjacent to either of $v_{T}$ or
$v_{T}^{\prime}$. So $v_{T}$ is adjacent to $v_{T}^{\prime}$ since
$\alpha(G)\leq 2$.

So $N_{F_{1}}(v_{T})=N_{F_{1}}(v_{T}^{\prime})$ if and only if $v_{T}$ is
adjacent to $v_{T}^{\prime}$. Thus, $T$ is formed by some disjoint cliques. By
$\alpha(G)\leq 2$, $T$ consists of at most two disjoint cliques, denoted by
$T_{1}$ and $T_{2}$ ($T_{2}$ can be an empty set).

Now we get three cliques $F_{1}$, $T_{1}\cup F_{2}$ and $T_{2}\cup F_{2}$ in
$G$, and $|F_{1}|+|T_{1}\cup F_{2}|+|T_{2}\cup F_{2}|=|G|+3$. This indicates
$\omega(G)\geq\lceil(|G|+3)/3\rceil\geq\lceil(|G|+3)/4\rceil$. By Theorem 2.9,
we get $h(G)\geq\chi(G)$, a contradiction.

###### Case 2

$|F_{2}|=2$.

It is easy to see $|T|\geq 6$ since $|G|\geq 27$. Then $T$ contains a triangle
$T_{1}$ since Ramsey number $R(3,3)=6$ and $\alpha(G)\leq 2$. By Claim 4.1 we
get that for any vertex $v_{T}\in T$, $|N_{F_{1}}(v_{T})|\leq 3$. So
$e(T_{1},F_{1})\leq 3\times 3=9$. By pigeonhole principle, there exists a
vertex $v_{F_{1}}\in F_{1}$, such that $|N_{T_{1}}(v_{F_{1}})|\leq 1$. If
$|N_{T_{1}}(v_{F_{1}})|=1$, then $\\{v_{F_{1}}\\}\cup T_{1}\cup F_{2}$ form an
induced copy of $H$, a contradiction. So $|N_{T_{1}}(v_{F_{1}})|=0$.

Set $T_{2}=\\{v\in T\ |\ v\text{ is not adjacent to }v_{F_{1}}\\}$, then
$T_{1}\subseteq T_{2}$ and $T_{2}$ is a clique since $\alpha(G)\leq 2$. Set
$T_{3}=T\backslash T_{2}$.

If $T_{3}=\emptyset$, then $F_{1}$ and $T\cup F_{2}$ are two disjoint cliques
in $G$. Since $G=F_{1}\cup T\cup F_{2}$, $G$ contains a clique of at least
$\lceil|G|/2\rceil$ vertices. Then $h(G)\geq\chi(G)$ by Theorem 1.3, a
contradiction.

If $T_{3}\neq\emptyset$. For any vertex $v_{T_{3}}\in T_{3}$ we have
$|N_{T_{2}}(v_{T_{3}})|\leq 1$, otherwise
$\\{v_{F_{1}}\\}\cup\\{v_{T_{3}}\\}\cup F_{2}\cup\\{\text{any two vertices in
}N_{T_{2}}(v_{T_{3}})\\}$ form an induced copy of $H$. By $\alpha(G)\leq 2$
and $|T_{2}|\geq 3$, we get that $T_{3}$ is a clique. Now $|F_{1}|+|T_{2}\cup
F_{2}|+|T_{3}\cup F_{2}|=|G|+2$, we have
$\omega(G)\geq\lceil(|G|+2)/3\rceil\geq\lceil(|G|+3)/4\rceil$. Then
$h(G)\geq\chi(G)$ by Theorem 2.9, a contradiction.

###### Case 3

$|F_{2}|=1$.

It is easy to see $|T|\geq 9$ since $|G|\geq 27$. Then $T$ contains a $K_{4}$
since Ramsey number $R(3,4)=9$ and $\alpha(G)\leq 2$. If
$|N_{K_{4}}(v_{F_{1}})|=1$ for some vertex $v_{F_{1}}\in F_{1}$, then
$\\{v_{F_{1}}\\}\cup K_{4}\cup F_{2}$ form an induced copy of $H$. So for
every vertex $v_{F_{1}}\in F_{1}$, $|N_{K_{4}}(v_{F_{1}})|\neq 1$.

###### Case 3.1

There exists a vertex $v_{F_{1}}\in F_{1}$, $|N_{K_{4}}(v_{F_{1}})|=0$.

Set $T_{1}=\\{v\in T\ |\ v\text{ is adjacent to }v_{F_{1}}\\}$,
$T_{2}=T\backslash T_{1}$, then $T_{2}$ contains a $K_{4}$ (so $|T_{2}|\geq
4$) and $T_{2}$ is a clique since $\alpha(G)\leq 2$. If
$|N_{T_{2}}(v_{T_{1}})|\geq 3$ for some vertex $v_{T_{1}}\in T_{1}$, then
$\\{v_{T_{1}}\\}\cup F_{2}\cup\\{v_{F_{1}}\\}\cup\\{\text{any three vertices
in }N_{T_{2}}(v_{T_{1}})\\}$ form an induced copy of $H$. So for every vertex
$v_{T_{1}}\in T_{1}$, $|N_{T_{2}}(v_{T_{1}})|\leq 2$ .

###### Case 3.1.1

$|T_{2}|\geq 5$.

$|N_{T_{2}}(v_{T_{1}})|+|N_{T_{2}}(v_{T_{1}}^{\prime})|\leq 4<|T_{2}|$ for any
two vertices $v_{T_{1}}$ and $v_{T_{1}}^{\prime}$ in $T_{1}$. So there exists
a vertex in $T_{2}$ that is not adjacent to either $v_{T_{1}}$ or
$v_{T_{1}}^{\prime}$. By $\alpha(G)\leq 2$, $v_{T_{1}}$ is adjacent to
$v_{T_{1}}^{\prime}$ hence $T_{1}$ is a clique due to the arbitrary choice of
$v_{T_{1}}$ and $v_{T_{1}}^{\prime}$. Now $|F_{1}|+|T_{1}\cup
F_{2}|+|T_{2}\cup F_{2}|=|G|+1$, we have
$\omega(G)\geq\lceil(|G|+1)/3\rceil\geq\lceil(|G|+3)/4\rceil$. By Theorem 2.9
we get $h(G)\geq\chi(G)$, a contradiction.

###### Case 3.1.2

$|T_{2}|=4$.

For any vertex $v_{T_{1}}\in T_{1}$, $N_{T_{2}}(v_{T_{1}})\neq\emptyset$,
otherwise $T_{2}\cup F_{2}\cup\\{v_{T_{1}}\\}$ form an induced copy of $H$.
Hence $1\leq|N_{T_{2}}(v_{T_{1}})|\leq 2$ for every vertex $v_{T_{1}}\in
T_{1}$.

If $T_{1}$ contains a $K_{5}$, then for every vertex $v_{T_{2}}\in T_{2}$,
$|N_{K_{5}}(v_{T_{2}})|\neq 0,1,2$. Otherwise $\\{v_{T_{2}}\\}\cup K_{5}\cup
F_{2}\cup\\{v_{F_{1}}\\}$ contain an induced copy of $H$. So
$e(T_{2},K_{5})\geq 3\times 4=12$. However, $|N_{T_{2}}(v_{T_{1}})|\leq 2$ for
every vertex $v_{T_{1}}\in T_{1}$, we have $e(T_{2},K_{5})\leq 2\times 5=10$,
a contradiction.

If $T_{1}$ is $K_{5}$-free, by Ramsey number $R(3,5)=14$ and $\alpha(G)\leq
2$, we obtain that $|T_{1}|\leq 13$. So $|G|\leq 24$, a contradiction.

###### Case 3.2

For every vertex $v_{F_{1}}\in F_{1}$, $|N_{K_{4}}(v_{F_{1}})|\geq 2$.

###### Case 3.2.1

$|G|\geq 29$

$|T\backslash K_{4}|\geq 18$ since $|G|\geq 29$. By Ramsey number $R(3,6)=18$
and $\alpha(G)\leq 2$, $T\backslash K_{4}$ contains a $K_{6}$.

For every vertex $v_{K_{4}}\in K_{4}$, $|N_{K_{6}}(v_{K_{4}})|\neq 0,1,2$,
otherwise $\\{v_{K_{4}}\\}\cup K_{6}\cup F_{2}$ contain an induced copy of
$H$. For every vertex $v_{F_{1}}\in F_{1}$, $|N_{K_{6}}(v_{F_{1}})|\neq
1,2,3$, otherwise $\\{v_{F_{1}}\\}\cup K_{6}\cup F_{2}$ contain an induced
copy of $H$.

If there exists a vertex $v_{F_{1}}\in F_{1}$ with $|N_{K_{6}}(v_{F_{1}})|=0$,
then we can choose a vertex $v_{K_{4}}\in N_{K_{4}}(v_{F_{1}})$ such that
$\\{\text{any three vertices in
}N_{K_{6}}(v_{K_{4}})\\}\cup\\{v_{F_{1}}\\}\cup\\{v_{K_{4}}\\}\cup F_{2}$
forms an induced copy of $H$.

If for every vertex $v_{F_{1}}\in F_{1}$, $|N_{K_{6}}(v_{F_{1}})|\geq 4$, then
$e(F_{1},K_{6})\geq 4\times 6=24$. However, $|N_{F_{1}}(v_{T})|\leq 3$ for
every vertex $v_{T}\in T$ by Claim 4.1, we have $e(F_{1},K_{6})\leq 3\times
6=18$, a contradiction.

###### Case 3.2.2

$|G|=27$

$|T|=20$ since $|G|=27$. Let $A$ be a set of two vertices in $K_{4}$, by
Ramsey number $R(3,6)=18$ and $\alpha(G)\leq 2$, $T\backslash A$ contains a
$K_{6}$. We have $|K_{6}\cap K_{4}|\leq 2$.

If $|K_{6}\cap K_{4}|=0$, the remaining proof is the same as Case 3.2.1.

If $1\leq|K_{6}\cap K_{4}|\leq 2$, then we can divide the proof into two
parts:

If there exists a vertex $v_{F_{1}}\in F_{1}$ with
$N_{K_{6}}(v_{F_{1}})=\emptyset$, then we can choose a vertex $v_{K_{4}}\in
N_{K_{4}}(v_{F_{1}})$ such that $\\{v_{F_{1}}\\}\cup\\{v_{K_{4}}\\}\cup
K_{6}\cup F_{2}$ contain an induced copy of $H$ (either $v_{F_{1}}$ or
$v_{K_{4}}$ is the vertex of degree one in $H$).

If $N_{K_{6}}(v_{F_{1}})\neq\emptyset$ for every vertex $v_{F_{1}}\in F_{1}$,
then we can also get that $|N_{K_{6}}(v_{F_{1}})|\neq 1,2,3$ for every vertex
$v_{F_{1}}\in F_{1}$, otherwise $\\{v_{F_{1}}\\}\cup K_{6}\cup F_{2}$ contain
an induced copy of $H$. So $e(F_{1},K_{6})\geq 4\times 6=24$. On the other
hand, $|N_{F_{1}}(v_{T})|\leq 3$ for every vertex $v_{T}\in T$ by Claim 4.1,
we have $e(F_{1},K_{6})\leq 3\times 6=18$, a contradiction.

So far we have proved the Theorem 1.6 for $H=K_{5}^{+}$, it suffices to prove
that Theorem 1.6 is also holds for $H=H_{7}$.

Let $H=H_{7}$ and let $G$ be a minimal counterexample to Theorem 1.6 with
respect to $|V(G)|+|E(G)|$. That is to say, $G$ is $H$-free with
$\alpha(G)\leq 2$, but $h(G)<\chi(G)$.

By the proof above, $G$ contains an induced copy of $K_{5}^{+}$. Let $v$ be
the vertex of degree one in $K_{5}^{+}$, and $u$ be the neighbor of $v$ in
$K_{5}^{+}$.

For every vertex $w\in G\backslash K_{5}^{+}$, if $w$ is not adjacent to $v$,
then $w$ is adjacent to all vertices of $K_{5}^{+}\backslash\\{u,v\\}$ since
$\alpha(G)\leq 2$. So $w$ is adjacent to $u$ because $G$ is $H$-free. That is
to say, edge $e_{uv}$ is a dominating edge, a contradiction to Lemma 2.11.

This completes the proof of Theorem 1.6.

##  5 Proof of Theorem 1.7

By Ramsey number $R(3,8)=28$ and $\alpha(G)\leq 2$, every $K_{8}$-free
counterexample to Problem 1.2 has exactly 27 vertices. By Ramsey number
$R(3,7)=23$ and $K_{8}$-free we have $\Delta(G)\leq 22$ and $\delta(G)\geq
19$, otherwise the neighbors of a vertex $v$ with maximum degree has a $K_{7}$
subgraph(together with $v$ we get $K_{8}$), or the non-neighbors of a vertex
$v$ with minimum degree has a $K_{8}$ subgraph.

Let $\Delta(G)=22$ and $v$ be the vertex of degree 22. Let $A=V(G)\backslash
N_{G}[v]$, then $|A|=4$. For any vertex $u\in N_{G}(v)$, $u$ is not adjacent
to at least one vertex in $A$, otherwise $e_{uv}$ is a dominating edge. Set
$A=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and $N_{G}(v)=N_{1}\cup N_{2}\cup N_{3}\cup
N_{4}$ where any vertex in $N_{i}$ is adjacent to $v_{1},...,v_{i-1}$ but not
adjacent to $v_{i}$ for $i=1,2,3,4$. Then $N_{i}$ is a clique since
$\alpha(G)\leq 2$, so $|N_{1}|\leq 6,|N_{2}|\leq 6,|N_{3}|\leq 5,|N_{4}|\leq
4$ since $G$ is $K_{8}$-free. But
$22=|N_{G}(v)|=|N_{1}|+|N_{2}|+|N_{3}|+|N_{4}|\leq 21$, a contradiction.

By the assumption $\delta(G)\neq 19$ we have $20=\delta(G)\leq\Delta(G)\leq
21$ since there is no 21 regular graph with 27 vertices.

Let $\Delta(G)=21$ and $v$ be the vertex of degree 21. Let $A=V(G)\backslash
N_{G}[v]$, then $|A|=5$. For any vertex $u\in N_{G}(v)$, $u$ is not adjacent
to at least one vertex in $A$, otherwise $e_{uv}$ is a dominating edge. So
$80=5\times(20-4)\leq e(N_{G}(v),A)\leq 21\times 4=84$. Set
$A=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ and $N_{G}(v)=N_{1}\cup N_{2}\cup
N_{3}\cup N_{4}\cup N_{5}\cup N$, where any vertex in $N_{i}$ is not adjacent
to $v_{i}$ and adjacent to $v_{j}$($j\neq i$) for $i=1,2,3,4,5$, any vertex in
$N$ is not adjacent to at least two vertices in $A$. Then $N_{i}$ is a clique
since $\alpha(G)\leq 2$, so $|N_{i}|\leq 3$ since $G$ is $K_{8}$-free. But
$|N|\leq 4$ since $e(N_{G}(v),A)\geq 80$, we have
$22=|N_{G}(v)|=|N_{1}|+|N_{2}|+|N_{3}|+|N_{4}|+|N_{5}|+|N|\leq 19$, a
contradiction.

If $\Delta(G)=20$, let $v$ be a vertex of degree 20. Let $A=V(G)\backslash
N_{G}[v]$, then $|A|=6$. For any vertex $u\in N_{G}(v)$, $u$ is not adjacent
to at least one vertex in $A$, otherwise $e_{uv}$ is a dominating edge. Set
$N_{G}(v)=N_{1}\cup N_{2}$, where any vertex in $N_{1}$ is adjacent to five
vertices in $A$ and any vertex in $N_{2}$ is adjacent to at most four vertices
in $A$. Since $e(N_{G}(v),A)=6\times(20-5)=90$, we have $|N_{2}|\leq 10$.
There are at most two vertices in $N_{1}$ have common neighbors in $A$ since
$G$ is $K_{8}$-free, so $|N_{1}|\leq 12$. Thus $N_{2}$ is one of the
following:

  * $\bullet$

10 vertices which have 4 neighbors in $A$; or

  * $\bullet$

9 vertices which have 4 neighbors in $A$; or

  * $\bullet$

8 vertices which have 4 neighbors in $A$; or

  * $\bullet$

8 vertices which have 4 neighbors in $A$ and 1 vertex which has 3 neighbors in
$A$; or

  * $\bullet$

7 vertices which have 4 neighbors in $A$ and 1 vertex which has 3 neighbors in
$A$; or

  * $\bullet$

7 vertices which have 4 neighbors in $A$ and 1 vertex which has 2 neighbors in
$A$; or

  * $\bullet$

6 vertices which have 4 neighbors in $A$ and 2 vertices which have 3 neighbors
in $A$.

The corresponding number of edges in $A$ that cannot dominate $N_{2}$ is at
most 10, 9, 8, 11, 10, 13, 12. So there exists one edge $e=\\{u,w\\}$ in $A$
which dominates $N_{2}$ since $e(A)=15$. By the definition of $N_{1}$, $e$
dominates $N_{1}$ as well.

The vertex $u$ or $w$ has at least one non-neighbor in $N_{1}$, otherwise
there are 3 vertices in $N_{1}$ have common neighbors in $A$ since
$|N_{1}|\geq 10$, a contradiction to $K_{8}$-free. Without loss of generality,
we assume that $x\in N_{1}$ is not adjacent to $u$, then
$e^{\prime}=\\{v,x\\}$ and $e=\\{u,w\\}$ are connected dominating matching, a
contradiction to 2.11.

This completes the proof of Theorem 1.7.

## References

  * [1] C. Bosse.  A note on Hadwiger’s conjecture for $W_{5}$-free graphs with independence number two.  Discrete Mathematics, 342(12):111595, 2019.
  * [2] D. Carter.  Hadwiger’s conjecture with certain forbidden induced subgraphs.  arXiv preprint arXiv:2211.00259, 2022.
  * [3] M. Chudnovsky and P. Seymour.  Packing seagulls.  Combinatorica, 32:251–282, 2012.
  * [4] M. Delcourt and L. Postle.  Reducing linear Hadwiger’s conjecture to coloring small graphs.  arXiv preprint arXiv:2108.01633, 2021.
  * [5] G. Dirac.  On the structure of 5-and 6-chromatic abstract graphs.  Journal für die reine und angewandte Mathematik (Crelles Journal), 1964(214-215):43–52, 1964.
  * [6] G. A. Dirac.  A property of 4-chromatic graphs and some remarks on critical graphs.  Journal of the London Mathematical Society, 1(1):85–92, 1952.
  * [7] H. Hadwiger.  Über eine klassifikation der streckenkomplexe.  Vierteljschr. Naturforsch. Ges. Zürich, 88(2):133–142, 1943.
  * [8] I. T. Jakobsen.  A homomorphism theorem with an application to the conjecture of Hadwiger.  1970\.
  * [9] I. T. Jakobsen.  Weakenings of the conjecture of Hadwiger for 8-and 9-chromatic graphs.  Aarhus Universitet, 1971.
  * [10] A. V. Kostochka.  Minors in Chromatic Graphs, II.  Journal of Graph Theory, 75(4):377–386, 2014.
  * [11] A. V. Kostochka and N. Prince.  Dense graphs have $K_{3,t}$ minors.  Discrete Mathematics, 310(20):2637–2654, 2010.
  * [12] M. Kriesell.  On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs.  Discrete Mathematics, 310(20):2714–2724, 2010.
  * [13] M. Lafferty and Z.-X. Song.  Every graph with no $\mathcal{K}_{8}^{-4}$ minor is 7-colorable.  arXiv preprint arXiv:2208.07338, 2022.
  * [14] S. Norin and P. Seymour.  Dense minors of graphs with independence number two.  arXiv preprint arXiv:2206.00186, 2022.
  * [15] M. Plummer, M. Stiebitz, and B. Toft.  On a special case of Hadwiger’s conjecture.  Discussiones Mathematicae Graph Theory, 23(2):333–363, 2003.
  * [16] N. Robertson, P. Seymour, and R. Thomas.  Hadwiger’s conjecture for $K_{6}$-free graphs.  Combinatorica, 13(3):279–361, 1993.
  * [17] M. Rolek.  Graphs with no $K_{9}^{=}$ minor are 10-colorable.  Journal of Graph Theory, 93(4):560–565, 2020.
  * [18] M. Rolek and Z.-X. Song.  Coloring graphs with forbidden minors.  Journal of Combinatorial Theory, Series B, 127:14–31, 2017.
  * [19] P. Seymour.  Hadwiger’s conjecture.  Open problems in mathematics, pages 417–437, 2016.
  * [20] K. Wagner.  Bemerkungen zu Hadwigers Vermutung.  Mathematische Annalen, 141(5):433–451, 1960.