# COV19IR : COVID-19 Domain Literature Information Retrieval

Arusarka Bose1, Zili Zhou2, Guandong Xu3  1Indian Institute of Technology
Kharagpur, India
<EMAIL_ADDRESS>2Department of Computer Science, University of
Manchester, UK
<EMAIL_ADDRESS>3Advanced Analytics Institute, University of
Technology Sydney, Australia
<EMAIL_ADDRESS>
###### Abstract

Increasing number of COVID-19 research literatures cause new challenges in
effective literature screening and COVID-19 domain knowledge aware Information
Retrieval. To tackle the challenges, we demonstrate two tasks along with
solutions, COVID-19 literature retrieval, and question answering. COVID-19
literature retrieval task screens matching COVID-19 literature documents for
textual user query, and COVID-19 question answering task predicts proper text
fragments from text corpus as the answer of specific COVID-19 related
questions. Based on transformer neural network, we provided solutions to
implement the tasks on CORD-19 dataset, we display some examples to show the
effectiveness of our proposed solutions.

###### Index Terms:

COVID-19, Information retrieval, Transformer Neural Network model.

##  I Introduction

Recently, increasing number of research works targeting COVID-19 contribute
rich literature and base for further research in the area. However, large data
volume brings out new challenges, 1) effectively screening literature
according to the user search query, 2) considering medical and COVID-19 domain
knowledge in the information retrieval process. In this paper, we demonstrate
our work on COVID-19 domain-specific information retrieval (IR) study. Two
specific tasks are presented in this work, 1) COVID-19 literature retrieval,
and 2) COVID-19 question answering. Our solutions on these two tasks are also
given.

Textual retrieval task is a common task in IR area, searching the matching
documents for each textual query provided by user. The COVID-19 literature
retrieval task in this paper is a special textual retrieval task. It uses
COVID-19 literatures as candidate documents set, the COVID-19 domain knowledge
acts as important inter-document connections. Besides that, the task orients
to search queries given by professional researchers which may contain medical
or COVID-19 related terminologies. Our target is to link documents and queries
based on COVID-19 domain knowledge aware semantic matching model.

COVID-19 question answering task is a new attempt of Natural Language
Understanding (NLU) on COVID-19 literature dataset. Treating COVID-19
literature dataset as an unstructured textual knowledge vault, the task is to
find proper text fragment from the original sentence as the answer of given
question based on knowledge understanding.

Transformer neural network is state-of-the-art solution for text analysis and
natural language understanding tasks. With deep multi-layer network structure,
transformer neural network is capable of capturing deep semantic information
from natural language, which is required by both COVID-19 IR tasks defined in
this paper. Both literature retrieval and question answering tasks are built
on the base that the model can well understand the common natural language
semantic and COVID-19 domain-specific knowledge inference. In this paper, we
formalize our two tasks into frameworks of two proper natural language
questions which can be fitted into transformer neural network. Based on
transformer neural network model, we implement the aforementioned tasks on a
COVID-19 literature dataset, CORD-19. Using example outputs of our solutions
on CORD-19 data, we show the effectiveness of our proposed solutions. The code
for this paper is available at https://github.com/ArusarkaBose/COVID-19

Figure 1: COVID-19 Literature Retrieval Model Architecture Figure 2: COVID-19
Question Answering Model Architecture

The rest of the paper is organized as follows. Section 2 presents the
preliminary of our study. In section 3, we present the state-of-the-art models
used in this paper for COVID-19 domain literature information retrieval. We
provide the experimental results and discussion in section 4. Finally, section
5 provides the conclusion of this paper.

##  II Preliminary

Stanford Question Answering Dataset (SQuAD) [6] defines a new category of
question-answering tasks. From the original textual sentence, a text fragment
is picked out as answer of given question.

The BERT model architecture [1, 7] is a multilayer bidirectional Transformer
trained on two tasks: 1) predicting randomly masked tokens, and 2) predicting
whether two sentences follow each other.

BERT model can also be fine-tuned with the classifier output layer to do the
text sequence classification. And with SQuAD task output layer, the question-
answering task can also be achieved by BERT.

The Hugging Face transformer is built on top of the BERT architecture and
provides a unified API for state-of-the-art general-purpose architectures for
Natural Language Understanding (NLU) and Natural Language Generation (NLG)
with over thousands of pretrained models [9] .

The COVID-19 Open Research Dataset (CORD-19) [8] is a resource of over 200,000
scholarly articles, including over 90,000 with full text, about COVID-19,
SARS-CoV-2, and related coronaviruses. This freely available dataset is
provided to the global research community to apply recent advances in NLP and
other AI techniques to generate new insights in support of the ongoing fight
against this infectious disease.

Although some previous BERT like transformer neural network models, can
achieve general text sequence classification and question answering task, the
available pre-trained BERT models are trained on common natural language text
corpora, and the COVID-19 domain knowledge and semantic is ignored. In this
case, we provide COVID-19 customized transformer neural network based IR
solutions in this paper to achieve accurate domain IR.

##  III COVID-19 Domain Literature Information Retrieval

In this section, we elaborate on the proposed architecture of the Literature-
Retrieval and Question-Answering system. As shown in Figure 1, the Literature
Retrieval (LR) model is designed to get the top articles in the corpus related
to the search query. In Figure 2, the Question-Answering (QA) system provides
a correct answer as an output to the search query.

Literature Retrieval The COVID-19 Literature Retrieval Model comprises a
sequential framework of different BERT architectures. The first stage employs
the BERT SQuAD model architecture for the selection of documents among the
candidate documents in the CORD-19 dataset, with relevance to the given
textual query. The BERT MRPC configuration is used in the second stage to rank
the selected documents in accordance with similarity to the textual query.

Each candidate document in the CORD-19 dataset is pre-processed into smaller
context chunks before passage through the IR system. In each iteration, one of
the context chunks is passed along with the textual query through the
Literature Retrieval Model in order to generate a probability score which
indicates the likelihood of the selected context containing the correct
information pertaining to the query.

Figure 1 illustrates the pathway for a textual query and context pair through
the Retrieval Model architecture. The BERT SQuAD neural network model is
designed to take as input a query and context pair, and return as output a
span of tokens from the context which is the best suitable option for the
answer to the input query string. The first stage of the IR framework employs
the BERT SQuAD model to select a word span from the input context which is a
possible contender for the answer to the input textual query. The answer thus
generated is passed on to the second stage of the framework, along with the
originally input textual query.

In the second stage, the BERT MRPC transformer architecture is utilized for
the generation of the probability metric. The job of the MRPC architecture is
to take in as input a pair of sentences and judge their semantic equivalence
on a scale from 0 to 1. In the proposed Literature Retrieval architecture, the
MRPC model serves to adjudicate whether the query, and the selected answer in
the first stage involved the same subject matter. The second stage of the IR
model outputs the probability score for the chosen context in the current
iteration.

Through the described framework, for each candidate document in the CORD-19
dataset, a number of probability scores are obtained corresponding to each
context chunk taken out of the document. The maximum of these scores is chosen
and assigned as the document-probability-score. The candidate documents are
ranked on the basis of their document-probability-scores and the top ranked
serve as the response of the Literature Retrieval system.

Table I: Literature Retrieval System Example Results(The search corpus taken
is a small subset of the CORD-19 dataset and the top 3 results from the IR
model has been recorded. The paper ids have been omitted for clarity of
reading.)

Query : What are the symptoms?
---
1. |  Multiple studies have confirmed that BCG is generally safe and can protect children against disseminated disease , including tuberculosis meningitis [ 1 , 2 ] . BCG also provides cross-protection against leprosy [ 3 ] . However , the success of BCG against pulmonary TB in adults is still debated , since randomized clini-cal trials have reported protection efficacy ranging from 0 - 80.
2. |  However , because reintroduction of ESX-1 into BCG does not restore full virulence , other genetic lesions are also involved [ 56 ] . As such , some strains are more virulent than others in animal models of infection [ 57 ] and also exhibit differential ability to induce adverse reactions ( reactogenicity ) following vaccination in neonates [ 58 ] .
3. |  ESX-5 is conserved in other pathogenic mycobacteria and reported to facilitate the cell-to-cell spread
Query : What is the structure?
1. |  Subsequent analyses of multiple vaccine strains have uncovered extensive genome diversity including both deletions and duplications in BCG substrains [ 18 , [ 20 ] [ 21 ] [ 22 ] . The phylogeny established by these molecular methods is consistent with the historical records of BCG dissemination [ 20 , 23 , 24 ] . For example , BCG strains acquired after 1927 exhibit the RD2 deletion , while nRD18 is only deleted in strains obtained after 1933 . Other genomic changes are exclusive to individual daughter strains , and are associated with vaccine production at specific locations [ 22 , 24 ] .A number of molecular techniques have been used to investigate genomic polymorphisms in BCG strains . Early efforts using subtractive hybridization [ 18 ] and spotted oligonucleotide arrays [ 20 , 22 , 25 ] effectively identified large sequence polymorphisms , but lacked the resolution to identify smaller changes .
2. |  termed B strain , which was responsible for a severe nosocomial outbreak of multidrug resistant TB in humans in Spain [ 50 , 51 ] . However , unlike the three BCG strains , the IS6110 insertion in the M. bovis B strain is located at 75 bp upstream of the start codon of phoP and is in the same orientation as phoP-phoR [ 50 ] . The potential effect of IS6110IS6110 insertion in the phoP promoter in BCG-Russia , -Moreau , and -Japan on phoP expression is described in the ’ Discussion ’ section . Three other novel phoP-phoR polymorphisms that likely impact their functions were also uncovered by our sequencing analysis . An identical , 11-bp deletion within the ORF of phoR was uncovered in BCG-Sweden and BCG-Birkhaug ( ACCGGACTGGG , nucleotides from 853689 to 853699 , M. tb genome coordinates ) . This deletion changes the amino acid sequence of 54 residues ( residues 432 to 485 ) in the C-terminal of PhoR. This polymorphism is different than the previously described 10 bp deletion within phoR present in BCG-Danish and BCG-Glaxo , which affects residues 91 - 485 [ 24 ] . BCG-Frappier also contains a single nucleotide deletion ( A at 852701 , M. tb genome coordinates ) , causing a frame-shift mutation that affect residues 103 - 485 of PhoR. Together , these results indicate that besides BCG-Danish and BCG-Glaxo ,
3. |  These include genes involved in the biosynthesis of lipid virulence factors PDIMs/PGLs , genes that encode the ESX family type VII secretion system , and the phoP-phoR two-component regulatory system .
Query : Regions affected?
1. |  The Middle East Respiratory Syndrome ( MERS ) crisis in Korea is coming to an end , but that ’s not the end of the story .
2. |  MERS-CoV is a human betacoronavirus responsible of a severe viral respiratory disease , first identified in Saudi Arabia in 2012 .
3. |  The WHO experts reminded us that hospital shopping greatly contributed to the rapid spread of MERS in Korea .
Query : antidote?
1. |  Rigorous evaluation of optimal antimicrobial and other therapeutic strategies to improve the clinical outcomes of this devastating combination is impeded by its sporadic occurrence and fulminant course . Although 838 children with confirmed or suspected 2009 pH1N1 were identified across 35 US pediatric intensive care units ( PICUs ) in 2009 , only 34 cases of MRSA coinfection were reported [ 5 ] .Intravenous vancomycin or clindamycin are recommended as the mainstay of therapy for treatment of hospitalized children with community-acquired ( CA ) pneumonia ( CAP ) if MRSA is suspected [ 6 ] . The addition of a second anti-MRSA agent is controversial [ 7 ] , partly because some combinations of commonly used antibiotics for MRSA , such as linezolid with vancomycin , have shown antagonistic effects in animal models of invasive MRSA infection [ 8 ] and in experimental in vitro assays [ 9 ] .
2. |  Shock requiring vasopressor support was use of a dopamine infusion >5 \u00b5g/kg/min or any epinephrine , norepinephrine , or phenylephrine infusion to maintain blood pressure .
3. |  data from in vitro models also suggest antagonism exists when vancomycin is combined with clindamycin or linezolid [ 7 ] , there is poor agreement between animal and human models of antibiotic antagonism or synergy when treating MRSA [ 38 ] .

Table II: Question Answering Results(The search corpus taken is a small subset
of the CORD-19 dataset)

Query |  Answer
---|---
Symptoms of COVID. |  Moderate , generalised symmetrical dilation of the ventricular system was present , with complete suppression of contents on FLAIR , indicating that the cerebrospinal fluid was not markedly abnormal .
Which chemicals can be used to kill the virus. |  Shock requiring vasopressor support was use of a dopamine infusion > 5 µg/kg/min or any epinephrine , norepinephrine , or phenylephrine infusion to maintain blood pressure .
Coronavirus symptoms. |  We excluded patients with preexisting lung disorders ; immune compromise ; mitochondrial , genetic , or neurologic disorders ; and/or preexisting cardiac diseases that increase the risk of infection or respiratory failure [ 24 ] .
What diseases are associated with Coronavirus. |  TEM showed the presence of characteristic small curvilinear lamellar stacks and electron-dense granular material , consistent morphologically with previously described intra-neuronal lipofuscins in cats , making the diagnosis of neuronal ceroid lipofuscinosis highly likely in this case .
Is there any antidote. |  Our analysis of the available data on time to presentation and our sensitivity analysis show that although longer time from symptom onset to PICU admission was associated with increased fatality , it was unlikely to explain the association between vancomycin monotherapy and death .
Vaccines for COVID. |  Although addition of clindamycin to vancomycin appears prudent in cases with high clinical suspicion of influenza-MRSA coinfection , clindamycin resistance must be monitored .
What is the structure of the virus. |  Biochemistry , including fasting ammonia and preprandial bile acids , and haematology were within normal limits .
Is there any medicine for COVID. |  Beta-lactam antibiotics were associated with increased S. aureus toxin expression in vitro [ 18 , 19 ] , and vancomycin had negligible effect .
Symptoms. |  compare MERS with tuberculosis .
Viral composition. |  FK506 binding protein 51 associates with and stabilizes BECN1 by scaffolding the assembly of a hetero-complex involving PHLPP , AKT1 , SKP2 and BECN1 that limits phosphorylation and thus activity of SKP2 .
Where is coronavirus found. |  MERS-CoV is a human betacoronavirus responsible of a severe viral respiratory disease , first identified in Saudi Arabia in 2012 .
Effects of COVID-19. |  The cat in this case demonstrated generalised and symmetrical brain cortical atrophy and secondary dilation of the ventricular system and intracranial subarachnoid space ( hydrocephalus ex vacuo ) .
Treatment of COVID-19. |  Symptomatic management is generally the mainstay of treatment .

Question Answering The Question Answering (QA) Model comprises an enhanced
version of the first stage of the proposed IR architecture. Similar to the
process for the IR framework, the candidate documents from the search corpus
(CORD-19) are subdivided into smaller paragraph chunks. Each of the obtained
chunks are iteratively streamed through the Question Answering architecture in
a two element tuple format along with the textual query string. Figure 2
conceptually describes the complete architecture for the proposed Question
Answering Model.

With assistance from the BERT SQuAD framework, the QA model selects a word
span from the input context which is the most probable answer for the given
textual query, congruent to the process followed in the first stage of the
Literature Retrieval Model. The model provides an answer span and a
corresponding score indicating the relative likelihood of that answer span.
The process is iteratively repeated for the various context chunks of
documents present in the search corpus and the answer span with the best
overall score is selected as the response of the QA model to the provided
textual query.

In order to tackle the non-availability of previously available annotated data
to train the transformer architectures for the specific domain in context, we
propose semi-manual rule based algorithms to train the neural network models
designed for the SQuAD and MRPC tasks.

For training SQuAD architectures, we follow a keyword centric format. We pre-
define a list of keywords and a keyword mapping dictionary which maps each of
the keywords to some of their synonyms. For example if the list of keywords is
chosen as,

$[`structure^{\prime},`symptoms^{\prime}]$

then one of the possible representations of the mapping dictionary can be,

$\\{`structure^{\prime}:[`structure^{\prime},`constituents^{\prime},`composition^{\prime}],$
$`symptoms^{\prime}:[`symptoms^{\prime},`effects^{\prime},`diseases^{\prime}]\\}$

For selecting the questions in the required (question, context) pair for the
SQuAD datafile format, we pre-define a list of queries.

Similar to the preprocessing step for our proposed model architectures, before
proceeding with the creation of training datasets, the available documents to
be used for training are divided into chunks of contexts. On selecting a
context from the available chunks, for each of the keywords in our defined
list of keywords, we choose the lines from that context which pertains to the
same subject-matter as the keyword does. Unlike all the other steps in our
training pipeline, this particular step is a manual one and serves as the main
temporal bottleneck of the proposed pipeline.

In order to choose the relevant lines, we take the assistance of the scispaCy
named entity recognition models [4]. For each (context, keyword) pairs, we

  * •

Find all the named entities in the context using one of the scispaCy NER
models.

  * •

Choose the entities having relevance to the current keyword.

  * •

Access the subtrees of the chosen entities and select the lines in the context
that contains those entities.

In this way, a dictionary consisting of the contexts and the lines selected
from them for each keyword in the keyword list, can be formed.

For any of the queries in our pre-defined list of queries, the query is
scanned for the presence of any of the words contained in the keyword mapping
dictionary and, if found, that word is mapped to the appropriate keyword in
the keyword list. Thus, a list of keywords that are present in the sentence
can be collected. The SQuAD training datafile consists of (question, answer,
context) triplets. In our proposed pipeline, these creation of these triplets
is implemented by the following steps:

  * •

Choose a query from the list of queries.

  * •

Choose a context chunk from the available chunks.

  * •

Extract the keywords present in the query and choose the appropriate lines
from the context as the answer to the query with referral from the dictionary
previously created.

The Microsoft Research Paraphrase Corpus (MRPC) task consists of checking
whether two sentences are semantically equivalent [2]. The MRPC trainfile
expects sentence sample pairs with scores of 1 or 0 indicating semantic
similarity and dissimilarity respectively. In order to create our question-
answer sentence pairs, we salvage the previously created SQuAD trainfile. For
creating the positive samples (the samples with a score of 1),

  * •

Select any query and one of its corresponding answers from the SQuAD trainfile

  * •

Split the selected answer into its constituent sentences. Our proposed
framework uses the NLTK punkt tokenizer for this purpose.

  * •

Choose any of the constituent sentences and the selected query as a positive
sample pair

The steps followed for the creation of the negative samples are sightly
different. We start with selecting a query and a context from the SQuAD
trainfile and subsequently select the lines from that context that are not
present among the answers for the query. As mentioned in the preceding
paragraph, the punkt tokenizer is used for sentence extraction. The generation
of the positive and negative samples is followed by a shuffling of the samples
to prevent any bias in training.

##  IV Experiment Results

Table I and II summarize our experiments for the two proposed architectures.
In order to exhibit the efficiency of the presented models, we select a very
small subset of the CORD-19 dataset as the search corpus for the experiments.

In table I, we choose four example user queries for the COVID-19 Literature
Retrieval solution. The framework returns a list of publication IDs and the
selected excerpt for each publication. The list is arranged in decreasing
order of relevance to the textual query provided as input. We select the top 3
results and present them in the table for each of the four example queries.
The publication IDs have been omitted for cogency. The proposed solution
provided the results which have high semantic and knowledge relevance with
given queries.

In table II, we list some user queries, by using them as questions, our
COVID-19 question answering solution is able to select proper text fragments
from the search corpus as answers. The predicted answers are sufficiently
relevant to the input questions and contain the effective knowledge or
information which is important in order to answer the given textual queries.

Though the number of queries our training samples contain is limited, unseen
queries can be answered by using word embeddings such as Word2Vec [3] or GloVe
[5] to calculate the similarity between the words in the unseen query and the
keywords in our keyword list. If the similarity with any of the keywords is
greater than a specified cutoff, that particular word in unseen query can be
replaced with that keyword and can subsequently be processed with an accuracy
closer to that of the queries available in the training scripts. For unseen
questions with proper nouns like the names of countries, chemicals, etc., for
example,

$``Coronavirus\ cases\ in\ Australia"$

or,

$``ChAdOx1\ nCoV-19\ as\ COVID\ vaccine"$

exact match of the proper noun with any of the words in the context, can be
used as a measure of score to rank the papers, along with the Literature
Retrieval architecture scores. Similar is the workaround for the proposed
Question-Answering model.

##  V Conclusion

In this paper, we define a novel COVID-19 Domain Literature Information
Retrieval framework which includes two tasks, COVID-19 literature retrieval,
and question answering. Based on Transformer Neural Network model, we propose
solutions for these two tasks respectively. In our solutions, the COVID-19
domain knowledge and particularity are considered in IR process. In this case,
our solutions achieve good IR results on CORD-19 dataset.

## References

  * [1] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”  In _arXiv preprint arXiv:1810.04805_ , 2018
  * [2] William B. Dolan and Chris Brockett  “Automatically Constructing a Corpus of Sentential Paraphrases”  In _IWP@IJCNLP_ , 2005
  * [3] Tomas Mikolov, Kai Chen, Greg Corrado and Jeffrey Dean  “Efficient Estimation of Word Representations in Vector Space”, 2013  arXiv:1301.3781 [cs.CL]
  * [4] Mark Neumann, Daniel King, Iz Beltagy and Waleed Ammar  “ScispaCy: Fast and Robust Models for Biomedical Natural Language Processing”  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ Florence, Italy: Association for Computational Linguistics, 2019, pp. 319–327  DOI: 10.18653/v1/W19-5034
  * [5] Jeffrey Pennington, Richard Socher and Christopher D. Manning  “Glove: Global Vectors for Word Representation”  In _EMNLP_ , 2014
  * [6] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev and Percy Liang  “SQuAD: 100, 000+ Questions for Machine Comprehension of Text”  In _ArXiv_ abs/1606.05250, 2016
  * [7] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser and Illia Polosukhin  “Attention is All you Need”  In _ArXiv_ abs/1706.03762, 2017
  * [8] Lucy Lu Wang, Kyle Lo, Yoganand Chandrasekhar, Russell Reas, Jiangjiang Yang, Doug Burdick, Darrin Eide, Kathryn Funk, Yannis Katsis, Rodney Kinney, Yunyao Li, Ziyang Liu, William Merrill, Paul Mooney, Dewey Murdick, Devvret Rishi, Jerry Sheehan, Zhihong Shen, Brandon Stilson, Alex Wade, Kuansan Wang, Nancy Xin Ru Wang, Chris Wilhelm, Boya Xie, Douglas Raymond, Daniel S. Weld, Oren Etzioni and Sebastian Kohlmeier  “CORD-19: The COVID-19 Open Research Dataset”, 2020  arXiv:2004.10706 [cs.DL]
  * [9] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, R’emi Louf, Morgan Funtowicz and Jamie Brew  “HuggingFace’s Transformers: State-of-the-art Natural Language Processing”  In _ArXiv_ abs/1910.03771, 2019


# Proof of a conjecture of Plummer and Zha

Maria Chudnovsky
Princeton University, Princeton, NJ 08544

Paul Seymour
Princeton University, Princeton, NJ 08544 Supported by NSF DMS-EPSRC grant
DMS-2120644.Supported by AFOSR grant A9550-19-1-0187.

(January 8, 2022; revised )

###### Abstract

Say a graph $G$ is a pentagraph if every cycle has length at least five, and
every induced cycle of odd length has length five. N. Robertson proposed the
conjecture that the Petersen graph is the only pentagraph that is three-
connected and internally 4-connected, but this was disproved by M. Plummer and
X. Zha in 2014. Plummer and Zha conjectured that every 3-connected, internally
4-connected pentagraph is three-colourable. We prove this: indeed, we will
prove that every pentagraph is three-colourable.

##  1 Introduction

Let us say a graph $G$ is a pentagraph if every cycle has length at least
five, and every induced cycle of odd length has length five. (All graphs in
this paper are finite, and have no loops or parallel edges.) Such graphs seem
to be richly structured; indeed N. Robertson [3] proposed the conjecture that
the Petersen graph is the only pentagraph that is three-connected and
internally 4-connected, although this was disproved by M. Plummer and X. Zha
[2] (see also [1]).

In the same paper, Plummer and Zha proposed the conjecture that all
3-connected, internally 4-connected pentagraphs have bounded chromatic number,
and the stronger conjecture that they are all three-colourable. The first was
proved by Xu, Yu, and Zha [4], who proved that all pentagraphs are four-
colourable; and we will prove the second. Our main theorem is:

###### 1.1

Every pentagraph is three-colourable.

The girth of $G$ is the minimum length of a cycle in $G$; a hole in $G$ is an
induced cycle of length at least four, and an odd hole means a hole with odd
length; and if $X\subseteq V(G)$, $G[X]$ denotes the subgraph induced on $X$.
We first prove the result of [4], because the proof is short and pretty:

###### 1.2

Every pentagraph is four-colourable.

Proof. It is enough to show that every connected pentagraph is four-
colourable. Let $G$ be a connected pentagraph, let $v_{0}\in V(G)$, and for
each $k\geq 0$ let $L_{k}$ be the set of vertices with distance exactly $k$
from $v_{0}$. Thus the sets $L_{0},L_{1},\ldots$ are pairwise disjoint and
have union $V(G)$; and for each $k\geq 1$, each vertex in $L_{k}$ has a
neighbour in $L_{k-1}$ and has no neighbour in $L_{0}\cup\cdots\cup L_{k-2}$.
Suppose that for some $k\geq 0$, $G[L_{k}]$ is not bipartite, and choose a
minimum such value of $k$. Thus $k\geq 1$; and since $G[L_{k}]$ is not
bipartite, it contains an odd cycle as a subgraph, and hence an induced odd
cycle, and hence a hole $C$ of length five (since $G$ is a pentagraph). Let
$C$ have vertices
$c_{1}\hbox{-}c_{2}\hbox{-}c_{3}\hbox{-}c_{4}\hbox{-}c_{5}\hbox{-}c_{1}$ in
order. For $1\leq i\leq 5$, let $d_{i}\in L_{k-1}$ be adjacent to $c_{i}$. It
follows that each of $d_{1},\ldots,d_{5}$ has only one neighbour in $V(C)$,
since $G$ has girth at least five, and hence $d_{1},\ldots,d_{5}$ are all
distinct. Thus $k\geq 2$. Since $G[L_{0}\cup\cdots\cup L_{k-2}]$ is connected,
and $d_{1},d_{3}$ both have a neighbour in $L_{k-2}$, there is an induced path
$P$ between $d_{1},d_{3}$ with interior in $L_{0}\cup\cdots\cup L_{k-2}$.
Since

$d_{1}\hbox{-}P\hbox{-}d_{3}\hbox{-}c_{3}\hbox{-}c_{4}\hbox{-}c_{5}\hbox{-}c_{1}\hbox{-}d_{1}$

is a hole of length at least six, it has even length and so $P$ has odd
length. Consequently

$d_{1}\hbox{-}P\hbox{-}d_{3}\hbox{-}c_{3}\hbox{-}c_{2}\hbox{-}c_{1}\hbox{-}d_{1}$

is an odd hole, and so it has length five, and therefore $d_{1}d_{3}$ is an
edge. Similarly $d_{3}d_{5},d_{5}d_{2},d_{2}d_{4},d_{4}d_{1}$ are edges, and
so $G[L_{k-1}]$ has a cycle of length five, contradicting the choice of $k$.

Thus $G[L_{k}]$ is bipartite for each $k$, and so $G$ is four-colourable. This
proves 1.2.

Now we turn to the proof of 1.1. This is a consequence of a stronger
statement, that every non-bipartite pentagraph is either isomorphic to the
Petersen graph, or has a vertex of degree at most two, or admits one of two
kinds of decomposition, that a minimal non-three-colourable pentagraph cannot
admit. Let us see these decompositions.

  * •

A $P_{3}$-cutset means an induced three-vertex path $P$ of $G$ such that
$G\setminus V(P)$ is disconnected.

  * •

A parity star-cutset means a set $X\subseteq V(G)$ such that $G\setminus X$ is
disconnected, and there is a vertex $x\in X$ such that $x$ is adjacent to
every other vertex in $X$, and there is a component $A$ of $G\setminus X$ such
that every two vertices in $X\setminus\\{x\\}$ are joined by an induced path
of even length with interior in $V(A)$. We call this a strong parity star-
cutset if $A$ can be chosen such that in addition $x$ has a neighbour in
$V(A)$.

We will prove:

###### 1.3

Let $G$ be a pentagraph. Then either

  * •

$G$ is bipartite; or

  * •

$G$ is isomorphic to the Petersen graph; or

  * •

$G$ has a vertex of degree at most two; or

  * •

$G$ admits a $P_{3}$-cutset or a strong parity star-cutset.

Proof of 1.1, assuming 1.3.  We prove by induction on $|V(G)|$ that every
pentagraph is three-colourable. Let $G$ be a pentagraph such that every
pentagraph with fewer vertices is three-colourable. If $G$ is isomorphic to
the Petersen graph, or some vertex has degree at most two, then $G$ is three-
colourable; so by 1.3 we may assume that $G$ admits a $P_{3}$-cutset or a
parity star-cutset (indeed, a strong parity star-cutset, but we do not need
“strong” here).

Suppose first that $G$ admits a $P_{3}$-cutset, and let
$v_{1}\hbox{-}v_{2}\hbox{-}v_{3}$ be an induced path such that
$G\setminus\\{v_{1},v_{2},v_{3}\\}$ is disconnected. Let $A_{1}$ be the union
of at least one and not all of the components of
$G\setminus\\{v_{1},v_{2},v_{3}\\}$, and let $A_{2}$ be the union of all the
other components. For $i=1,2$ let $G_{i}=G[A_{i}\cup\\{v_{1},v_{2},v_{3}\\}]$.
From the inductive hypothesis, both $G_{1}$ and $G_{2}$ are three-colourable;
let $\phi_{i}:V(G_{i})\rightarrow\\{1,2,3\\}$ be a three-colouring, for
$i=1,2$. We may assume that $\phi_{i}(v_{1})=1$ and $\phi_{i}(v_{2})=2$ for
$i=1,2$. Thus $\phi_{1}(v_{3}),\phi_{2}(v_{3})\in\\{1,3\\}$, and if
$\phi_{1}(v_{3})=\phi_{2}(v_{3})$ then $G$ is three-colourable. Thus we may
assume that $\phi_{1}(v_{3})=1$ and $\phi_{2}(v_{3})=3$. Let $H_{1}$ be the
subgraph of $G_{1}$ induced on the set of vertices $v\in V(G_{1})$ with
$\phi_{1}(v)\in\\{1,3\\}$. If $v_{1},v_{3}$ belong to different components of
$H_{1}$, then by exchanging colours in the component containing $v_{3}$, we
obtain another three-colouring of $G_{1}$ that can be combined with $\phi_{2}$
to show that $G$ is three-colourable. So we may assume that $v_{1},v_{3}$
belong to the same component of $H_{1}$, and so there is an induced path
$P_{1}$ of $H_{1}$ between $v_{1},v_{3}$. Consequently $P_{1}$ has even
length, and length at least four since $G$ has girth at least five. Define
$H_{2}$ in $G_{2}$ similarly: then similarly we may assume that $v_{1},v_{3}$
belong to the same component of $H_{2}$, and so there is an induced path
$P_{2}$ of $H_{2}$ between $v_{1},v_{3}$ with odd length, at least three. But
then $P_{1}\cup P_{2}$ is an induced cycle of $G$ of odd length at least
seven, a contradiction.

Now suppose that $G$ admits a parity star-cutset, and let $X\subseteq V(G)$
and $v\in V(G)\setminus X$, such that $v$ is adjacent to every vertex in $X$,
and $G\setminus(X\cup\\{v\\})$ is disconnected, and there is a component $A$
of $G\setminus(X\cup\\{v\\})$ such that every two vertices in $X$ are joined
by an induced path of even length with interior in $V(A)$. Choose $X$ minimal
with this property, and let $A_{1},\ldots,A_{k}$ be the components of
$G\setminus(X\cup\\{v\\})$, where every two vertices in $X$ are joined by an
induced path of even length with interior in $V(A_{1})$.

(1) For $1\leq i\leq k$ and for all distinct $x,x^{\prime}\in X$, every
induced path between $x,x^{\prime}$ with interior in $A_{i}$ has a length that
is even and at least four.

For all distinct $x,x^{\prime}\in X$, let $P_{1}(x,x^{\prime})$ be an induced
path of even length with interior in $V(A_{1})$. It follows that
$P_{1}(x,x^{\prime})$ has length at least four, since $v$ is adjacent to
$x,x^{\prime}$ and $G$ has girth at least five. For $2\leq i\leq k$, if
$x,x^{\prime}$ both have a neighbour in $A_{i}$, let $P_{i}(x,x^{\prime})$ be
an induced path between $x,x^{\prime}$ with interior in $A_{i}$. Thus
$P_{i}(x,x^{\prime})$ has length at least three, for the same reason. Since
$P_{1}(x,x^{\prime})\cup P_{i}(x,x^{\prime})$ is an induced cycle of length at
least seven, it follows that $P_{i}(x,x^{\prime})$ has even length, and length
at least four, for all choices of $x,x^{\prime}$ that both have a neighbour in
$A_{i}$; and therefore every induced path between $x,x^{\prime}$ with interior
in $A_{i}$ has even length at least four. From the minimality of $X$, it
follows that every vertex in $X$ has a neighbour in $A_{i}$ for $2\leq i\leq
k$; and so, by the same argument with $A_{1},A_{2}$ exchanged, every induced
path between $x,x^{\prime}$ with interior in $A_{1}$ has even length at least
four. This proves (1).

For $1\leq i\leq k$, let $G_{i}=G[V(A_{i})\cup X\cup\\{v\\}]$.

(2) For $1\leq i\leq k$, there is a three-colouring
$\phi_{i}:V(G_{i})\rightarrow\\{1,2,3\\}$ with $\phi_{i}(v)=1$ and
$\phi_{i}(x)=2$ for all $x\in X$.

From the inductive hypothesis, $G_{i}$ admits a three-colouring
$\phi_{i}:V(G_{i})\rightarrow\\{1,2,3\\}$ with $\phi_{i}(v)=1$. Choose
$\phi_{i}$ such that $\phi_{i}(x)=3$ for as few vertices $x\in X$ as possible.
We claim that $\phi_{i}(x)=2$ for all $x\in X$. To see this, let $X_{2}$ be
the set of $x\in X$ with $\phi_{i}(x)=2$, and let $X_{3}$ be the set of $x\in
X$ with $\phi_{i}(x)=3$. Thus $X_{2}\cup X_{3}=X$. Let $H$ be the subgraph of
$G_{i}$ induced on the set of vertices $u\in V(G_{i})$ with
$\phi_{i}(u)\in\\{2,3\\}$. Suppose that $X_{3}\neq\emptyset$, and let $C$ be a
component of $H$ that contains a vertex of $X_{3}$. By exchanging colours in
$C$, the choice of $\phi_{i}$ implies that some vertex of $X_{2}$ belong to
$C$, and so there is a minimal induced path $P$ of $H$ between $X_{2},X_{3}$,
which therefore has odd length; but from the minimality of $P$, all internal
vertices of $P$ belong to $A_{i}$, contradicting (1). This proves (2).

From (2) it follows that $G$ is three-colourable. This proves 1.3.

##  2 Pentagraphs that contain large parts of the Petersen graph

In this section we prove part of 1.3. A clique cutset of $G$ is a clique $X$
of $G$ such that $G\setminus X$ is disconnected. In a pentagraph $G$, every
clique has cardinality at most two, and so if $G$ has an edge and $G$ admits a
clique cutset, then $G$ admits a strong parity star-cutset. If $P$ is an
induced path, we denote the set of internal vertices of $P$ by $P^{*}$. Two
disjoint subsets $X,Y$ of $G$ are anticomplete if there are no edges between
$X,Y$. Let us say two nonadjacent vertices $s,t$ of a graph $H$ are linked if
there are induced paths $Q_{1},Q_{2}$ of $H$ both with ends $s,t$ and both of
length at least three, with lengths of different parity. We say that $s,t$ are
odd-linked if there is an induced path of $H$ with ends $s,t$ and with odd
length at least five.

We begin with:

###### 2.1

Let $G$ be a pentagraph that does not admit a clique cutset, and let $H$ be an
induced subgraph of $G$ with $H\neq G$ and $|V(H)|\geq 3$. Then either

  * •

there is a vertex $v\in V(G)\setminus V(G)$ with at least three neighbours in
$V(H)$ (and therefore every two neighbours of $v$ in $V(H)$ have distance at
least three in $H$); or

  * •

there exist nonadjacent $s,t\in V(H)$, and a vertex $v\in V(G)\setminus V(G)$
adjacent to $s,t$ and with no other neighbours in $V(H)$ (and therefore $s,t$
have distance at least three in $H$ and are not odd-linked in $H$); or

  * •

no vertex in $V(G)\setminus V(H)$ has more than one neighbour in $V(H)$, and
there exist nonadjacent $s,t\in V(H)$, not linked in $H$, and an induced path
$P$ of $G$ with length at least three, with ends $s,t$ and with
$P^{*}\subseteq V(G)\setminus V(H)$, such that every vertex of $H$ with a
neighbour in $P^{*}$ is adjacent to both $s,t$.

Proof. If some $v\in V(G)\setminus V(H)$ has at least three neighbours in
$V(H)$ then the first bullet is satisfied, since $G$ has girth at least five.
If some $v\in V(G)\setminus V(H)$ has exactly two neighbours $s,t$ in $V(H)$,
and $Q$ is an induced path of $H$ with ends $s,t$ and with odd length at least
five, then adding $v$ to $Q$ makes a long odd hole $G$, a contradiction; so
$s,t$ are not odd-linked and the second bullet is satisfied. Thus we may
assume that each vertex in $V(G)\setminus V(H)$ has at most one neighbour in
$V(H)$.

Let $C$ be a component of $G\setminus V(H)$. Since $G$ does not admit a clique
cutset, and $|V(H)|\geq 3$, it follows that there exist nonadjacent vertices
in $V(H)$ both with neighbours in $V(C)$. Thus there is an induced path $P$
with $P^{*}\subseteq V(C)$, with ends nonadjacent vertices of $C$. Choose $P$
with $P^{*}$ minimal, and let its ends be $s,t$. Since no vertex in
$V(G)\setminus V(H)$ has more than one neighbour in $V(H)$, it follows that
$P$ has length at least three. If $v\in V(H)$ has a neighbour in $P^{*}$, and
$v$ is nonadjacent to $s$ say, then from the minimality of $P^{*}$, it follows
that $v$ has only one neighbour in $P^{*}$ and that neighbour is adjacent to
$t$. Hence $v$ is nonadjacent to $t$, since $G$ has girth at least five; and
this contradicts the minimality of $P^{*}$. So every vertex of $H$ with a
neighbour in $P^{*}$ is adjacent to both $s,t$. Suppose that $s,t$ are linked
in $H$, and so there are induced paths $Q_{1},Q_{2}$ of $H$ between $s,t$,
both of length at least three, and with lengths of different parity. Thus
neither contains a vertex adjacent to both $s,t$, and so $Q_{1}^{*},Q_{2}^{*}$
are both anticomplete to $P^{*}$. Consequently both $P\cup Q_{1},P\cup Q_{2}$
are long holes, and one has odd length, a contradiction; and so $s,t$ are not
linked, and the third bullet is satisfied. This proves 2.1.

We deduce:

###### 2.2

Let $G$ be a pentagraph that has an induced subgraph isomorphic to the
Petersen graph. Then either $G$ is isomorphic to the Petersen graph, or $G$
admits a clique cutset.

Proof. Let $H$ be an induced subgraph of $G$ isomorphic to the Petersen graph.
No two vertices of $H$ have distance at least three in $H$. Moreover, every
two nonadjacent vertices of $H$ are linked in $H$. The result follows from
2.1. This proves 2.2.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$ Figure 1: $\mathcal{P}$ and $\mathcal{P}^{0}$.

Let $\mathcal{P}$ denote the Petersen graph, and let
$\mathcal{P}^{0},\mathcal{P}^{1},\mathcal{P}^{2}$ denote the graphs obtained
from $\mathcal{P}$ by deleting one edge, one vertex, and two adjacent vertices
respectively. (See figures 1 and 2.)

###### 2.3

Let $G$ be a pentagraph that has an induced subgraph isomorphic to
$\mathcal{P}^{0}$. Then either $G$ is isomorphic to $\mathcal{P}^{0}$, or $G$
admits a clique cutset.

Proof. Let $H$ be an induced subgraph of $G$ isomorphic to $\mathcal{P}^{0}$,
numbered as in figure 1. $(9,10)$ is the only pair of vertices of $H$ that
have distance more than two in $H$. Consequently no three vertices of $H$
pairwise have distance at least three; and every two vertices of $H$ with
distance at least three in $H$ are odd-linked in $H$. Moreover, every two
nonadjacent vertices are linked in $H$, and so the result follows from 2.1.
This proves 2.3.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$$2$$3$$4$$5$$6$$7$$8$ Figure 2:
$\mathcal{P}^{1}$ and $\mathcal{P}^{2}$.

###### 2.4

Let $G$ be a pentagraph that has an induced subgraph isomorphic to
$\mathcal{P}^{1}$. Then either $G$ is isomorphic to one of
$\mathcal{P},\mathcal{P}^{0},\mathcal{P}^{1}$, or $G$ admits a clique cutset.

Proof. Let $H$ be an induced subgraph of $G$ isomorphic to $\mathcal{P}^{1}$,
numbered as in figure 2. The only pairs of vertices that have distance at
least three in $H$ are the pairs of vertices in $\\{7,8,9\\}$. Thus if the
first bullet of 2.1 holds then $G$ contains $\mathcal{P}$ and the result
follows from 2.2. If the second bullet of 2.1 holds, then $G$ contains
$\mathcal{P}_{0}$ and the result follows from 2.3. Every two nonadjacent
vertices of $H$ are linked, so the third bullet of 2.1 does not hold. This
proves 2.4.

###### 2.5

Let $G$ be a pentagraph that has an induced subgraph isomorphic to
$\mathcal{P}^{2}$. Then either $G$ is isomorphic to one of
$\mathcal{P},\mathcal{P}^{0},\mathcal{P}^{1}$, $\mathcal{P}^{2}$, or $G$
admits a $P_{3}$-cutset or a strong parity star-cutset.

Proof. Let $H$ be an induced subgraph of $G$ isomorphic to $\mathcal{P}^{2}$,
numbered as in figure 2. The only pairs of vertices that have distance at
least three in $H$ are $(1,5)$ and $(3,7)$, so the first bullet of 2.1 does
not hold, and if the second bullet of 2.1 holds then $G$ contains
$\mathcal{P}^{1}$ and the result follows from 2.4 (since if $G$ has a clique
cutset then it has a strong parity star-cutset). Thus we may assume that the
third bullet of 2.1 holds, and in particular, no vertex in $V(G)\setminus
V(H)$ has more than one neighbour in $V(H)$.

Let us say the four sets

$\\{1,2,3\\},\\{3,4,5\\},\\{5,6,7\\},\\{7,8,1\\}$

are the sides of $H$. We may assume that $H\neq G$, and $G$ does not admit a
$P_{3}$-cutset, and so there is a connected subgraph $F$ of $G\setminus V(H)$
such that $N(F)$ is not a subset of any side of $H$, where $N(F)$ denotes the
set of vertices in $H$ with a neighbour in $V(F)$. Choose $F$ with $|V(F)|$
minimal. Since $N(F)$ is not a clique, there is an induced path $P$ with ends
$s,t\in N(F)$, nonadjacent; and as in 2.1, by choosing $P$ with $P^{*}$
minimal it follows that $s,t$ are not linked in $H$, and no vertex of $H$ has
a neighbour in $P^{*}$ except $s,t$ and possibly a common neighbour of $s$ and
$t$. The only nonadjacent pairs of vertices of $H$ that are not linked are
$(1,3),(3,5),(5,7),(7,1)$, so from the symmetry we may assume that $s=1$ and
$t=3$. Thus no vertex of $V(H)$ has a neighbour in $P^{*}$ except $1,3$ and
possibly $2$. Since $N(F)\not\subseteq\\{1,2,3\\}$, there is an induced path
$Q$ of $G$ with interior in $V(F)$ with one end in $P^{*}$ and the other in
$\\{4,5,6,7,8\\}$. Thus $Q$ has length at least two, and $F=P^{*}\cup Q^{*}$,
from the minimality of $|V(F)|$. Let the vertices of $Q$ be
$q_{1}\hbox{-}q_{2}\hbox{-}\cdots\hbox{-}q_{k}$ in order, where $k\geq 3$, and
$q_{1}\in P^{*}$, and $q_{k}\in\\{4,5,6,7,8\\}$. From the symmetry we may
assume that $q_{k}\in\\{4,5,6\\}$. The vertices $1,2,3$ may have neighbours in
$Q^{*}$, but since no vertex has more than one neighbour in $V(H)$, it follows
from the minimality of $|V(F)|$ that $q_{k}$ is the only vertex in
$\\{4,5,6,7,8\\}$ with a neighbour in $Q^{*}$.

(1) $q_{k}=4$.

There is an induced path $R$ between $1,q_{k}$ with interior in $P^{*}\cup
Q^{*}$, and it has length at least three since no vertex in $V(G)\setminus
V(H)$ has more than one neighbour in $V(H)$. If $q_{k}=5$, then one of

$1\hbox{-}R\hbox{-}5\hbox{-}4\hbox{-}8\hbox{-}1,1\hbox{-}R\hbox{-}5\hbox{-}6\hbox{-}7\hbox{-}8\hbox{-}1$

is a long odd hole, a contradiction; and if $q_{k}=6$, then one of

$1\hbox{-}R\hbox{-}6\hbox{-}5\hbox{-}4\hbox{-}8\hbox{-}1,1\hbox{-}R\hbox{-}6\hbox{-}7\hbox{-}8\hbox{-}1$

is a long odd hole, a contradiction. Since $q_{k}\in\\{4,5,6\\}$, this proves
(1).

$1$$2$$3$$4$$5$$6$$7$$8$$q_{1}$$P$$Q$ Figure 3: Step (2) of the proof of 2.5.

(2) $2$ has no neighbour in $P^{*}\cup Q^{*}$, and $P$ has length three.

(See figure 3.) Suppose that $2$ has a neighbour in $P^{*}\cup Q^{*}$; then
there is an induced path $R$ between $2,4$ with interior in $P^{*}\cup Q^{*}$,
and it has length at least three. But then one of

$2\hbox{-}R\hbox{-}4\hbox{-}5\hbox{-}6\hbox{-}2,2\hbox{-}R\hbox{-}4\hbox{-}8\hbox{-}7\hbox{-}6\hbox{-}2$

is a long odd hole, a contradiction. Thus $2$ has no neighbour in $P^{*}\cup
Q^{*}$. Consequently

$1\hbox{-}P\hbox{-}3\hbox{-}2\hbox{-}1,1\hbox{-}P\hbox{-}3\hbox{-}4\hbox{-}8\hbox{-}1$

are both holes of length at least five, and one has odd length; so $P$ has
length three. This proves (2).

$1$$2$$3$$4$$5$$6$$7$$8$$x_{1}$$y_{1}$$Q$ Figure 4: Step (3) of the proof of
2.5.

Let the vertices of $P$ be $1\hbox{-}y_{1}\hbox{-}x_{1}\hbox{-}3$ in order.

(3) $1$ has no neighbour in $V(Q)$, and so $q_{1}=x_{1}$.

Suppose that $1$ has a neighbour in $V(Q)$; then there is an induced path $R$
between $1,4$ with $R^{*}\subseteq V(Q)$. Since $N(R^{*})$ is not a subset of
a side of $H$, the minimality of $|V(F)|$ implies that $R^{*}=V(F)$, and in
particular $x_{1}\in R^{*}\subseteq V(Q)$. Since $x_{1}\notin Q^{*}$, it
follows that $q_{1}=x_{1}\in R^{*}$, and so $Q$ is a subpath of $R$,
contradicting that $1$ has a neighbour in $V(Q)$. This proves (3).

See figure 4. Let us say a $1\hbox{-}3$ handle is an induced path $R$ of $G$
of length three between $1,3$ such that $R^{*}\cap V(H)=\emptyset$ and no
vertex in $V(H)$ has a neighbour in $R^{*}$ except $1,3$. Thus $P$ is a
$1\hbox{-}3$ handle. Let $X$ be the set of neighbours of $3$ that belong to
$1\hbox{-}3$ handles, and let $Y$ be the set of all neighbours of $1$ that
belong to $1\hbox{-}3$ handles. Thus $x_{1}\in X$ and $y_{1}\in Y$, and $Y\cap
V(Q)=\emptyset$ by (3). If some $y\in Y$ has a neighbour in $Q^{*}$, then
$Q^{*}\cup\\{y\\}$ induces a connected subgraph of $G$ and $1,4$ both have
neighbours in this subgraph, contrary to the minimality of $|V(F)|$. Thus $Y$
is anticomplete to $Q^{*}$, and therefore $X\cap Q^{*}=\emptyset$. Let $D$ be
a connected induced subgraph of $G$, with $Q^{*}\subseteq V(D)$, maximal such
that $V(D)\cap(X\cup\\{3,4\\})=\emptyset$ and no vertex in
$Y\cup\\{1,2,5,6,7,8\\}$ has a neighbour in $V(D)$. It follows that $x_{1},4$
both have a neighbour in $D$. (See figure 5.)

$1$$2$$3$$4$$5$$6$$7$$8$$x_{1}$$y_{1}$$D$$Y$$X$ Figure 5: Handles in the proof
of 2.5.

For every two vertices in $X\cup\\{4\\}$, there is a path between them of
length four with middle vertex $1$; and this path is induced since $G$ has
girth at least five. We may assume that $X\cup\\{3,4\\}$ is not a strong
parity star-cutset, and so $D$ is not a component of
$G\setminus(X\cup\\{3,4\\})$. Consequently there is a vertex $v\in
V(G)\setminus V(D)$ with a neighbour in $V(D)$ and with $v\notin
X\cup\\{3,4\\}$. From the maximality of $D$, it follows that $v$ has a
neighbour in $Y\cup\\{1,2,5,6,7,8\\}$. Since there is a path between this
neighbour and $3$ of length at most three with vertex set in $V(H)\cup Y$, it
follows that $3,v$ are nonadjacent.

(4) $v$ has a unique neighbour in $Y\cup\\{1,2,5,6,7,8\\}$.

Suppose that $v$ has more than one neighbour in $Y\cup\\{1,2,5,6,7,8\\}$.
Every vertex in $V(G)\setminus V(H)$ has at most one neighbour in $V(H)$, as
we saw earlier, so we may assume that $v$ is adjacent to some $y\in Y$. Choose
$x\in X$ adjacent to $y$. All neighbours of $v$ in $V(H)\cup X\cup Y$ pairwise
have distance at least three in $G[V(H)\cup X\cup Y]$, and so $v$ has no more
neighbours in $Y$, and none in $\\{x,1,2,3,8\\}$. Since $v$ has two neighbours
in $Y\cup\\{1,2,5,6,7,8\\}$, it has a unique neighbour in $\\{5,6,7\\}$ (say
$u$), and therefore is nonadjacent to $4$. The paths

$y\hbox{-}1\hbox{-}8\hbox{-}7\hbox{-}6\hbox{-}5,y\hbox{-}1\hbox{-}8\hbox{-}4\hbox{-}5\hbox{-}6,y\hbox{-}x\hbox{-}3\hbox{-}4\hbox{-}8\hbox{-}7$

all have length five, and so $v$ cannot be adjacent to both ends of any of
them, and so $u\neq 5,6,7$, a contradiction. This proves (4).

Let $u$ be the unique neighbour of $v$ in $Y\cup\\{1,2,5,6,7,8\\}$. Let $R$ be
an induced path with interior in $V(D)\cup\\{v\\}$ between $x_{1},u$, and let
$S$ be a minimal path with interior in $V(D)\cup\\{v\\}$ between $u$ and
$\\{3,4\\}$. Thus one of $3,4$ is an end of $S$, and the other has no
neighbour in $V(S)$.

  * •

If $u=5$, the union of $R$ with one of
$x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}8\hbox{-}7\hbox{-}6\hbox{-}5,x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}2\hbox{-}6\hbox{-}5$
is a long odd hole.

  * •

If $u=6$, the union of $R$ with one of
$x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}8\hbox{-}7\hbox{-}6,x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}2\hbox{-}6$
is a long odd hole.

  * •

If $u=7$, the union of $R$ with one of
$x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}8\hbox{-}7,x_{1}\hbox{-}y_{1}\hbox{-}1\hbox{-}2\hbox{-}6\hbox{-}7$
is a long odd hole.

  * •

If $u=8$, let $T$ be an induced path with interior in $V(D)\cup\\{x_{1},v\\}$
between $3,u$; then $T$ has length at least three and the union of $T$ with
one of $3\hbox{-}2\hbox{-}6\hbox{-}7\hbox{-}8,3\hbox{-}2\hbox{-}1\hbox{-}8$ is
a long odd hole.

  * •

If $u=2$, let $T$ be an induced path with interior in $V(D)\cup\\{v\\}$
between $4,u$; then $T$ has length at least three and the union of $T$ with
one of $4\hbox{-}8\hbox{-}7\hbox{-}6\hbox{-}2,4\hbox{-}5\hbox{-}6\hbox{-}2$ is
a long odd hole.

  * •

If $u\in Y$ and $4$ is an end of $S$, then the union of $S$ with one of
$4\hbox{-}5\hbox{-}6\hbox{-}2\hbox{-}1\hbox{-}u,4\hbox{-}3\hbox{-}2\hbox{-}1\hbox{-}u$
is a long odd hole.

  * •

If $u\in Y$ and $3$ is an end of $S$, then $S$ has length at least three, and
the union of $S$ with one of
$3\hbox{-}2\hbox{-}1\hbox{-}u,3\hbox{-}4\hbox{-}8\hbox{-}1\hbox{-}u$ is a long
odd hole.

  * •

If $u=1$ and $4$ is an end of $S$, then $S$ has length at least three, and the
union of $S$ with one of
$4\hbox{-}5\hbox{-}6\hbox{-}2\hbox{-}1,4\hbox{-}3\hbox{-}2\hbox{-}1$ is a long
odd hole.

  * •

If $u=1$ and $3$ is an end of $S$, then $S$ has length at least three, and the
union of $S$ with one of $3\hbox{-}2\hbox{-}1,3\hbox{-}4\hbox{-}8\hbox{-}1$ is
an odd hole. So $S$ is a path of length three between 1,3 with interior in
$V(D)\cup\\{v\\}$, and no vertex of $H$ has a neighbour in $S^{*}$ except
$1,3$. Consequently $S$ is a $1\hbox{-}3$ handle, and so $V(D)\cup\\{v\\}$
contains a vertex in $X$, a contradiction.

Thus in all cases we obtain a contradiction. This proves 2.5.

##  3 Jumps across a pentagon

In view of 2.5, we turn our attention to pentagraphs that do not contain
$\mathcal{P}^{2}$ as an induced subgraph. Let $G$ be a pentagraph, and let $C$
be a hole of length five in $G$. No vertex in $V(G)\setminus V(C)$ has more
than one neighbour in $V(C)$, since $G$ has girth five. Let $P$ be an induced
path with both ends in $V(C)$, nonadjacent, and with no other vertices in
$V(C)$. We call $P$ a jump over $C$. Let $P$ have ends $s,t$; then we call $P$
an $s\hbox{-}t$ jump, and if $c$ is the vertex of $C$ adjacent to both $s,t$,
we say $P$ is a jump across $c$. If $P$ is an $s\hbox{-}t$ jump across $c$ and
no vertex of $V(C)\setminus\\{c,s,t\\}$ has a neighbour in $P^{*}$, we say $P$
is a local jump. If $P$ has length three we say that $P$ is a short jump.
Then, clearly,

  * •

all jumps have length at least three;

  * •

a jump $P$ is short if and only if no vertex of $V(C)\setminus V(P)$ has a
neighbour in $P^{*}$;

  * •

short jumps are local;

  * •

local jumps have odd length.

We need to analyze which pairs of vertices of $C$ can be joined by short and
local jumps. We begin with:

###### 3.1

Let $G$ be a pentagraph not containing $\mathcal{P}^{2}$, and let $C$ be a
hole of length five in $G$. If $P_{1},P_{2}$ are local jumps over $C$ with
exactly one common end $c$, then there is a short jump across $c$ with
interior in $P_{1}^{*}\cup P_{2}^{*}$, and consequently neither of them is
short.

Proof. (See figure 6.) Suppose that there are local jumps $P_{1},P_{2}$ over
$C$ with exactly one common end $c$ say, and there is no short jump across $c$
with interior in $P_{1}^{*}\cup P_{2}^{*}$. Choose such $P_{1},P_{2},c$ with
$P_{1}^{*}\cup P_{2}^{*}$ minimal. (Note that $P_{1}^{*}\cap P_{2}^{*}$ may be
nonempty.)

$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{1}$$a_{1}$$a_{2}$$b_{1}$$b_{2}$$P_{2}$$P_{1}$
Figure 6: Local jumps with a common end.

Let $C$ have vertices
$c_{1}\hbox{-}c_{2}\hbox{-}c_{3}\hbox{-}c_{4}\hbox{-}c_{5}\hbox{-}c_{1}$ in
order, where $P_{i}$ is a $c_{i}\hbox{-}c_{4}$ jump for $i=1,2$. For $i=1,2$,
let $a_{i},b_{i}$ be the vertices of $P_{i}$ adjacent to $c_{i}$ and $c_{4}$
respectively. For $i=1,2$, let $D_{i}=P_{i}^{*}\setminus\\{a_{i},b_{i}\\}$.

(1) $D_{1}\cup\\{b_{1}\\}$ is disjoint from and anticomplete to
$D_{2}\cup\\{b_{2}\\}$.

Suppose not. Since $b_{2}\notin V(P_{1})$ (because $P_{1}$ is local) and vice
versa, and $b_{1},b_{2}$ are not adjacent, it follows that either there is a
path of $G[D_{1}\cup D_{2}\cup\\{b_{1}\\}]$ from $b_{1}$ to $D_{2}$ or a path
of $G[D_{1}\cup D_{2}\cup\\{b_{2}\\}]$ from $b_{2}$ to $D_{1}$, and from the
symmetry we may assume the first. Hence $D_{2}\neq\emptyset$, so $P_{2}$ is
not short, and so $c_{3}$ has a neighbour in $D_{2}$. Consequently there is a
path between $c_{3}$ and $\\{c_{1},c_{5}\\}$ with interior in $D_{1}\cup
D_{2}\cup\\{b_{1}\\}$. Let $Q$ be a minimal path from $c_{3}$ to one of
$c_{1},c_{5}$, with interior in $D_{1}\cup D_{2}\cup\\{b_{1}\\}$. It follows
that one of $c_{1},c_{5}$ is an end of $Q$ and the other has no neighbour in
$Q^{*}$. Moreover, neither of $c_{2},c_{4}$ has a neighbour in $Q^{*}$, and so
$Q$ is a short jump. The choice of $P_{1},P_{2}$ implies that $Q$ is not a
short jump across $c_{4}$, and so $c_{1}$ is an end of $Q$ and $Q$ is a short
jump across $c_{2}$. There is no short jump across $c_{1}$ with interior in
$P_{1}^{*}\cup Q^{*}$, since $c_{2}$ has no neighbour in $P_{1}^{*}\cup
Q^{*}$; and since $P_{1}^{*}\cup Q^{*}$ is a proper subset of $P_{1}^{*}\cup
P_{2}^{*}$, this contradicts the minimality of $P_{1}^{*}\cup P_{2}^{*}$. This
proves (1).

If $a_{1}=a_{2}$, then since the paths $P_{1},P_{2}$ have odd length (because
they are local), (1) implies that $G[V(P_{1}\cup P_{2})]$ is an odd hole,
which therefore has length five; and so $P_{1},P_{2}$ are both short. But then
$G[V(C\cup P_{1}\cup P_{2})]$ is isomorphic to $\mathcal{P}^{2}$, a
contradiction. Thus $a_{1}\neq a_{2}$, and since $a_{1}\notin V(P_{2})$ and
vice versa, (1) implies that $P_{1}^{*},P_{2}^{*}$ are disjoint, and every
edge between them has an end in $\\{a_{1},a_{2}\\}$. Since $G[V(P_{1}\cup
P_{2})]$ is not a long odd hole, there is an edge between
$P_{1}^{*},P_{2}^{*}$; so from the symmetry we may assume that $a_{1}$ has a
neighbour in $D_{2}\cup\\{b_{2}\\}$, and therefore there is a
$c_{2}\hbox{-}c_{4}$ jump with interior in $\\{a_{1},b_{2}\\}\cup D_{2}$.
Since $c_{1},c_{5}$ have no neighbours in $\\{a_{1},b_{2}\\}\cup D_{2}$, this
$c_{2}\hbox{-}c_{4}$ jump is local, contrary to the minimality of
$P_{1}^{*}\cup P_{2}^{*}$. This proves 3.1.

To complete the proof of 1.3 we need:

###### 3.2

Let $G$ be a pentagraph not containing $\mathcal{P}^{2}$, and let $C$ be a
hole of length five in $G$. Then either:

  * •

some vertex of $C$ has degree two; or

  * •

$G$ admits a $P_{3}$-cutset; or

  * •

$G$ admits a strong parity star-cutset.

Proof. We claim first that we may number the vertices of $C$ as
$c_{1}\hbox{-}c_{2}\hbox{-}c_{3}\hbox{-}c_{4}\hbox{-}c_{5}\hbox{-}c_{1}$ in
order, such that:

(1) There are no short jumps across any of $c_{3},c_{4},c_{5}$, there are no
local jumps across $c_{4}$, and every local jump across $c_{3}$ or $c_{5}$
contains a vertex that is in a short jump.

Let $S$ be the set of $c\in V(C)$ such that there is a short jump across $c$,
and let $L$ be the set of $c\in V(C)$ such that there is a local jump across
$c$. Thus $S\subseteq L$. If $L$ is a clique, then (1) holds; so we may assume
that $c_{2},c_{5}\in L$, where the vertices of $C$ are
$c_{1}\hbox{-}c_{2}\hbox{-}c_{3}\hbox{-}c_{4}\hbox{-}c_{5}\hbox{-}c_{1}$ in
order. 3.1 implies that if $c,c^{\prime}\in L$ are nonadjacent, then neither
of them is in $S$; so $S$ is a clique, and every vertex of $S$ is adjacent to
every vertex of $L\setminus S$. In particular $S=\\{c_{1}\\}$, and
$L=\\{c_{5},c_{1},c_{2}\\}$. By 3.1 again, either every local jump across
$c_{2}$ contains a vertex in a short jump across $c_{1}$, or every local jump
across $c_{5}$ contains such a vertex; and from the symmetry we may assume the
second. This proves (1).

$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{1}$$X_{1}$$X_{2}$$X_{3}$$X_{5}$$D$ Figure 7:
The numbering of $C$.

Let $X_{1},X_{3}$ be the sets of vertices adjacent to $c_{1},c_{3}$
respectively that are in short jumps across $c_{2}$ (thus, $X_{1},X_{3}$ might
be empty); and similarly let $X_{2},X_{5}$ be the sets of vertices adjacent to
$c_{2},c_{5}$ respectively that are in short jumps across $c_{1}$. (See figure
7.) Let $X=X_{1}\cup X_{2}\cup X_{3}\cup X_{5}$. Thus $X$ is the set of all
vertices that belong to the interior of short jumps.

Now, $c_{4}$ has no neighbour in $X\cup\\{c_{1},c_{2}\\}$, but we may assume
that $c_{4}$ has degree at least three, and so there is a connected induced
subgraph $D$ such that $c_{4}$ has a neighbour in $V(D)$ and
$V(D)\cap(V(C)\cup X)=\emptyset$, and $D$ is maximal with these properties.
Let $N$ be the set of vertices in $V(C)\cup X$ that have a neighbour in
$V(D)$; so $c_{4}\in N$.

(2) $c_{1},c_{2}\notin N$, and $N\cap(X_{1}\cup X_{2})=\emptyset$.

Suppose not; then from the symmetry we may assume that either $c_{1}$ or some
member of $X_{1}$ belongs to $N$. Choose an induced path $P$ between
$c_{4},c_{1}$ with interior in $D\cup X_{1}$. Since $P^{*}\setminus
X_{1}\subseteq D$, it follows that $P^{*}\cap X\subseteq X_{1}$; and so
$|P^{*}\cap X|\leq 1$, since $P$ is induced. Suppose that $P$ is a local jump.
From 3.1, there is no short jump across $c_{2}$, and in particular
$X_{1}=\emptyset$; and so $V(P)\cap X=\emptyset$, contrary to (1). Thus $P$ is
not local. Let $Z$ be the set of vertices of $P$ that are not equal or
adjacent to $c_{1}$ or to $c_{4}$. Thus one of $c_{2},c_{3}$ has a neighbour
in $Z$, since $P$ is not local and $G$ has girth five. If also $c_{5}$ has a
neighbour in $P^{*}$, this neighbour also belongs to $Z$, and so there is a
minimal path $Q$ from $c_{5}$ to one of $c_{2},c_{3}$, with interior in $Z$.
Then no vertex of $C$ has a neighbour in $Q^{*}$ except the ends of $Q$, and
so $Q$ is short, and therefore two vertices of $Q^{*}$ belong to $X$; and
since $Q^{*}\subseteq P^{*}$. But this contradicts that $Q^{*}\subseteq P^{*}$
and $|P^{*}\cap X|\leq 1$. So $c_{5}$ has no neighbour in $P^{*}$. If $c_{2}$
has a neighbour in $P^{*}$, choose a minimal path between $c_{2},c_{4}$ with
interior in $P^{*}$; then this is a local jump across $c_{3}$, containing no
vertices in $X$, contrary to (1). Thus $c_{3}$ has a neighbour in $P^{*}$, and
hence in $Z$, and none of $c_{2},c_{4},c_{5}$ have a neighbour in $Z$; and so
there is a short jump across $c_{2}$ with interior in $P^{*}$, and therefore
two vertices of $P^{*}$ belong to $X$, a contradiction. This proves (2).

From (2) it follows that $N\subseteq X_{3}\cup
X_{5}\cup\\{c_{3},c_{4},c_{5}\\}$. If $N\subseteq\\{c_{3},c_{4},c_{5}\\}$ then
$G$ admits a $P_{3}$-cut, so we may assume from the symmetry that some
$x_{3}\in X_{3}$ belongs to $N$. If also $c_{5}$ or some $x_{5}\in X_{5}$ has
a neighbour in $D$, then there is an induced path $Q$ between $c_{3},c_{5}$
with interior in $V(D)\cup X_{3}\cup X_{5}$, and so neither of $c_{1},c_{2}$
have a neighbour in it, and it is therefore a local jump across $c_{4}$,
contrary to (1). Thus $N\subseteq X_{3}\cup\\{c_{3},c_{4}\\}$. But every two
vertices in $X_{3}\cup\\{c_{4}\\}$ are joined by an induced path of length
four with interior in $X_{1}\cup\\{c_{1},c_{5}\\}$, and so
$X_{3}\cup\\{c_{3},c_{4}\\}$ is a strong parity star-cutset. This proves 3.2.

Finally we deduce 1.3, which we restate:

###### 3.3

Let $G$ be a pentagraph. Then either

  * •

$G$ is bipartite; or

  * •

$G$ is isomorphic to the Petersen graph; or

  * •

$G$ has a vertex of degree at most two; or

  * •

$G$ admits a $P_{3}$-cutset or a strong parity star-cutset.

Proof. Since $\mathcal{P}^{0},\mathcal{P}^{1},\mathcal{P}^{2}$ all have
vertices of degree two, the result is true by 2.5 if $G$ contains an induced
subgraph isomorphic to $\mathcal{P}^{2}$; so we assume it does not. We may
assume that $G$ is not bipartite, and so it has a hole of length five. But
then the result follows from 3.2. This proves 3.3.

##  4 Construction?

Robertson’s conjecture, that the Petersen graph is the only non-bipartite
three-connected internally four-connected pentagraph, is false, but perhaps
something like it is true. For instance, in [1] the following is shown:

###### 4.1

The Petersen graph is the only cubic non-bipartite three-connected pentagraph.

A cubic three-connected pentagraph cannot admit a $P_{3}$-cutset (because the
middle vertex of the $P_{3}$ must have a neighbour on either side of the
cutset, by three-connectivity), and cannot admit a strong parity star-cutset
(because the “strong” condition implies that such a cutset would be a
$P_{3}$-cutset); and so in fact 4.1 follows easily from 1.3.

Is there some hope of extending 4.1 to larger classes of pentagraphs, or
indeed to a construction for all pentagraphs? In [2], Plummer and Zha
conjecture that every counterexample to Robertson’s conjecture is “close to
bipartite”, and one might hope that this too would follow from 1.3, but we do
not see how to show it. The problem is, let $G$ be a pentagraph, with a parity
star-cutset $X\cup\\{x\\}$, where $x$ is adjacent to every vertex in $X$, and
$A_{1},\ldots,A_{k}$ are the components of $G\setminus(X\cup\\{x\\})$. As in
the derivation of 1.1 from 1.3, we may assume that each vertex in $X$ has a
neighbour in each of $A_{1},\ldots,A_{k}$, and every induced path with ends in
$X$ and no other vertex has even length. Let $G_{i}$ be the subgraph induced
on $V(A_{i})\cup X\cup\\{x\\}$. We would like to apply an inductive hypothesis
that says each $G_{i}$ is “close to bipartite”, but even if $G$ is three-
connected and internally four-connected, we do not know that
$G_{1},\ldots,G_{k}$ are three-connected; for instance, they might have
vertices of degree two.

On the other hand, a parity star-cutset is a “reversible” decomposition, that
can be turned into something like a construction: in the notation above, if we
do not know that $G$ is a pentagraph, but we know that each of
$G_{1},\ldots,G_{k}$ is a pentagraph, it folows that $G$ is indeed a
pentagraph. So there is some hope here for a construction.

## Acknowledgements

This research was conducted during an Oberwolfach workshop on graph theory in
January 2022, and the authors are grateful to MFO for providing accommodations
and facilities. We would like to thank Xingxing Yu for introducing us to this
problem (at an open problem session during the workshop) and for supplying
background information.

## References

  * [1] D. Nelson, M. Plummer, N. Robertson and X. Xha, “On a conjecture concerning the Petersen graph”, Electronic J. Combinatorics 18 (2011), #P20.
  * [2] M. Plummer and X. Zha, “On a conjecture concerning the Petersen graph: part II”, Electronic J. Combinatorics 21 (2014), #P1.34.
  * [3] N. Robertson, personal communication to Xiaoya Zha.
  * [4] B. Xu, G. Yu, and X. Zha, “A note on chromatic number and induced odd cycles”, Electronic J. Combinatorics 24 (4) (2017), #P4.32.