# DialogStudio: Towards Richest and Most Diverse Unified Dataset Collection
for Conversational AI

Jianguo Zhang111Core contributors. Work completed during Kun’s internship at
Salesforce. 1, Kun Qian111Core contributors. Work completed during Kun’s
internship at Salesforce. 2, Zhiwei Liu222Also a major contributor. 1, Shelby
Heinecke1, Rui Meng1

Ye Liu1, Zhou Yu2, Huan Wang1, Silvio Savarese1, Caiming Xiong1

1 Salesforce AI 2 Columbia University

{jianguozhang, zhiweiliu, shelby.heinecke, ruimeng, yeliu,
<EMAIL_ADDRESS>

{ssavarese<EMAIL_ADDRESS>{kq2157<EMAIL_ADDRESS>

###### Abstract

Despite advancements in conversational AI, language models encounter
challenges to handle diverse conversational tasks, and existing dialogue
dataset collections often lack diversity and comprehensiveness. To tackle
these issues, we introduce DialogStudio: the largest and most diverse
collection of dialogue datasets, unified under a consistent format while
preserving their original information. Our collection encompasses data from
open-domain dialogues, task-oriented dialogues, natural language
understanding, conversational recommendation, dialogue summarization, and
knowledge-grounded dialogues, making it an incredibly rich and diverse
resource for dialogue research and model training. To further enhance the
utility of DialogStudio, we identify the licenses for each dataset and design
domain-aware prompts for selected dialogues to facilitate instruction-aware
fine-tuning. Furthermore, we develop conversational AI models using the
dataset collection, and our experiments in both zero-shot and few-shot
learning scenarios demonstrate the superiority of DialogStudio. To improve
transparency and support dataset and task-based research, as well as language
model pre-training, all datasets, licenses, codes, and models associated with
DialogStudio are made publicly
accessible111https://github.com/salesforce/DialogStudio.

##  1 Introduction

Recent years have seen remarkable progress in Conversational AI, primarily
driven by the advent of language models (Longpre et al., 2023; Zhang et al.,
2022b; Brown et al., 2020; Touvron et al., 2023). Despite the advancements,
these models often fall short when handling various tasks in a conversation
due to the lack of comprehensive and diverse training data. Current dialogue
datasets (Lin et al., 2021; Asri et al., 2017) are typically limited in size
and task-specific, which thus results in suboptimal ability in task-oriented
model performance. Additionally, the lack of dataset standardization impedes
model generalizability.

A few recent works (Longpre et al., 2023; Gupta et al., 2022; Ding et al.,
2023) have introduced a large collection of datasets, which includes diverse
tasks based on public datasets. For instance, FlanT5 (Longpre et al., 2023)
presents the flan collections with a wide array of datasets and tasks.
However, only a few of them are relevant to conversational AI. Although OPT
(Iyer et al., 2022) have incorporated collections with several dialogue
datasets, these collections remain inaccessible to the public. Other efforts
like InstructDial (Gupta et al., 2022) and ParlAI (Miller et al., 2017)
consist of more dialogue datasets, but they lack diversity and
comprehensiveness. For instance, ParlAI mainly includes open-domain dialogue
datasets, which are exclusively accessible through their platform. These
collections often process datasets into a sequence-to-sequence format to
support language model training, featuring input-output pairs such as dialogue
context and system response. However, they often overlook other crucial
dialogue information, constraining their utility for research interest on
individual datasets, tasks, and broader applications.

(a) Dataset Distribution

(b) Domain Coverage of TOD

Figure 1: (a) is the distribution of all datasets in DialogStudio. The outer
and inner circle list names of datasets and the associated categories,
respectively. (b) illustrates covered domains of Task-Oriented Dialogues in
DialogStudio.

To overcome the aforementioned challenges, we introduce DialogStudio, the most
comprehensive and diverse collection of publicly available dialogue datasets,
unified under a consistent format. By aggregating dialogue from various
sources, DialogStudio promotes holistic analysis and the development of models
adaptable to a variety of conversational scenarios. The collection spans an
extensive range of domains, aspects, and tasks, and it is inclusive of several
categories: Open-Domain Dialogues, Task-Oriented Dialogues, Natural Language
Understanding, Conversational Recommendation, Dialogue Summarization, and
Knowledge-Grounded Dialogues. Thus, it can provide support for research in
both individual dialogue tasks and large-scale language pre-training.

DialogStudio stands out not only for its comprehensive coverage but also for
its accessibility. It offers easy access with a unified format and documents.
A straightforward $\mathtt{load\\_dataset()}$ command through HuggingFace
allows users to seamlessly interact with the collection, and we have included
documentation for each dataset to enhance usability. We anticipate that this
collection will enable comprehensive and standardized training and evaluations
of dialogue models, fostering fair comparisons and propelling further
advancements in Conversational AI.

Furthermore, we identify dialogue domains for each dialogue and create
tailored prompts for selected datasets accordingly. Leveraging these datasets
from DialogStudio, we have constructed instruction-aware models, with
capacities ranging from 770M to 3B parameters. These models have the ability
to handle various external knowledge and are adept at both response generation
and general tasks, demonstrating the benefits of DialogStudio. The main
contributions of this paper are as follows:

  * •

We introduce DialogStudio, a meticulously curated collection of dialogue
datasets. These datasets are unified under a consistent format while retaining
their original information. We incorporate domain-aware prompts and identify
dataset licenses, making DialogStudio an exceptionally rich and diverse
resource for dialogue research and model training.

  * •

To promote transparency and facilitate research, we made our collected
datasets publicly accessible. Moreover, we have made concerted efforts to
enhance DialogStudio’s usability and will continue refining it for optimal
user experience.

  * •

We train conversational AI models based on DialogStudio, and these models have
demonstrated superior performance over strong baselines in both zero-shot and
few-shot learning scenarios.

##  2 Data analysis

###  2.1 Data Visualization

The dialogue datasets are compartmentalized into several categories: Open-
Domain Dialogues, Task-Oriented Dialogues (TOD), Natural Language
Understanding Dialogues (NLU), Conversational Recommendation (Conv-Rec),
Dialogue Summarization (Dial-Sum), and Knowledge-Grounded Dialogues (KG-Dial).
Figure 1(a) presents an overview of DialogStudio’s dataset categories. Note
that the category boundaries are fuzzy as some datasets span multiple
categories. For instance, SalesBot (Chiu et al., 2022) contains both casual
and task-oriented conversations. Analogously, MultiWOZ (Budzianowski et al.,
2018), a task-oriented dialogue corpus, incorporates knowledge bases and
dialogue acts to enhance knowledge-grounded generation. Additionally,
DialogStudio demonstrates its diversity by covering a wide range of domains,
part of which is shown in Figure 1(b).

(a) Overall, $\mu=4.14$

(b) Understanding, $\mu=4.39$

(c) Relevance, $\mu=4.80$

(d) Correctness, $\mu=4.38$

(e) Coherence, $\mu=4.47$

(f) Completeness, $\mu=4.16$

Figure 2: The score distribution for the dialogue quality.

###  2.2 Data Quality Investigation

Due to the existence of noise in dialogue, we develop a simple yet effective
way to verify the quality of the datasets. Specifically, we employ ChatGPT
(GPT-3.5-turbo) to evaluate the quality of system responses based on severall
perspectives (Mehri et al., 2022; Kim et al., 2022a), i.e., Understanding,
Relevance, Correctness, Coherence, Completeness and Overall quality.
Understanding assesses whether the model’s responses accurately reflect the
meaning and intent of the user’s inputs. Relevance demonstrates whether the
generated response should be directly related and appropriate to the preceding
user input and the context of the conversation. Coherence measures the logical
consistency of the model’s responses within the context of the conversation.
Completeness refers to whether the system’s responses fully address the user’s
queries or tasks. Overall quality comprehensively rates the quality of
dialogue. All scores are in the range of 1-5, and higher scores should only be
given to truly exceptional examples. We delicately design the prompt and ask
the ChatGPT model to strictly rate the score. After aligning ChatGPT and human
verification on sampled dialogues, we view a score greater than 3 as a good
quality dialog. Since there are a lot of datasets in DialogStudio, we select
33 datasets and the distributions of those scores are illustrated in Figure 2.
We also reveal the average score as the $\mu$ in each sub-caption. In general,
the dialogues show high qualities.

##  3 Datasets Unification and Access

We collect and process a wide range of datasets, involving different domains,
types, and tasks. Since these datasets originally contain various information
and format, we propose a unification strategy to process all the datasets such
that they can be loaded in the same data loader.

###  3.1 Unification

Before unifying the format of those datasets, we fixed several issues as
follows: 1) we remove those dialogues labeled as multi-turn dialogues, but
actually with only one turn and miss either user utterance or system
utterance. 2) We manually check the individual dialogues. If one dialogue
contains one or more empty user or system utterances, we fill utterances based
on corresponding dialogue contexts, dialogue acts, and dialogue information.

Additionally, we recognize the success of instruction tuning for dialogue
models and thus we manually pre-define five different prompt templates for
multi-turn dialogue datasets, such as This is a bot helping users to
{Task_Domain}. Given the dialogue context and external database, please
generate a relevant system response for the user. The {Task_Domain} is
associated with the dialogue domain and we manually create a corresponding
description. For example, if a dialogue is of domain travel, we set
{Task_Domain} as book a trip. A concrete example of the prompt is demonstrated
in Figure 3.

Figure 3: A dialogue format example. Left: original example, right: converted
example. Here We only show the first turn and partial information.

Next, we construct a uniform JSON dictionary format to store all relevant
information of each dialogue as illustrated in Figure 3. Compared with
existing works, DialogStudio covers more dialogue information and is easier to
retrieve the information for arbitrary dialogue-related tasks. Concretely, we
include all dialogue-related information, such as the dialogue ID, data split
label, domain, task, and content. Additionally, we identify the external
knowledge, dialogue state tracking (DST) knowledge, and intent knowledge in
the dialogue, which are the most beneficial knowledge for a dialogue.

Regarding external knowledge, we construct it based on information such as
databases and dialogue acts. Since each dialogue dataset focuses on specific
tasks or domains and has a different database and annotation schema, we unify
such information into external knowledge. For example, if the user is looking
for a hotel and asking for its address, the system response should be based on
both the search results from the database and the dialogue context. To
simulate the realistic situation and avoid directly providing the model with
the ground truth resulting hotel, we also randomly sample four other candidate
results and mix them with the ground truth result. All information is
flattened and converted into a string as external knowledge.

To complete tasks and generate coherent responses, a dialogue system needs to
track users’ requirements for the task. Those requirements are usually
represented as dialogue states. For example, regarding the hotel booking task,
a dialogue system needs to extract information such as price range and
locations to enable searching hotels in the database. The type of dialogue
states varies across different tasks and datasets. As such, it is hard for
dialogue systems to predict the values of those dialogue states if unknowing
the specific dialogue states the task covers. Therefore, we propose to insert
the schema, consisting of pre-defined dialogue state types and values for each
task, into the input sequence. For datasets like SGD (Rastogi et al., 2020),
which already provides annotation schema, we directly convert the dictionary-
structured schema into a string. For the rest datasets that have no such
schema file, we iterate over all dialogues and collect potential state
annotations to construct a schema. We provide domains, slot types, and slot
values in the schema string. For those categorized dialogue slots like ”hotel
star-ratings”, which have a fixed number of candidate values, we provide all
possible values. For others that have unlimited possible values, e.g. ”stay
night”, we randomly sample ten values, such that a model can learn what slot
values are relevant to these slot types. We put the turn-level ground-truth
DST information in ”dst”, and the general DST information under ”dst
knowledge”, as presented in Figure 3.

Analogously, intent prediction also requires models to know all possible
intent types for each task. Therefore, we extract the schema directly from the
schema file if it exists. As to datasets without schema, we also iterate over
all dialogue in the dataset to collect all potential intents. Then, we put the
turn-level ground-truth intent information into ”intent”, and the general
intents under ”intent knowledge”, as presented in Figure 3. Note that not all
datasets provide detailed annotation for dialogue states, intents, or even
databases. For dialogue state tracking and intent classification tasks, we
only process dialogues with corresponding annotations. Since all data is used
for response generation, we leave the external knowledge value for the
database blank if there is no related database in the original dataset.

###  3.2 Access and Ethics

As aforementioned in the format, our DialogStudio data is easy to access via
the JSON files. To make DialogStudio more maintainable and accessible, we
publish datasets on both GitHub and HuggingFace. GitHub mainly stores selected
dialogue examples and relevant documents. We sample 5 original dialogues and 5
converted dialogues for each dataset to facilitate users in comprehending our
format and examining the contents of each dataset. The complete DialogStudio
dataset is maintained in our HugginFace repository, where all the datasets can
be directly downloaded or loaded with the HuggingFace
$\mathtt{load\\_dataset()}$ API. We will continuously maintain and update both
GitHub and HuggingFace.

DialogStudio is built upon public research datasets, and we believe it is
important to clearly present the license associated with each of these
datasets. Consequently, we have included the original licenses for all
datasets. All these datasets are supportive of academic research, and some of
them also endorse commercial usage. The code that we employ falls under the
widely accepted Apache 2.0 license.

Regarding the ethical concerns, we admit that DialogStudio is collected by the
authors of this work and we did not hire external annotators. Since it
contains unified datasets across several categories, it supports various
research purposes from individual tasks and datasets to language model pre-
training.

##  4 Experiments

In this section, we present the pre-training details, methodologies, and
metrics used to assess the performance of our DialogOhana model. The
evaluation process aims to measure the model’s ability to both solve task-
oriented dialogues and understand general prompt-based instruction.

###  4.1 DialogOhana Pre-training

In this section, we introduce more details about how we conduct our pre-
training. In regards of training DialogOhana, we mix several datasets from
DialogStudio.

For task-oriented and conversational recommendation datasets, we selected
dialogues from a range of sources including KVRET (Eric et al., 2017),
AirDialogue (Wei et al., 2018), DSTC2-Clean (Mrkšić et al., 2017), CaSiNo
(Chawla et al., 2021), FRAMES (El Asri et al., ), WOZ2.0 (Mrkšić et al.,
2017), CraigslistBargains (He et al., 2018), Taskmaster1-2 (Byrne et al.,
2019), ABCD (Chen et al., 2021a), MulDoGO (Peskov et al., 2019), BiTOD (Lin et
al., 2021), SimJoint (Shah et al., 2018), STAR (Mosig et al., 2020), SGD
(Rastogi et al., 2020), OpenDialKG (Moon et al., 2019) and DuRecDial-2.0 (Liu
et al., 2021).

Meanwhile, for knowledge-grounded dialogues, we drew upon dataset from SQA
(Iyyer et al., 2017), SParC (Yu et al., 2019b), FeTaQA (Nan et al., 2022),
MultiModalQA (Talmor et al., 2021), CompWebQ (Talmor & Berant, 2018), CoSQL
(Yu et al., 2019a).

For open-domain dialogues, we sample dialogues from SODA (Kim et al., 2022a),
ProsocialDialog (Kim et al., 2022b), Chitchat (Myers et al., 2020).

For each dialogue dataset, we sample at most 11k dialogues. Additionaly, we
extracted around 11k dialogue turns from question-answering dialogues featured
in RACE (Lai et al., 2017), NarrativeQA (Kočiskỳ et al., 2018), SQUAD
(Rajpurkar et al., 2018), MCtest (Richardson et al., 2013), OpenBookQA
(Mihaylov et al., 2018), MultiRC (Khashabi et al., 2018). Here, a dialogue
turn refers to a pair consisting of a dialogue context and its corresponding
system response. The rest datasets in DialogStudio are preserved for future
evaluations and downstream fine-tuning.

For each dialogue during the training, we shape the available external
knowledge into a string, which is included in dialogue context, and instruct
the model to generate a dialogue response based on external knowledge. We use
the format Instruction \n <USER> user utterance <SYSTEM> system response
<USER> … <USER> user utterance \n <EXTERNAL KNOWLEDGE> supported knowledge to
train the model, where <USER>, <SYSTEM> and <EXTERNAL KNOWLEDGE> are special
tokens.

We follow the public HuggingFace transformer code (Wolf et al., 2020; Wang et
al., 2022) to train the model. For initializing our models, we adopt T5
(Raffel et al., 2020) and Flan-T5 (Longpre et al., 2023) as starting points to
respectively establish DialogStudio-T5 and DialogStudio-Flan-T5. For the
training of DialogStudio-Flan-T5, we exclude all translation-oriented tasks,
limiting the sample size for each Flan task to a maximum of 150 examples. This
leads to a cumulative total of 140,000 samples. We train the model up to 3
epochs with bfloat16 precision, a total batch size of 64. We set a constant
learning rate 5e-5 and 3e-5 for the large model and the 3B model,
respectively. Experiments are conducted using 16 A100 GPUs, each with 40GB of
GPU memory.

###  4.2 Evaluation for Response Generation

Settings. We evaluate the performance on CoQA (Reddy et al., 2019) and
MultiWOZ 2.2 (Zang et al., 2020). CoQA is a multi-turn conversational question
answering dataset with 8k conversations about text passages from seven diverse
domains. MultiWOZ 2.2 is one of the largest and most widely used multi-domain
task-oriented dialogue corpora with more than 10000 dialogues. Each dialogue
involves with one or more domains such as Train, Restaurant, Hotel, Taxi, and
Attraction. The dataset is challenging and complex due to the multi-domain
setting and diverse linguistic styles. Note that we exclude these two datasets
during the pre-training stage in case of data leakage.

For CoQA, we follow the original paper setting to answer question based on
external passage. For MultiWOZ 2.2, we consider the lexicalized dialogue-act-
to-response generation task where the model needs to consider both the
dialogue context and the dialogue acts during generation. We follow the prompt
from (Bang et al., 2023) to instruct models, i.e., Continue the dialogue as a
task-oriented dialogue system called SYSTEM. The answer of SYSTEM should
follow the ACTION provided next while answering the USER’s last utterance.

We focus on zero-shot evaluation and report the ROUGE-L and F1 score (Miller
et al., 2017), where ROUGE-L measures the longest common subsequence and F1
measures the Unigram F1 overlap between the prediction and ground-truth
response.

Baselines. We consider GODEL (Peng et al., 2022) and Flan-T5 (Longpre et al.,
2023) as our baselines. GODEL is a T5-based large pre-trained model for goal-
oriented dialogues. It is pre-trained with 551M multi-turn Reddit dialogues
and 5M knowledge-grounded and question-answering dialogues. Flan-T5 is an
instruction-aware model. It is also initialized from T5 and pre-trained on the
Flan collection, which consists of more than 1800 tasks and 400 datasets,
including dialogue datasets.

Results. Table 1 depicts the results from both zero-shot and few-shot testing.
Evidently, DialogStudio considerably surpasses the baseline models in terms of
zero-shot learning, exhibiting a robust generalized ability for response
generation in a zero-shot scenario.

Flan-T5-3B, on the other hand, underperforms in the task of generating
responses from dialog-acts. This model tends to produce incorrect dialog acts,
unnatural utterances, or terminates with an empty end token. One explanation
for this is that Flan-T5 models did not receive sufficient dialogue training
during the instruction-training phase on the Flan collections.

| CoQA | MultiWOZ
---|---|---
| ROUGE-L | F1 | ROUGE-L | F1
Flan-T5-3B (Longpre et al., 2023) | 37.1 | 37.2 | 7.0 | 7.4
Flan-T5-Large (Longpre et al., 2023) | 22.5 | 22.3 | 15.9 | 17.6
GODEL-Large (Peng et al., 2022) | 43.2 | 43.3 | 18.5 | 19.3
DialogStudio-T5-Large | 61.2 | 61.5 | 32.4 | 34.5
DialogStudio-Flan-T5-Large | 63.3 | 63.5 | 33.7 | 35.9
Table 1: Zero-shot results on CoQA and MultiWOZ 2.2.

|  | CR
---
(14 tasks)
| DAR
---
(7 tasks)
| TE
---
(27 tasks)
| avg.
---
(48 tasks)
OPT-30B (Zhang et al., 2022b) | 21.3/1.1 | 35.2/4.1 | 40.3/0.9 | 32.3/2.0
OPT-IML-30B (Iyer et al., 2022) | 37.4/41.6 | 51.4/51.8 | 54.7/47.8 | 47.9/47.1
OPT-175B (Zhang et al., 2022b) | 21.0/4.2 | 37.1/16.8 | 41.6/2.2 | 33.3/7.7
OPT-IML-175B (Iyer et al., 2022) | 39.0/49.8 |  61.2/60.2 | 54.3/51.0 |  51.5/53.6
Tk-INSTRUCT-11B (Wang et al., 2022) | 32.3/62.3 | 51.1/69.6 |  55.0/64.1 | 46.1/65.3
Tk-INSTRUCT-3B (Wang et al., 2022) | 38.4/51.3 | 45.7/58.5 | 48.4/52.8 | 44.2/54.2
DialogStudio-NIV2-T5-3B |  41.3/59.8 | 57.5/63.7 | 52.3/55.1 | 50.4/59.5

Table 2: 0-shot/2-shot/5-shot ROUGE-L testing results on unseen datasets and
unseen tasks. Results of baselines are reported by original papers. CR, DAR,
and TE, avg. are abbreviations for Coreference Resolution, Dialogue Act
Recognition, Textual Entailment, and average results, respectively.

###  4.3 Evaluation on Super-NaturalInstructions

Settings. NIV2 (Wang et al., 2022) introduces an instruction-tuning benchmark
with more than 1600 tasks. We select 3 categories with 44 tasks from the held-
out test set, which consists of 154 tasks, i.e., Coreference Resolution,
Dialogue Act Recognition, and Textual Entailment. The selected tasks and
datasets are unseen in the training stage. Specifically, we follow all
settings including metrics in Wang et al. (2022), i.e., we train the model
with instructions + 2 positive demonstrations and no negative demonstrations.
We fine-tune DialogStudio-T5-3B on the 756 training tasks.

Baselines. OPT (Zhang et al., 2022b) is a set of open decoder-only transformer
models pre-trained on 180B tokens. OPT-IML (Iyer et al., 2022) is an
instruction meta-learning model based on the OPT-IML bench with more than 1500
tasks. Tk-INSTRUCT (Wang et al., 2022) is initialized from T5 and further pre-
trained based on NIV2 collections. Note that we neglect Flan-T5 because it
trains with all the downstream datasets and tasks.

Results. Table 2 shows the 0-shot and 2-shot results on unseen datasets and
unseen tasks. Based on the average performance on 48 tasks, DialogStudio-
NIV2-T5-3B outperforms OPT-IML-175B by 5.9% on 2-shot learning with more than
50 times fewer model parameters, and it surpasses Tk-INSTRUCT-11B by 4.3% on
0-shot learning with more than 3 times fewer parameters. The performance
demonstrates the strong generalization ability of DialogStudio model. Compared
with Tk-INSTRUCT-3B, DialogStudio-NIV2-T5-3B achieves 6.2% and 5.3%
improvements on 0-shot and 2-shot learning respectively. Given that both Tk-
INSTRUCT and our DialogStudio-NIV2-T5-3B are fine-tuned from the T5 model,
this improvement indicates the effectiveness of pre-training with our dialogue
collection, DialogStudio.

###  4.4 Evaluation on MMLU and BBH

Table 3 presents results on MMLU (Hendrycks et al., 2020) and Big Bench Hard
(BBH) (Srivastava et al., 2022). When comparing the performance of
DialogStudio-Flan-T5 with Flan-T5, we observe a minor decrease. However, this
is accompanied by a significant improvement in dialogue capabilities.

| MMLU | BBH
---|---|---
| 0-SHOT | 5-SHOT | 3-SHOT
TK-INSTRUCT 11B (Wang et al., 2022) | - | 41.1 | 32.9
LLAMA 13B (Touvron et al., 2023) | - | 46.2 | 37.1
Vicuna 13B (Chiang et al., 2023) | - | 49.7 | 37.1
Flan-T5-Large (Longpre et al., 2023) | 41.5 | 41.9 | 37.1
Flan-T5-XL (Peng et al., 2022) | 48.7 | 49.3 | 40.2
OPT-IML-Max 30B (Iyer et al., 2022) | 46.3 | 43.2 | 31.3
DialogStudio-Flan-T5-Large | 40.1 | 40.9 | 34.2
DialogStudio-Flan-T5-3B | 48.3 | 47.8 | 40.3
Table 3: Test results on MMLU and BBH. Results come from original papers and
InstructEval (Chia et al., 2023)

##  5 CONCLUSION

In this paper, we introduce DialogStudio, a unified and diverse collection of
80 dialogue datasets, retaining their original information. Utilizing
DialogStudio, we developed the DialogOhana models, demonstrating superior
performance in both zero-shot and few-shot learning scenarios. We release both
DialogStudio and DialogOhana to foster transparency and support research into
datasets, tasks, and pre-training models for conversational AI.

## References

  * Asri et al. (2017) Layla El Asri, Hannes Schulz, Shikhar Sharma, Jeremie Zumer, Justin Harris, Emery Fine, Rahul Mehrotra, and Kaheer Suleman.  Frames: a corpus for adding memory to goal-oriented dialogue systems.  _arXiv preprint arXiv:1704.00057_ , 2017.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022.
  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.  _arXiv preprint arXiv:2302.04023_ , 2023.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Budzianowski et al. (2018) Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Ultes Stefan, Ramadan Osman, and Milica Gašić.  Multiwoz - a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2018.
  * Byrne et al. (2019) Bill Byrne, Karthik Krishnamoorthi, Chinnadhurai Sankar, Arvind Neelakantan, Ben Goodrich, Daniel Duckworth, Semih Yavuz, Amit Dubey, Kyu-Young Kim, and Andy Cedilnik.  Taskmaster-1: Toward a realistic and diverse dialog dataset.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 4516–4525, 2019.
  * Casanueva et al. (2020) Iñigo Casanueva, Tadas Temčinas, Daniela Gerz, Matthew Henderson, and Ivan Vulić.  Efficient intent detection with dual sentence encoders.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pp. 38–45, 2020.
  * Casanueva et al. (2022) Iñigo Casanueva, Ivan Vulić, Georgios Spithourakis, and Paweł Budzianowski.  Nlu++: A multi-label, slot-rich, generalisable dataset for natural language understanding in task-oriented dialogue.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pp. 1998–2013, 2022.
  * Chawla et al. (2021) Kushal Chawla, Jaysa Ramirez, Rene Clever, Gale Lucas, Jonathan May, and Jonathan Gratch.  Casino: A corpus of campsite negotiation dialogues for automatic negotiation systems.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 3167–3185, 2021.
  * Chen et al. (2021a) Derek Chen, Howard Chen, Yi Yang, Alexander Lin, and Zhou Yu.  Action-based conversations dataset: A corpus for building more in-depth task-oriented dialogue systems.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 3002–3017, 2021a.
  * Chen et al. (2023) Maximillian Chen, Alexandros Papangelis, Chenyang Tao, Seokhwan Kim, Andy Rosenbaum, Yang Liu, Zhou Yu, and Dilek Hakkani-Tur.  Places: Prompting language models for social conversation synthesis.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pp. 814–838, 2023.
  * Chen et al. (2022a) Mingda Chen, Zewei Chu, Sam Wiseman, and Kevin Gimpel.  SummScreen: A dataset for abstractive screenplay summarization.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 8602–8615, Dublin, Ireland, May 2022a. Association for Computational Linguistics.  URL https://aclanthology.org/2022.acl-long.589.
  * Chen et al. (2020) Wenhu Chen, Hanwen Zha, Zhiyu Chen, Wenhan Xiong, Hong Wang, and William Yang Wang.  Hybridqa: A dataset of multi-hop question answering over tabular and textual data.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 1026–1036, 2020.
  * Chen et al. (2021b) Yulong Chen, Yang Liu, Liang Chen, and Yue Zhang.  DialogSum: A real-life scenario dialogue summarization dataset.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pp. 5062–5074, Online, August 2021b. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.449.  URL https://aclanthology.org/2021.findings-acl.449.
  * Chen et al. (2022b) Zhiyu Chen, Bing Liu, Seungwhan Moon, Chinnadhurai Sankar, Paul A Crook, and William Yang Wang.  Ketod: Knowledge-enriched task-oriented dialogue.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pp. 2581–2593, 2022b.
  * Chia et al. (2023) Yew Ken Chia, Pengfei Hong, Lidong Bing, and Soujanya Poria.  Instructeval: Towards holistic evaluation of instruction-tuned large language models.  _arXiv preprint arXiv:2306.04757_ , 2023.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.  _See https://vicuna. lmsys. org (accessed 14 April 2023)_ , 2023.
  * Chiu et al. (2022) Ssu Chiu, Maolin Li, Yen-Ting Lin, and Yun-Nung Chen.  Salesbot: Transitioning from chit-chat to task-oriented dialogues.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 6143–6158, 2022\.
  * Coope et al. (2020) Samuel Coope, Tyler Farghly, Daniela Gerz, Ivan Vulić, and Matthew Henderson.  Span-convert: Few-shot span extraction for dialog with pretrained conversational representations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 107–121, 2020.
  * Coucke et al. (2018) Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, et al.  Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces.  _arXiv preprint arXiv:1805.10190_ , 2018.
  * Dinan et al. (2018) Emily Dinan, Stephen Roller, Kurt Shuster, Angela Fan, Michael Auli, and Jason Weston.  Wizard of wikipedia: Knowledge-powered conversational agents.  _arXiv preprint arXiv:1811.01241_ , 2018.
  * Dinan et al. (2019) Emily Dinan, Varvara Logacheva, Valentin Malykh, Alexander H. Miller, Kurt Shuster, Jack Urbanek, Douwe Kiela, Arthur D. Szlam, Iulian Serban, Ryan Lowe, Shrimai Prabhumoye, Alan W. Black, Alexander I. Rudnicky, Jason Williams, Joelle Pineau, Mikhail S. Burtsev, and Jason Weston.  The second conversational intelligence challenge (convai2).  _ArXiv_ , abs/1902.00098, 2019.
  * Ding et al. (2023) Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Zhi Zheng, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou.  Enhancing chat language models by scaling high-quality instructional conversations.  _arXiv preprint arXiv:2305.14233_ , 2023.
  * (24) Layla El Asri, Hannes Schulz, Shikhar Sharma, Jeremie Zumer, Justin Harris, Emery Fine, Rahul Mehrotra, and Kaheer Suleman.  Frames: A corpus for adding memory to goal-oriented dialogue systems.
  * Eric et al. (2017) Mihail Eric, Lakshmi Krishnan, Francois Charette, and Christopher D Manning.  Key-value retrieval networks for task-oriented dialogue.  In _Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue_ , pp. 37–49, 2017.
  * Eric et al. (2020) Mihail Eric, Rahul Goel, Shachi Paul, Abhishek Sethi, Sanchit Agarwal, Shuyang Gao, Adarsh Kumar, Anuj Goyal, Peter Ku, and Dilek Hakkani-Tur.  Multiwoz 2.1: A consolidated multi-domain dialogue dataset with state corrections and state tracking baselines.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pp. 422–428, 2020.
  * Fabbri et al. (2021) Alexander Fabbri, Faiaz Rahman, Imad Rizvi, Borui Wang, Haoran Li, Yashar Mehdad, and Dragomir Radev.  ConvoSumm: Conversation summarization benchmark and improved abstractive summarization with argument mining.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 6866–6880, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.535.  URL https://aclanthology.org/2021.acl-long.535.
  * Feigenblat et al. (2021) Guy Feigenblat, Chulaka Gunasekara, Benjamin Sznajder, Sachindra Joshi, David Konopnicki, and Ranit Aharonov.  TWEETSUMM - a dialog summarization dataset for customer service.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pp. 245–260, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  URL https://aclanthology.org/2021.findings-emnlp.24.
  * Gliwa et al. (2019) Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer.  SAMSum corpus: A human-annotated dialogue dataset for abstractive summarization.  In _Proceedings of the 2nd Workshop on New Frontiers in Summarization_ , pp. 70–79, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-5409.  URL https://www.aclweb.org/anthology/D19-5409.
  * Gu et al. (2021) Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su.  Beyond iid: three levels of generalization for question answering on knowledge bases.  In _Proceedings of the Web Conference 2021_ , pp. 3477–3488, 2021\.
  * Gupta et al. (2022) Prakhar Gupta, Cathy Jiao, Yi-Ting Yeh, Shikib Mehri, Maxine Eskenazi, and Jeffrey P Bigham.  Instructdial: Improving zero and few-shot generalization in dialogue through instruction tuning.  _arXiv preprint arXiv:2205.12673_ , 2022.
  * Gupta et al. (2018) Sonal Gupta, Rushin Shah, Mrinal Mohit, Anuj Kumar, and Mike Lewis.  Semantic parsing for task oriented dialog using hierarchical representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 2787–2792, 2018.
  * Hayati et al. (2020) Shirley Anugrah Hayati, Dongyeop Kang, Qingxiaoyang Zhu, Weiyan Shi, and Zhou Yu.  Inspired: Toward sociable recommendation dialog systems.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 8142–8152, 2020.
  * He et al. (2018) He He, Derek Chen, Anusha Balakrishnan, and Percy Liang.  Decoupling strategy and generation in negotiation dialogues.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 2333–2343, 2018.
  * Hemphill et al. (1990) Charles T Hemphill, John J Godfrey, and George R Doddington.  The atis spoken language systems pilot corpus.  In _Speech and Natural Language: Proceedings of a Workshop Held at Hidden Valley, Pennsylvania, June 24-27, 1990_ , 1990.
  * Hendrycks et al. (2020) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Iyer et al. (2022) Srinivasan Iyer, Xi Victoria Lin, Ramakanth Pasunuru, Todor Mihaylov, Dániel Simig, Ping Yu, Kurt Shuster, Tianlu Wang, Qing Liu, Punit Singh Koura, et al.  Opt-iml: Scaling language model instruction meta learning through the lens of generalization.  _arXiv preprint arXiv:2212.12017_ , 2022.
  * Iyyer et al. (2017) Mohit Iyyer, Wen-tau Yih, and Ming-Wei Chang.  Search-based neural structured learning for sequential question answering.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1821–1831, 2017\.
  * Janin et al. (2003) Adam Janin, Don Baron, Jane Edwards, Dan Ellis, David Gelbart, Nelson Morgan, Barbara Peskin, Thilo Pfau, Elizabeth Shriberg, Andreas Stolcke, et al.  The icsi meeting corpus.  In _2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings.(ICASSP’03)._ , volume 1, pp. I–I. IEEE, 2003.
  * Khashabi et al. (2018) Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth.  Looking beyond the surface:a challenge set for reading comprehension over multiple sentences.  In _Proceedings of North American Chapter of the Association for Computational Linguistics (NAACL)_ , 2018.
  * Kim et al. (2022a) Hyunwoo Kim, Jack Hessel, Liwei Jiang, Peter West, Ximing Lu, Youngjae Yu, Pei Zhou, Ronan Le Bras, Malihe Alikhani, Gunhee Kim, Maarten Sap, and Yejin Choi.  Soda: Million-scale dialogue distillation with social commonsense contextualization.  _ArXiv_ , abs/2212.10465, 2022a.
  * Kim et al. (2022b) Hyunwoo Kim, Youngjae Yu, Liwei Jiang, Ximing Lu, Daniel Khashabi, Gunhee Kim, Yejin Choi, and Maarten Sap.  Prosocialdialog: A prosocial backbone for conversational agents.  _arXiv preprint arXiv:2205.12688_ , 2022b.
  * Kočiskỳ et al. (2018) Tomáš Kočiskỳ, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette.  The narrativeqa reading comprehension challenge.  _Transactions of the Association for Computational Linguistics_ , 6:317–328, 2018.
  * Komeili et al. (2022) Mojtaba Komeili, Kurt Shuster, and Jason Weston.  Internet-augmented dialogue generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 8460–8478, 2022\.
  * (45) Wessel Kraaij, Thomas Hain, Mike Lincoln, and Wilfried Post.  The ami meeting corpus.
  * Lai et al. (2017) Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy.  Race: Large-scale reading comprehension dataset from examinations.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pp. 785–794, 2017.
  * Larson et al. (2019) Stefan Larson, Anish Mahendran, Joseph J Peper, Christopher Clarke, Andrew Lee, Parker Hill, Jonathan K Kummerfeld, Kevin Leach, Michael A Laurenzano, Lingjia Tang, et al.  An evaluation dataset for intent classification and out-of-scope prediction.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 1311–1316, 2019.
  * Lee et al. (2019) S Lee, H Schulz, A Atkinson, J Gao, K Suleman, L El Asri, M Adada, M Huang, S Sharma, W Tay, et al.  Multi-domain task-completion dialog challenge.  _Dialog system technology challenges_ , 8(9), 2019.
  * Li et al. (2018a) Raymond Li, Samira Ebrahimi Kahou, Hannes Schulz, Vincent Michalski, Laurent Charlin, and Chris Pal.  Towards deep conversational recommendations.  In _Advances in Neural Information Processing Systems 31 (NIPS 2018)_ , 2018a.
  * Li et al. (2018b) Xiujun Li, Yu Wang, Siqi Sun, Sarah Panda, Jingjing Liu, and Jianfeng Gao.  Microsoft dialogue challenge: Building end-to-end task-completion dialogue systems.  _arXiv preprint arXiv:1807.11125_ , 2018b.
  * Li et al. (2020) Yu Li, Kun Qian, Weiyan Shi, and Zhou Yu.  End-to-end trainable non-collaborative dialog system.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 8293–8302, 2020.
  * Lin et al. (2021) Zhaojiang Lin, Andrea Madotto, Genta Indra Winata, Peng Xu, Feijun Jiang, Yuxiang Hu, Chen Shi, and Pascale Fung.  Bitod: A bilingual multi-domain dataset for task-oriented dialogue modeling.  _NeurIPS 2021 Track on Datasets and Benchmarks_ , 2021.
  * Liu et al. (2013) Jingjing Liu, Panupong Pasupat, Scott Cyphers, and Jim Glass.  Asgard: A portable architecture for multilingual dialogue systems.  In _2013 IEEE International Conference on Acoustics, Speech and Signal Processing_ , pp. 8386–8390. IEEE, 2013.
  * Liu et al. (2019) Xingkun Liu, Arash Eshghi, Pawel Swietojanski, and Verena Rieser.  Benchmarking natural language understanding services for building conversational agents.  _arXiv preprint arXiv:1903.05566_ , 2019.
  * Liu et al. (2021) Zeming Liu, Haifeng Wang, Zheng-Yu Niu, Hua Wu, and Wanxiang Che.  Durecdial 2.0: A bilingual parallel corpus for conversational recommendation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 4335–4347, 2021.
  * Longpre et al. (2023) Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V Le, Barret Zoph, Jason Wei, et al.  The flan collection: Designing data and methods for effective instruction tuning.  _arXiv preprint arXiv:2301.13688_ , 2023.
  * Martin et al. (2020) Scott Martin, Shivani Poddar, and Kartikeya Upasani.  Mudoco: corpus for multidomain coreference resolution and referring expression generation.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pp. 104–111, 2020.
  * Mehri et al. (2022) Shikib Mehri, Jinho Choi, Luis Fernando D’Haro, Jan Deriu, Maxine Eskenazi, Milica Gasic, Kallirroi Georgila, Dilek Hakkani-Tur, Zekang Li, Verena Rieser, et al.  Report from the nsf future directions workshop on automatic evaluation of dialog: Research directions and challenges.  _arXiv preprint arXiv:2203.10012_ , 2022.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  In _EMNLP_ , 2018.
  * Miller et al. (2017) Alexander H Miller, Will Feng, Adam Fisch, Jiasen Lu, Dhruv Batra, Antoine Bordes, Devi Parikh, and Jason Weston.  Parlai: A dialog research software platform.  _arXiv preprint arXiv:1705.06476_ , 2017.
  * Moon et al. (2019) Seungwhan Moon, Pararth Shah, Anuj Kumar, and Rajen Subba.  Opendialkg: Explainable conversational reasoning with attention-based walks over knowledge graphs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 845–854, 2019.
  * Mosig et al. (2020) Johannes EM Mosig, Shikib Mehri, and Thomas Kober.  Star: A schema-guided dialog dataset for transfer learning.  _arXiv preprint arXiv:2010.11853_ , 2020.
  * Mrkšić et al. (2017) Nikola Mrkšić, Diarmuid Ó Séaghdha, Tsung-Hsien Wen, Blaise Thomson, and Steve Young.  Neural belief tracker: Data-driven dialogue state tracking.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1777–1788, 2017\.
  * Mukherjee et al. (2022) Rajdeep Mukherjee, Abhinav Bohra, Akash Banerjee, Soumya Sharma, Manjunath Hegde, Afreen Shaikh, Shivani Shrivastava, Koustuv Dasgupta, Niloy Ganguly, Saptarshi Ghosh, and Pawan Goyal.  ECTSum: A new benchmark dataset for bullet point summarization of long earnings call transcripts.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 10893–10906, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  URL https://aclanthology.org/2022.emnlp-main.748.
  * Myers et al. (2020) Will Myers, Tyler Etchart, and Nancy Fulda.  Conversational scaffolding: An analogy-based approach to response prioritization in open-domain dialogs.  2020\.
  * Nan et al. (2021) Linyong Nan, Dragomir Radev, Rui Zhang, Amrit Rau, Abhinand Sivaprasad, Chiachun Hsieh, Xiangru Tang, Aadit Vyas, Neha Verma, Pranav Krishna, et al.  Dart: Open-domain structured data record to text generation.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 432–447, 2021.
  * Nan et al. (2022) Linyong Nan, Chiachun Hsieh, Ziming Mao, Xi Victoria Lin, Neha Verma, Rui Zhang, Wojciech Kryściński, Hailey Schoelkopf, Riley Kong, Xiangru Tang, et al.  Fetaqa: Free-form table question answering.  _Transactions of the Association for Computational Linguistics_ , 10:35–49, 2022.
  * Parikh et al. (2020) Ankur Parikh, Xuezhi Wang, Sebastian Gehrmann, Manaal Faruqui, Bhuwan Dhingra, Diyi Yang, and Dipanjan Das.  Totto: A controlled table-to-text generation dataset.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 1173–1186, 2020.
  * Pasupat & Liang (2015) Panupong Pasupat and Percy Liang.  Compositional semantic parsing on semi-structured tables.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 1470–1480, 2015.
  * Peng et al. (2022) Baolin Peng, Michel Galley, Pengcheng He, Chris Brockett, Lars Liden, Elnaz Nouri, Zhou Yu, Bill Dolan, and Jianfeng Gao.  Godel: Large-scale pre-training for goal-directed dialog.  _arXiv preprint arXiv:2206.11309_ , 2022.
  * Peskov et al. (2019) Denis Peskov, Nancy Clarke, Jason Krone, Brigi Fodor, Yi Zhang, Adel Youssef, and Mona Diab.  Multi-domain goal-oriented dialogues (multidogo): Strategies toward curating and annotating large scale dialogue data.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 4526–4536, 2019.
  * Qian et al. (2022) Kun Qian, Satwik Kottur, Ahmad Beirami, Shahin Shayandeh, Paul A Crook, Alborz Geramifard, Zhou Yu, and Chinnadhurai Sankar.  Database search results disambiguation for task-oriented dialog systems.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 1158–1173, 2022.
  * Quan et al. (2019) Jun Quan, Deyi Xiong, Bonnie Webber, and Changjian Hu.  Gecor: An end-to-end generative ellipsis and co-reference resolution model for task-oriented dialogue.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 4547–4557, 2019.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551, 2020.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang.  Know what you don’t know: Unanswerable questions for squad.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pp. 784–789, 2018\.
  * Rameshkumar & Bailey (2020) Revanth Rameshkumar and Peter Bailey.  Storytelling with dialogue: A Critical Role Dungeons and Dragons Dataset.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 5121–5134, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.459.  URL https://aclanthology.org/2020.acl-main.459.
  * Rashkin et al. (2019) Hannah Rashkin, Eric Michael Smith, Margaret Li, and Y-Lan Boureau.  Towards empathetic open-domain conversation models: a new benchmark and dataset.  In _ACL_ , 2019.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 8689–8696, 2020.
  * Reddy et al. (2019) Siva Reddy, Danqi Chen, and Christopher D Manning.  Coqa: A conversational question answering challenge.  _Transactions of the Association for Computational Linguistics_ , 7:249–266, 2019.
  * Richardson et al. (2013) Matthew Richardson, Christopher JC Burges, and Erin Renshaw.  Mctest: A challenge dataset for the open-domain machine comprehension of text.  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , pp. 193–203, 2013.
  * Shah et al. (2018) Pararth Shah, Dilek Hakkani-Tür, Gokhan Tür, Abhinav Rastogi, Ankur Bapna, Neha Nayak, and Larry Heck.  Building a conversational agent overnight with dialogue self-play.  _arXiv preprint arXiv:1801.04871_ , 2018.
  * Srivastava et al. (2022) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_ , 2022.
  * Talmor & Berant (2018) Alon Talmor and Jonathan Berant.  The web as a knowledge-base for answering complex questions.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pp. 641–651, 2018.
  * Talmor et al. (2021) Alon Talmor, Ori Yoran, Amnon Catav, Dan Lahav, Yizhong Wang, Akari Asai, Gabriel Ilharco, Hannaneh Hajishirzi, and Jonathan Berant.  Multimodalqa: Complex question answering over text, tables and images.  _ICLR_ , 2021.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wang et al. (2022) Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, et al.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ nlp tasks.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 5085–5109, 2022.
  * Wei et al. (2018) Wei Wei, Quoc Le, Andrew Dai, and Jia Li.  Airdialogue: An environment for goal-oriented dialogue research.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 3844–3854, 2018.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations_ , pp. 38–45, 2020.
  * Yih et al. (2016) Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh.  The value of semantic parse labeling for knowledge base question answering.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pp. 201–206, 2016\.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 3911–3921, 2018.
  * Yu et al. (2019a) Tao Yu, Rui Zhang, Heyang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, et al.  Cosql: A conversational text-to-sql challenge towards cross-domain natural language interfaces to databases.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 1962–1979, 2019a.
  * Yu et al. (2019b) Tao Yu, Rui Zhang, Michihiro Yasunaga, Yi Chern Tan, Xi Victoria Lin, Suyi Li, Heyang Er, Irene Li, Bo Pang, Tao Chen, et al.  Sparc: Cross-domain semantic parsing in context.  _arXiv preprint arXiv:1906.02285_ , 2019b.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen.  Multiwoz 2.2: A dialogue dataset with additional annotation corrections and state tracking baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pp. 109–117, 2020.
  * Zhang et al. (2022a) Jianguo Zhang, Kazuma Hashimoto, Yao Wan, Zhiwei Liu, Ye Liu, Caiming Xiong, and S Yu Philip.  Are pre-trained transformers robust in intent classification? a missing ingredient in evaluation of out-of-scope intent detection.  In _Proceedings of the 4th Workshop on NLP for Conversational AI_ , pp. 12–20, 2022a.
  * Zhang et al. (2022b) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022b.
  * Zhong et al. (2021) Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, and Dragomir Radev.  QMSum: A New Benchmark for Query-based Multi-domain Meeting Summarization.  In _North American Association for Computational Linguistics (NAACL)_ , 2021.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  _arXiv preprint arXiv:1709.00103_ , 2017.
  * Zhu et al. (2021) Chenguang Zhu, Yang Liu, Jie Mei, and Michael Zeng.  Mediasum: A large-scale media interview dataset for dialogue summarization.  _arXiv preprint arXiv:2103.06410_ , 2021.

Appendix

Table 4 and Table 5 lists datasets included in DialogStudio. Initially, we
present a partial list of these datasets. For more comprehensive and up-to-
date information, please refer to our GitHub page.

NLU | NLU++ (Casanueva et al., 2022)
---|---
BANKING77-OOS (Zhang et al., 2022a)
BANKING77 (Casanueva et al., 2020)
RESTAURANTS8K (Coope et al., 2020)
CLINC150 (Larson et al., 2019)
CLINC-Single-Domain-OOS-banking (Zhang et al., 2022a)
CLINC-Single-Domain-OOS-credit_cards (Zhang et al., 2022a)
HWU64 (Liu et al., 2019)
SNIPS (Coucke et al., 2018)
SNIPS-NER (Coucke et al., 2018)
DSTC8-SGD (Coope et al., 2020)
TOP (Gupta et al., 2018)
TOP-NER (Gupta et al., 2018)
ATIS-NER (Hemphill et al., 1990)
ATIS (Hemphill et al., 1990)
MIT-MOVIE (Liu et al., 2013)
MIT-RESTAURANT (Liu et al., 2013)
TOD | KVRET (Eric et al., 2017)
AirDialogue (Wei et al., 2018)
DSTC2-Clean (Mrkšić et al., 2017)
CaSiNo (Chawla et al., 2021)
FRAMES (El Asri et al., )
WOZ2.0 (Mrkšić et al., 2017)
CraigslistBargains (He et al., 2018)
Taskmaster1 (Byrne et al., 2019)
Taskmaster2 (Byrne et al., 2019)
Taskmaster3 (Byrne et al., 2019)
ABCD (Chen et al., 2021a)
MulDoGO (Peskov et al., 2019)
BiTOD (Lin et al., 2021)
SimJointGEN (Shah et al., 2018)
SimJointMovie (Shah et al., 2018)
SimJointRestaurant (Shah et al., 2018)
STAR (Mosig et al., 2020)
SGD (Rastogi et al., 2020)
MultiWOZ2_1 (Eric et al., 2020)
MultiWOZ2_2 (Zang et al., 2020)
HDSA-Dialog (Chen et al., 2021a)
MS-DC (Li et al., 2018b)
GECOR (Quan et al., 2019)
Disambiguation (Qian et al., 2022)
MetaLWOZ (Lee et al., 2019)
KETOD (Chen et al., 2022b)
MuDoCo (Martin et al., 2020)
Table 4: List of datasets included in DialogStudio (a). KG-Dial | SQA (Iyyer et al., 2017)
---|---
SParC (Yu et al., 2019b)
FeTaQA (Nan et al., 2022)
MultiModalQA (Talmor et al., 2021)
CompWebQ (Talmor & Berant, 2018)
CoSQL (Yu et al., 2019a)
CoQA (Reddy et al., 2019)
Spider (Yu et al., 2018)
ToTTo (Parikh et al., 2020)
WebQSP (Yih et al., 2016)
WikiSQL (Zhong et al., 2017)
WikiTQ (Pasupat & Liang, 2015)
DART (Nan et al., 2021)
GrailQA (Gu et al., 2021)
HybridQA (Chen et al., 2020)
MTOP (Chen et al., 2020)
UltralChat-Assistance (Ding et al., 2023)
Wizard_of_Wikipedia (Dinan et al., 2018)
Wizard_of_Internet (Komeili et al., 2022)
Dial-Sum | TweetSumm (Feigenblat et al., 2021)
SAMSum (Gliwa et al., 2019)
DialogSum (Chen et al., 2021b)
AMI (Kraaij et al., )
ICSI (Janin et al., 2003)
QMSum (Zhong et al., 2021)
MediaSum (Zhu et al., 2021)
ECTSum (Mukherjee et al., 2022)
SummScreen_ForeverDreaming (Chen et al., 2022a)
SummScreen_TVMegaSite (Chen et al., 2022a)
CRD3 (Rameshkumar & Bailey, 2020)
ConvoSumm (Fabbri et al., 2021)
Open-Domain | ChitCHAT (Myers et al., 2020)
SODA Kim et al. (2022a)
Prosocial (Kim et al., 2022b)
HH-RLHF (Bai et al., 2022)
Empathetic (Rashkin et al., 2019)
ConvAI2 (Dinan et al., 2019)
AntiScam (Li et al., 2020)
PLACES3.5 (Chen et al., 2023)
Conv-Rec | SalesBot (Chiu et al., 2022)
Redial (Li et al., 2018a)
Inspired (Hayati et al., 2020)
DuRecDial 2.0 (Liu et al., 2021)
OpendialKG (Moon et al., 2019)
Table 5: List of datasets included in DialogStudio (b).


# The minmin coalition number in graphs

1Davood Bakhshesh and 2Michael A. Henning

1Department of Computer Science
University of Bojnord
Bojnord, Iran
Email<EMAIL_ADDRESS>

2Department of Mathematics and Applied Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa
Email<EMAIL_ADDRESS>Research supported in part by the University of
Johannesburg and the South African National Research Foundation

###### Abstract

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of
$V(G)\setminus S$ is adjacent to a vertex in $S$. A coalition in $G$ consists
of two disjoint sets of vertices $X$ and $Y$ of $G$, neither of which is a
dominating set but whose union $X\cup Y$ is a dominating set of $G$. Such sets
$X$ and $Y$ form a coalition in $G$. A coalition partition, abbreviated
$c$-partition, in $G$ is a partition $\mathcal{X}=\\{X_{1},\ldots,X_{k}\\}$ of
the vertex set $V(G)$ of $G$ such that for all $i\in[k]$, each set
$X_{i}\in\mathcal{X}$ satisfies one of the following two conditions: (1)
$X_{i}$ is a dominating set of $G$ with a single vertex, or (2) $X_{i}$ forms
a coalition with some other set $X_{j}\in\mathcal{X}$. Let ${\cal
A}=\\{A_{1},\ldots,A_{r}\\}$ and ${\cal B}=\\{B_{1},\ldots,B_{s}\\}$ be two
partitions of $V(G)$. Partition ${\cal B}$ is a refinement of partition ${\cal
A}$ if every set $B_{i}\in{\cal B}$ is either equal to, or a proper subset of,
some set $A_{j}\in{\cal A}$. Further if ${\cal A}\neq{\cal B}$, then ${\cal
B}$ is a proper refinement of ${\cal A}$. Partition ${\cal A}$ is a minimal
$c$-partition if it is not a proper refinement of another $c$-partition.
Haynes et al. [AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659] defined
the minmin coalition number $c_{\min}(G)$ of $G$ to equal the minimum order of
a minimal $c$-partition of $G$. We show that $2\leq c_{\min}(G)\leq n$, and we
characterize graphs $G$ of order $n$ satisfying $c_{\min}(G)=n$. A polynomial-
time algorithm is given to determine if $c_{\min}(G)=2$ for a given graph $G$.
A necessary and sufficient condition for a graph $G$ to satisfy
$c_{\min}(G)\geq 3$ is given, and a characterization of graphs $G$ with
minimum degree $2$ and $c_{\min}(G)=4$ is provided.

Keywords: Coalition number; Domination number; Coalition partition
AMS subject classification: 05C69

##  1 Introduction

A set $S$ of vertices in a graph $G$ is a _dominating set_ if every vertex in
$V(G)\setminus S$ is adjacent to a vertex in $S$. The _domination number_
$\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. If
$A,B\subseteq S$, then set $A$ _dominates_ the set $B$ if every vertex $b\in
B$ belongs to $A$ or is adjacent to a vertex of $A$. The study of domination
in graphs is an active area of research in graph theory. A thorough treatment
of this topic can be found in recent so-called “domination books” [6, 7, 8,
9].

For graph theory notation and terminology, we generally follow [8].
Specifically, let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$,
and of order $n(G)=|V(G)|$ and size $m(G)=|E(G)|$. Two adjacent vertices in
$G$ are _neighbors_. The _open neighborhood_ of a vertex $v$ in $G$ is
$N_{G}(v)=\\{u\in V\,\colon\,uv\in E\\}$ and the _closed neighborhood of $v$_
is $N_{G}[v]=\\{v\\}\cup N_{G}(v)$. We denote the degree of $v$ in $G$ by
$\deg_{G}(v)$, and so $\deg_{G}(v)=|N_{G}(v)|$. The minimum and maximum
degrees in $G$ are denoted by $\delta(G)$ and $\Delta(G)$, respectively. An
_isolated vertex_ in $G$ is a vertex of degree $0$ in $G$. A graph is
_isolate_ -_free_ if it contains no isolated vertex. A vertex $v$ is a
_universal vertex_ , also called a _full vertex_ in the literature, if
$N_{G}[v]=V(G)$, that is, $\deg_{G}(v)=n(G)-1$. If the graph $G$ is clear from
the context, we simply write $V$, $E$, $n$, $m$, $\deg(v)$, $N(v)$, and $N[v]$
rather than $V(G)$, $E(G)$, $n(G)$, $m(G)$, $\deg_{G}(v)$, $N_{G}(v)$, and
$N_{G}[v]$, respectively.

We denote a _path_ and _cycle_ on $n$ vertices by $P_{n}$ and $C_{n}$,
respectively, and we denote a _complete graph_ on $n$ vertices by $K_{n}$. A
_complete bipartite graph_ with partite sets of cardinalities $r$ and $s$ we
denote by $K_{r,s}$. A _star_ is a complete bipartite graph $K_{1,s}$ where
$s\geq 2$. A _nontrivial tree_ is a tree of order at least $2$. A partition of
a set is a grouping of its elements into non-empty subsets, in such a way that
every element of the set is included in exactly one subset.

A _coalition_ in a graph $G$ consists of two disjoint sets of vertices $X$ and
$Y$ of $G$, neither of which is a dominating set but whose union $X\cup Y$ is
a dominating set of $G$. Such sets $X$ and $Y$ _form a coalition_ in $G$. A
_coalition partition_ , called a $c$-_partition_ , in $G$ is a partition
$\Psi=\\{V_{1},\ldots,V_{k}\\}$ of $V(G)$ such that for all $i\in[k]$, the set
$V_{i}$ is either a singleton dominating set or forms a coalition with another
set $V_{j}$ for some $j$, where $j\in[k]\setminus\\{i\\}$. The _coalition
number_ , $C(G)$, in $G$ equals the maximum order $k$ of a $c$-partition of
$G$. Coalitions in graphs were introduced and first studied by Haynes,
Hedetniemi, Hedetniemi, McRae, and Mohan [2], and have subsequently been
studied, for example, in [5, 3, 4]. Their research primarily focused on
examining coalition numbers in trees and cycles. In [3], they established
upper bounds on the coalition number of a graph in terms of its minimum and
maximum degree. Bakhshesh et al. in [1] characterized graphs $G$ of order $n$
with $\delta(G)\geq 1$ and $C(G)=n$. They also identified all trees $T$ of
order $n$ with $C(T)=n-1$.

In [2], Haynes et al. introduced the _refinement_ of a coalition partition and
defined a _minimal coalition partition_. Let ${\cal
A}=\\{A_{1},\ldots,A_{r}\\}$ and ${\cal B}=\\{B_{1},\ldots,B_{s}\\}$ be two
partitions of $V(G)$. Partition ${\cal B}$ is a _refinement_ of partition
${\cal A}$, denoted ${\cal A}\leq{\cal B}$, if every set $B_{i}\in{\cal B}$ is
either equal to, or a proper subset of, some set $A_{j}\in{\cal A}$. Further
if ${\cal A}\neq{\cal B}$, then ${\cal B}$ is a _proper refinement_ of ${\cal
A}$, denoted ${\cal A}<{\cal B}$. The following observation follows from the
definition of a proper refinement of a coalition partition.

###### Observation 1

([2]) If $\Psi=\\{V_{1},\ldots,V_{k}\\}$ is a $c$-partition of a graph $G$,
and there exist two sets $V_{i}$ and $V_{j}$ whose union $V_{i}\cup V_{j}$ is
not a dominating set, then the partition $\Psi^{\prime}$ formed from $\Psi$ by
replacing $V_{i}$ and $V_{j}$ with the union $V_{i}\cup V_{j}$ is a
$c$-partition of $G$ and $\Psi$ is a proper refinement of $\Psi^{\prime}$.

A $c$-partition ${\cal A}$ is a _minimal_ $c$-_partition_ in $G$ if it is not
a proper refinement of any other $c$-partition in $G$. In [2], Haynes et al.
defined the _minmin coalition number_ $c_{\min}(G)$ of $G$ to equal the
minimum order of a minimal $c$-partition of $G$. A minimal $c$-partition of
$G$ of cardinality $c_{\min}(G)$ is called a $c_{\min}$-_partition of $G$_.
Haynes et al. [2] posed the following open problem.

###### Problem 1

([2]) What can you say about $c_{\min}(G)$?

This paper addresses Problem 1. We proceed as follows. In Section 2, we
present lower and upper bounds on the minmin coalition number and we prove
that if $G$ is a graph of order $n$, then $2\leq c_{\min}(G)\leq n$, and these
bounds are sharp. In Section 3, we characterize graphs $G$ of order $n$
satisfying $c_{\min}(G)=n$. In Section 4, we give a comprehensive description
of graphs $G$ satisfying $c_{\min}(G)=k$ where $2\leq k\leq 4$. Additionally,
we present a polynomial-time algorithm to determine if $c_{\min}(G)=2$ for a
given graph $G$. If $G$ is an isolate-free graph that does not contain a
universal vertex and has minimum degree $1$, then we show that
$c_{\min}(G)=2$. A characterization of graphs $G$ with minimum degree $2$ and
$c_{\min}(G)=4$ is provided.

##  2 Bounds on the minmin coalition number

In this section, we present lower and upper bounds on the minmin coalition
number. We prove firstly that the minmin coalition number is bounded above by
the cardinality of an arbitrary $c$-partition of $G$.

###### Proposition 1

If $G$ is a graph and ${\cal X}$ is a $c$-partition of $G$, then
$c_{\min}(G)\leq|{\cal X}|$.

Proof.  Let ${\cal X}$ be an arbitrary $c$-partition of $G$. If ${\cal X}$ is
a minimal $c$-partition of $G$, then $c_{\min}(G)\leq|{\cal X}|$. Now, assume
that ${\cal X}$ is not a minimal $c$-partition. By repeated applications of
Observation 1, there exists a minimal $c$-partition ${\cal P}$ of $G$ with
${\cal P}<{\cal X}$. Hence, $c_{\min}(G)\leq|{\cal P}|<|{\cal X}|$. $\Box$

As an immediate consequence of Proposition 1, we have the following upper
bound on the minmin coalition number.

###### Corollary 1

If $G$ is a graph, then $c_{\min}(G)\leq C(G)$.

We determine next a relationship between the minmin coalition number of a
graph and the graph obtained from it by removing the universal vertices.

###### Proposition 2

If $G$ is a graph that is not a complete graph and contains $k$ universal
vertices, then $c_{\min}(G)=c_{\min}(G^{\prime})+k$, where $G^{\prime}$ is
obtained from $G$ by removing the universal vertices.

Proof.  Let $G$ be a graph that is not a complete graph and contains $k$
universal vertices, and let ${\cal X}$ be a $c_{\min}$-partition of $G$. Thus,
${\cal X}$ is a minimal $c$-partition of $G$ and $|{\cal X}|=c_{\min}(G)$. If
$u$ is a universal vertex, then every $c$-partition of $G$ contains the set
$\\{u\\}$. In particular, $\\{u\\}\in{\cal X}$. Let ${\cal X}^{\prime}$ be
obtained from ${\cal X}$ by removing all sets $\\{u\\}$, where $u$ is a
universal vertex of $G$. The resulting partition ${\cal X}^{\prime}$ is a
$c$-partition of $G^{\prime}$. Thus by Proposition 1 we infer that
$c_{\min}(G^{\prime})\leq|{\cal X}^{\prime}|=|{\cal X}|-k=c_{\min}(G)-k$. To
prove the reverse inequality, let ${\cal Y}^{\prime}$ be a
$c_{\min}$-partition of $G^{\prime}$. Thus, ${\cal Y}^{\prime}$ is a minimal
$c$-partition of $G^{\prime}$ and $|{\cal Y}^{\prime}|=c_{\min}(G^{\prime})$.
Adding all sets $\\{u\\}$ to ${\cal Y}^{\prime}$, where $u$ is a universal
vertex of $G$, yields a partition ${\cal Y}$ that is a $c$-partition of $G$.
By Proposition 1 we infer that $c_{\min}(G)\leq|{\cal Y}|=|{\cal
Y}^{\prime}|+k=c_{\min}(G^{\prime})+k$. Consequently,
$c_{\min}(G)=c_{\min}(G^{\prime})+k$. $\Box$

We next establish lower and upper bounds on the minmin coalition number of a
graph.

###### Theorem 1

If $G$ is a graph of order $n\geq 2$, then $2\leq c_{\min}(G)\leq n$, and
these bounds are sharp.

Proof.  Let $G$ be a graph of order $n\geq 2$. By Corollary 1,
$c_{\min}(G)\leq C(G)$. Since $C(G)\leq n$, the upper bound $c_{\min}(G)\leq
n$ trivially holds. To prove the lower bound on $c_{\min}(G)$, let ${\cal Y}$
be a $c_{\min}$-partition of $G$. If ${\cal Y}$ contains a set of cardinality
$1$, then such a set is a singleton dominating set of $G$. In this case, we
infer from the lower bound on the order of $G$ that $|{\cal Y}|\geq 2$. If
every set in ${\cal Y}$ has cardinality at least $2$, then every set in ${\cal
Y}$ forms a coalition with some other set in the $c$-partition, implying once
again that $|{\cal Y}|\geq 2$. Hence in both cases, $c_{\min}(G)=|{\cal
Y}|\geq 2$.

To prove the sharpness of lower bound, consider, for example, when $G$ is a
path $v_{1}v_{2}\ldots v_{n}$ of order $n\geq 4$. The partition ${\cal
X}=\\{\\{v_{1},v_{2}\\},\\{v_{3},\ldots,v_{n}\\}\\}$ is a $c$-partition of $G$
that is not a proper refinement of any other $c$-partition in $G$, implying
that ${\cal X}$ is a minimal $c$-partition. Therefore, $2\leq
c_{\min}(G)\leq|{\cal X}|=2$, and so $c_{\min}(G)=2$. To prove the sharpness
of upper bound, consider, for example, a complete bipartite graph $G$ with
partite sets $V_{1},V_{2},\ldots,V_{k}$ where $k\geq 2$ and $|V_{i}|=2$ for
all $i\in[k]$. Since $\gamma(G)=2$ and every subset of $V(G)$ of cardinality
$2$ is a dominating set of $G$, we infer that every $c$-partition of $G$
contains only singleton sets. Hence, $c_{\min}(G)=n$. $\Box$

##  3 Graphs with large minmin coalition number

In this section, we characterize graphs $G$ of order $n$ satisfying
$c_{\min}(G)=n$. For this purpose, we define a family ${\cal M}$ of graphs $G$
that are generated in the following recursive manner. We begin by including
the graphs $K_{1}$, $K_{2}$, and $\overline{K}_{2}$ in ${\cal M}$. If $H$ is a
graph already present in ${\cal M}$, then we add the two graphs $K_{1}+H$ and
$\overline{K}_{2}+H$ to ${\cal M}$, where the join $F+G$ of two graphs $F$ and
$G$ is the graph formed from disjoint copies of $F$ and $H$ by joining every
vertex of $F$ to every vertex of $G$. As an illustration, the
$C_{4}=\overline{K}_{2}+\overline{K}_{2}$ belongs to the family ${\cal M}$,
and so $C_{4}\in{\cal M}$. The graph $\overline{K}_{2}+C_{4}$ illustrated on
the left hand drawing of Figure 1 (where here $H=C_{4}$) therefore belongs to
the family ${\cal M}$. Moreover the graph $K_{1}+C_{4}$ belongs to the family
${\cal M}$, implying that the graph $K_{1}+H$ illustrated in the right hand
drawing of Figure 1 (where here $H=K_{1}+C_{4}$) therefore belongs to the
family ${\cal M}$.

Figure 1: Two graphs in the family ${\cal M}$.

###### Proposition 3

If $G\in{\cal M}$ has order $n\geq 3$, then $G$ is a connected graph and
$c_{\min}(G)=n$.

Proof.  Let $G\in{\cal M}$ have order $n\geq 3$. By construction of graphs in
the family ${\cal M}$, the graph $G$ is connected. Let
$V=\\{v_{1},\ldots,v_{n}\\}$. We proceed by induction on $n\geq 3$ to show
that the property ($\star$) below holds in the graph $G$:

  1. ($\star$)

Every two distinct vertices that are not universal vertices form a dominating
set of $G$.

Suppose that $n=3$. In this case, either $G=K_{1}+K_{2}=K_{3}$ or
$G=K_{1}+\overline{K}_{2}=P_{3}$. If $G=K_{3}$, then every vertex of $G$ is a
universal vertex. If $G=P_{3}$, then $G$ has two vertices that are not
universal and these two vertices form a dominating set of $G$. Hence if $n=3$,
then property ($\star$) holds. Suppose that $n=4$. Thus, $G=K_{1}+H$ where
$H\in\\{P_{3},K_{3}\\}$ or $G=\overline{K}_{2}+H$ where
$H\in\\{K_{2},\overline{K}_{2}\\}$. Hence, $G\in\\{K_{4},K_{4}-e,C_{4}\\}$ and
property ($\star$) holds in the graph $G$. This establishes the base case when
$n=3$ and $n=4$. Suppose that $n\geq 5$ and that if $G^{\prime}\in{\cal M}$
has order $n^{\prime}$ where $3\leq n^{\prime}<n$, then property ($\star$)
holds in the graph $G^{\prime}$. Let $G\in{\cal M}$ have order $n$. Since
$G\in{\cal M}$, either $G=K_{1}+G^{\prime}$ or $G=\overline{K}_{2}+G^{\prime}$
for some graph $G^{\prime}\in{\cal M}$.

Suppose firstly that $G=K_{1}+G^{\prime}$ for some graph $G^{\prime}\in{\cal
M}$ of order $n^{\prime}$. Necessarily, $n^{\prime}=n-1$. Let $v$ be the
vertex added to $G^{\prime}$ to construct $G$, and so $v$ is a universal
vertex of $G$. Every universal vertex in $G^{\prime}$ is also a universal
vertex in $G$. Let $x$ and $y$ be two arbitrary vertices of $G$ that are not
universal vertices of $G$. Both $x$ and $y$ belong to $G^{\prime}$ and neither
$x$ nor $y$ is a universal vertices of $G^{\prime}$. Applying the inductive
hypothesis to $G^{\prime}$, the set $\\{x,y\\}$ forms a dominating set of
$G^{\prime}$, and therefore also of $G$ since both $x$ and $y$ are adjacent to
the universal vertex $v$ of $G$. Hence in this case when $G=K_{1}+G^{\prime}$
for some graph $G^{\prime}\in{\cal M}$, property ($\star$) holds in the graph
$G$.

Suppose secondly that $G=\overline{K}_{2}+G^{\prime}$ for some graph
$G^{\prime}\in{\cal M}$ of order $n^{\prime}$. Necessarily, $n^{\prime}=n-2$.
Let $v_{1}$ and $v_{2}$ be the two vertices added to $G^{\prime}$ to construct
$G$, and so $v_{i}$ is adjacent to every vertex of $G$ except for the vertex
$v_{3-i}$ for $i\in[2]$. Every universal vertex in $G^{\prime}$ is also a
universal vertex in $G$. Let $x$ and $y$ be two arbitrary vertices of $G$ that
are not universal vertices of $G$. If both $x$ and $y$ belong to $G^{\prime}$,
then neither $x$ nor $y$ is a universal vertex of $G^{\prime}$, and so by the
inductive hypothesis, the set $\\{x,y\\}$ forms a dominating set of
$G^{\prime}$, and therefore also of $G$. If exactly one of $x$ and $y$ belong
to $G^{\prime}$, then renaming vertices if necessary we may assume that
$x=v_{1}$ and $y\in V(G^{\prime})$. In this case, since $x$ dominates the set
$V(G^{\prime})$ and the vertex $y$ is adjacent to $v_{2}$, the set $\\{x,y\\}$
once again forms a dominating set of $G$. Finally, if
$\\{x,y\\}=\\{v_{1},v_{2}\\}$, then $\\{x,y\\}$ again forms a dominating set
of $G$. Hence in this case when $G=\overline{K}_{2}+G^{\prime}$ for some graph
$G^{\prime}\in{\cal M}$, property ($\star$) holds in the graph $G$.

Since property ($\star$) holds in the graph $G$, if ${\cal X}$ is an arbitrary
$c$-partition of $G$, then every set in the partition ${\cal X}$ is a
singleton set, and so $|{\cal X}|=n$, implying that $c_{\min}(G)=n$. $\Box$

We are now in a position to characterize graphs $G$ of order $n$ satisfying
$c_{\min}(G)=n$.

###### Theorem 2

If $G$ is a connected graph of order $n\geq 3$, then $c_{\min}(G)=n$ if and
only if $G\in{\cal M}$.

Proof.  Let $G$ be a connected graph of order $n\geq 3$. If $G\in{\cal M}$,
then by Proposition 3, $c_{\min}(G)=n$. Hence it suffices for us to prove that
if $c_{\min}(G)=n$, then $G\in{\cal M}$. We prove by induction on $n\geq 3$
that $G\in{\cal M}$. If $n=3$, then since $G$ is a connected graph either
$G=P_{3}$ or $G=K_{3}$. In both cases, $G\in{\cal M}$. This establishes the
base case. Suppose that $n\geq 4$ and that if $G^{\prime}$ is a connected
graph of order $n^{\prime}$ where $3\leq n^{\prime}<n$ and
$c_{\min}(G^{\prime})=n^{\prime}$, then $G^{\prime}\in{\cal M}$.

Let $G$ be a connected graph of order $n$ satisfying $c_{\min}(G)=n$, and let
$V=\\{v_{1},\ldots,v_{n}\\}$. Thus, $G$ contains a unique $c$-partition,
namely the partition in which every set is a singleton set. In particular, $G$
contains a unique $c_{\min}$-partition, namely the partition
$\Psi=\\{\\{v_{1}\\},\\{v_{2}\\},\ldots,\\{v_{n}\\}\\}$. Since the
$c_{\min}$-partition $\Psi$ is not a proper refinement of any other
$c$-partition in $G$, by Proposition 1 if $v_{i}$ and $v_{j}$ are distinct
vertices that are not universal vertices of $G$, then the set
$\\{v_{i},v_{j}\\}$ is a dominating set of $G$ for all $i,j\in[n]$. If
$G=K_{n}$, then by repeated applications of the join operation $K_{1}+H$ where
$H\in{\cal M}$, the graph $G\in{\cal M}$ noting that $K_{2}\in{\cal M}$.
Hence, we may assume that $G\neq K_{n}$, for otherwise the desired result is
immediate. In particular, $G$ contains at least two vertices that are not
universal vertices.

Let $v$ be an arbitrary vertex of $G$ that is not a universal vertex, and
consider the set $S_{v}=V\setminus N_{G}[v]$. Thus, the set $S_{v}$ consists
of all vertices of $G$ different from $v$ that are not adjacent to $v$. By
supposition, $|S_{v}|\geq 1$. Suppose that $|S_{v}|\geq 2$, and let
$\\{x,y\\}\subseteq S_{v}$. Since neither $x$ nor $y$ is adjacent to $v$, the
vertices $x$ and $y$ are not universal vertices of $G$. By our earlier
observations, the set $\\{x,y\\}$ is therefore a dominating set of $G$.
However, the vertex $v$ is not dominated by the set $\\{x,y\\}$, a
contradiction. Hence, $|S_{v}|=1$.

Let $S_{v}=\\{v^{\prime}\\}$. Let $u$ be an arbitrary neighbor of $v$, and so
$u\in N_{G}(v)$. If $u$ is a universal vertex, then $u$ is adjacent to
$v^{\prime}$. If $u$ is not a universal vertex, then by our earlier
observations, the set $\\{u,v\\}$ is therefore a dominating set of $G$. In
particular, this implies that the vertex $u$ is adjacent to $v^{\prime}$.
Hence, the vertex $v^{\prime}$ is adjacent to every vertex in $N_{G}(v)$.
Thus, $G=\overline{K}_{2}+G^{\prime}$ where $G^{\prime}=G-\\{v,v^{\prime}\\}$.
Let $G^{\prime}$ have order $n^{\prime}$, and so $n=n^{\prime}-2$. If
$G^{\prime}$ is a complete graph $K_{n-2}$, then $G^{\prime}\in{\cal M}$,
implying that $G^{\prime}\in{\cal M}$.

Hence we may assume that $G^{\prime}$ contains at least two vertices that are
not universal vertices in $G^{\prime}$. Let $x$ and $y$ be two distinct
vertices that are not universal vertices of $G^{\prime}$. Since $x$ and $y$
are not universal vertices of $G$, by our earlier observations that
$\\{x,y\\}$ is a dominating set of $G$. This in turn implies that $\\{x,y\\}$
is a dominating set of $G^{\prime}$. This is true for every two distinct
vertices that are not universal vertices of $G^{\prime}$. Hence,
$c_{\min}(G^{\prime})=n^{\prime}$. If $n^{\prime}=2$, then either
$G^{\prime}=K_{2}$, in which case $G=K_{4}-e$, or
$G^{\prime}=\overline{K}_{2}$, in which case $G=C_{4}$. In both cases,
$G\in{\cal M}$. Hence, we may assume that $n^{\prime}\geq 3$, for otherwise
the desired result follows. Thus by our earlier properties of the graph
$G^{\prime}$, we infer that $G^{\prime}$ is a connected graph. As observed
earlier, $c_{\min}(G^{\prime})=n^{\prime}$. Applying the inductive hypothesis
to $G^{\prime}$, we infer that $G^{\prime}\in{\cal M}$. This in turn implies
that $G=\overline{K}_{2}+G^{\prime}\in{\cal M}$. $\Box$

##  4 Graphs with small minmin coalition number

In this section, we study graphs with small minmin coalition number. We
characterize graphs $G$ with no universal vertex satisfying $c_{\min}(G)=2$.
We present necessary and sufficient condition for a graph $G$ to satisfy
$c_{\min}(G)\geq 3$, and necessary and sufficient condition for a graph $G$ to
satisfy $c_{\min}(G)\geq 4$. We first prove a necessary condition for a graph
$G$ to satisfy $c_{\min}(G)=2$.

###### Lemma 1

If $G$ is an isolate-free graph with $\delta(G)=1$ that does not contain a
universal vertex, then $c_{\min}(G)=2$.

Proof.  Let $G$ be an isolate-free graph with $\delta(G)=1$ that does not
contain a universal vertex. Suppose, to the contrary, that $c_{\min}(G)\neq
2$. Hence by Theorem 1, $c_{\min}(G)\geq 3$. In particular, this implies that
$G$ has order at least $3$. Let $x$ be a vertex of degree $1$ in $G$, and let
$y$ be its only neighbor. We now consider the partition $\Psi=(V_{1},V_{2})$
of $V(G)$ into sets $V_{1}=\\{x,y\\}$ and $V_{2}=V(G)\setminus V_{1}$. Since
the vertex $x$ is not dominated by $V_{2}$, the set $V_{2}$ is not a
dominating set of $G$. By supposition the graph $G$ does not contain a
universal vertex. In particular, the vertex $y$ is not a universal vertex of
$G$, implying that the set $V_{1}$ is not a dominating set of $G$. Hence, the
sets $V_{1}$ and $V_{2}$ form a coalition in $G$. Thus, $\Psi$ is a
$c$-partition of $G$, implying by Proposition 1 that
$c_{\min}(G)\leq|\Psi|=2$, a contradiction. $\Box$

As a consequence of Lemma 1, we can determine the minmin coalition number of a
tree.

###### Corollary 2

If $T$ is a nontrivial tree, then $c_{\min}(T)=2$, unless $T$ is a star
$T\cong K_{1,r}$ where $r\geq 2$.

Proof.  Let $T$ be a nontrivial tree. Thus, $T$ has order $n\geq 2$. If $n=2$,
then $c_{\min}(T)=2$. Hence we may assume that $n\geq 3$, for otherwise the
desired result is immediate. If $T$ does not contain a universal vertex, then
we immediately infer from Lemma 1 that $c_{\min}(G)=2$. Hence we may further
assume that $T$ contains a universal vertex. Thus, $T$ is a star $K_{1,n-1}$.
By our earlier assumptions, $n\geq 3$. If $\Psi$ is an arbitrary $c$-partition
of $T$, then the universal vertex, $v$ say, of $T$ form a singleton set
$\\{v\\}$ in $\Psi$. Since $n\geq 3$, no leaf of $T$ is a dominating set of
$T$. Since the set of leaves in $T$ forms a dominating set of $T$, the set of
leaves cannot be a set in the $c$-partition $\Psi$, implying that $\Psi$
contains at least two sets different from the singleton set $\\{v\\}$.
Therefore, $|\Psi|\geq 3$. Since this is true for every $c$-partition of $T$,
we infer that $c_{\min}(T)\geq 3$. On the other hand, if $(V_{1},V_{2})$ is an
arbitrary partition of the set of leaves of $T$, then the partition ${\cal
X}=(V_{1},V_{2},V_{3})$ where $V_{3}=\\{v\\}$ is a $c$-partition of $T$, and
so by Proposition 1 $c_{\min}(G)\leq|{\cal X}|=3$. Consequently,
$c_{\min}(T)=3$. $\Box$

We present next a necessary and sufficient condition for a graph $G$ to
satisfy $c_{\min}(G)\geq 3$.

###### Theorem 3

If $G$ is a graph that does not contain a universal vertex, then
$c_{\min}(G)\geq 3$ if and only if for every vertex $v\in V$, the set $N[v]$
is a dominating set of $G$.

Proof.  Let $G$ be a graph that does not contain a universal vertex. Suppose
firstly that $c_{\min}(G)\geq 3$. Let $v$ be an arbitrary vertex of $G$, and
let $S=N_{G}[v]$. Since the vertex $v$ is not adjacent to any vertex in
$V\setminus S$, the set $V\setminus S$ is not a dominating set of $G$. If $S$
is not a dominating set of $G$, then $\\{S,V\setminus S\\}$ is a coalition
partition of $G$, and so by Proposition 1 $c_{\min}(G)\leq 2$, a
contradiction. Hence, $S$ is a dominating set of $G$.

Conversely, suppose that the set $N[v]$ is a dominating set of $G$ for every
vertex $v\in V$. We show that $c_{\min}(G)\geq 3$. Suppose, to the contrary,
that $c_{\min}(G)<3$. By Theorem 1, this implies that $c_{\min}(G)=2$. Let
${\cal X}=\\{A,B\\}$ be a $c_{\min}$-partition of $G$. Since $G$ has no
universal vertex, neither set $A$ nor $B$ is a dominating set of $G$. Let $u$
be a vertex of $G$ not dominated by the set $A$, and so $A\cap
N[u]=\emptyset$. Since $B=V\setminus A$, we have $N[u]\subseteq B$. By
supposition the set $N[u]$ is a dominating set of $G$. Since the property of
being a dominating set is superhereditary, the set $B$ is therefore a
dominating set of $G$, a contradiction. Hence, $c_{\min}(G)\geq 3$, as
desired. $\Box$

As an immediate consequence of Theorem 1 and Theorem 3, we have the following
characterization of graphs with no universal vertex satisfying
$c_{\min}(G)=2$.

###### Corollary 3

If $G$ is a graph that does not contain a universal vertex, then
$c_{\min}(G)=2$ if and only if there exists a vertex $v\in V$ such that $N[v]$
is not a dominating set of $G$.

As an application of Corollary 3, consider the Heawood graph and the Petersen
graph illustrated in Figure 2(a) and (b), respectively. Since neither graph
has a vertex whose closed neighborhood is a dominating set, we infer from
Corollary 3 that the minmin coalition number is equal to $2$ for both the
Heawood graph and the Petersen graph.

(a)  (b)

Figure 2: (a): Heawood graph. (b): Petersen graph.

As a further application of Corollary 3, we can determine the minmin coalition
number of a cycle.

###### Corollary 4

The minmin coalition number of a cycle $C_{n}$ is given by following closed
formula.

$c_{\min}(C_{n})=\left\\{\begin{array}[]{cl}2&\text{\rm if~{}}n\geq 6\\\
3&\text{\rm if~{}}n=3\text{~{}\rm or~{}}n=5.\\\ 4&\text{\rm
if~{}}n=4.\end{array}\right.$

Proof.  If $n\geq 6$, then by Corollary 3 we have $c_{\min}(C_{n})=2$. For
$n\leq 5$, Theorem 3 implies that $c_{\min}(C_{n})\geq 3$. When $n=3$, the
only $c$-partition of $C_{3}$ consists of three singleton sets which implies
that $c_{\min}(C_{3})=3$. When $n=4$, we note that every subset of vertices of
$C_{4}$ with at least two vertices is a dominating set, implying that the only
$c$-partition of $C_{4}$ consists of four singleton sets, and so
$c_{\min}(C_{4})=4$. Suppose that $n=5$ and consider the $5$-cycle
$v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}$. The partition
$\\{\\{c_{1}\\},\\{c_{2},c_{3}\\},\\{c_{4},c_{5}\\}\\}$, for example, is a
minimal $c$-partition of $C_{5}$, implying that $c_{\min}(C_{5})=3$. $\Box$

We remark that Theorem 3 yields a polynomial time algorithm to determine
whether a graph $G$ with no universal vertex satisfies $c_{\min}(G)=2$ or
$c_{\min}(G)\neq 2$. We recursively examine all the vertices of $G$ one by
one. If there exists a vertex $v\in V$ such that the set $N[v]$ is not a
dominating set of $G$, then we infer by Theorem 3 that $c_{\min}(G)=2$. If no
such vertex exists, then we infer that $c_{\min}(G)\neq 2$. Given a set of
vertices of $G$, one can easily check in polynomial time whether the set is a
dominating set of $G$ or not. Therefore, the total time required to determine
whether $c_{\min}(G)=2$ is polynomial. This yields the following result.

###### Theorem 4

There exists a polynomial time algorithm to determine whether for a given
graph $G$ with no universal vertices the equation $c_{\min}(G)=2$ holds or
not.

We present next a necessary and sufficient condition for a graph $G$ to
satisfy $c_{\min}(G)\geq 4$.

###### Theorem 5

If $G$ is a graph that does not contain a universal vertex, then
$c_{\min}(G)\geq 4$ if and only if for every vertex $v\in V$ and every
partition $\\{P,Q\\}$ of $N[v]$, at least one of $P$ or $Q$ is a dominating
set of $G$.

Proof.  Let $G$ be a graph that does not contain a universal vertex. Suppose
firstly that $c_{\min}(G)\geq 4$. Let $v$ be an arbitrary vertex of $G$, and
let $\\{P,Q\\}$ be an arbitrary partition of $N[v]$. Thus, $P\neq\emptyset$,
$Q\neq\emptyset$ and $P\cup Q=N[v]$. Suppose that $P=\\{v\\}$, and so
$Q=N(v)$. By Theorem 3, $N[v]$ is a dominating set of $G$, implying that $Q$
is a dominating set, yielding the desired result. Analogously, if $Q=\\{v\\}$,
then the desired result follows. Hence we may assume that $P\neq\\{v\\}$ and
$Q\neq\\{v\\}$. Renaming the sets $P$ and $Q$ if necessary, we may assume that
$v\in P$. Let $R=V\setminus(P\cup Q)$. Since $R$ contains no neighbors of $v$,
it is not a dominating set of $G$. We now consider the partition ${\cal
X}=\\{P,Q,R\\}$ of $V$. Suppose that neither $P$ nor $Q$ is a dominating set
of $G$. Since $c_{\min}(G)\neq 2$, by Theorem 3 the set $P\cup Q$ is a
dominating set. Additionally, $P\cup R$ is a dominating set of $G$ noting that
the vertex $v$ dominates all vertices in $Q$. Therefore, $\cal X$ is a
$c$-partition of $G$, which implies that $c_{\min}(G)\leq 3$, a contradiction.
Hence, at least one of $P$ or $Q$ is a dominating set.

Conversely, suppose that for every vertex $v\in V$ and every partition
$\\{P,Q\\}$ of $N[v]$, at least one of $P$ or $Q$ is a dominating set of $G$.
We show that $c_{\min}(G)\geq 4$. Suppose, to the contrary, that
$c_{\min}(G)<4$. Hence by Theorem 1, $c_{\min}(G)$ can only be equal to $2$ or
$3$. If $c_{\min}(G)=2$, then by Corollary 3 there exists a vertex $v\in V$
such that $N[v]$ is not a dominating set of $G$. However in this case for
every possible partition $\\{P,Q\\}$ of $N[v]$, neither $P$ nor $Q$ is a
dominating set of $G$, a contradiction. Therefore, $c_{\min}(G)=3$. Let ${\cal
X}=\\{A,B,C\\}$ be a $c_{\min}$-partition of $G$. Thus, ${\cal X}$ is a
minimal $c$-partition of $G$ and $|{\cal X}|=3$. Since $G$ has no universal
vertex, we note that none of the sets $A$, $B$ and $C$ is a dominating set of
$G$. Let $u$ be a vertex of $G$ not dominated by the set $A$, and so $A\cap
N[u]=\emptyset$. Since $B\cup C=V\setminus A$, we therefore have
$N[u]\subseteq B\cup C$. Suppose that $B\cap N[u]=\emptyset$, implying that
$N[u]\subseteq C$. By Theorem 3 and our assumption that $c_{\min}(G)\neq 2$,
the set $N[u]$ is a dominating set. Since the property of being a dominating
set is superhereditary, the set $C$ is therefore a dominating set of $G$, a
contradiction. Hence, $B\cap N[u]\neq\emptyset$. Analogously, $C\cap
N[u]\neq\emptyset$. Thus letting $P=B\cap N[u]$ and $Q=C\cap N[u]$, we have
that $\\{P,Q\\}$ is a partition of $N[u]$. Hence by supposition, at least one
of $P$ or $Q$ is a dominating set of $G$. This in turn implies that at least
one of $B$ or $C$ is a dominating set of $G$, a contradiction. Hence,
$c_{\min}(G)\geq 4$. $\Box$

Let ${\cal F}$ be the family of graphs $G$ with vertex set $V=\\{v,x,y\\}\cup
U$, where $\deg(v)=2$ and $N(v)=\\{x,y\\}$, and where the vertices $x$ and $y$
are not adjacent but are both adjacent to all vertices of $U$ as illustrated
in Figure 3. Furthermore, the subgraph $G[U]$ induced by $U$ contains any
number of edges, including the possibility of no edges. As an application of
Theorem 5, we have the following result.

Figure 3: A graph in the family ${\cal F}$

###### Theorem 6

If $G$ is a graph with $\delta(G)=2$ that does not contain a universal vertex,
then $c_{\min}(G)=4$ if and only if $G\in{\cal F}$.

Proof.  Let $G$ be a graph with $\delta(G)=2$ that does not contain a
universal vertex. Let $v$ be a vertex of degree $2$ in $G$, and let
$N(v)=\\{x,y\\}$. Further, let $U=V\setminus N[v]$. Suppose firstly that
$c_{\min}(G)=4$. Let $P=\\{v,x\\}$ and $Q=\\{y\\}$. By Theorem 5, at least one
of $P$ and $Q$ is a dominating set of $G$. Since $G$ has no universal vertex,
the set $Q$ is not a dominating set of $G$, implying that $P$ is necessarily a
dominating set of $G$. This in turn implies that $x$ is adjacent to all
vertices of $U$. Since $G$ has no universal vertex, the vertex $x$ is
therefore not adjacent to the vertex $y$. Interchanging the roles of $x$ and
$y$, identical arguments show that the vertex $y$ is adjacent to all vertices
of $U$. Hence, $G\in{\cal F}$.

Conversely, suppose that $G\in{\cal F}$. We adopt the notation used in the
definition of the family ${\cal F}$, and so $V=\\{v,x,y\\}\cup U$, where
$N_{G}(v)=\\{x,y\\}$. We show firstly that $c_{\min}(G)\geq 3$. Suppose, to
the contrary, that $c_{\min}(G)=2$. Let ${\cal X}=\\{A,B\\}$ be a
$c_{\min}$-partition of $G$. Since $G$ has no universal vertex, neither set
$A$ nor $B$ is a dominating set of $G$. If $\\{x,y\\}\subseteq A$ or
$\\{x,y\\}\subseteq B$, then since $\\{x,y\\}$ is a dominating set of $G$, at
least one of $A$ or $B$ is a dominating set of $G$, a contradiction. Hence,
$|A\cap\\{x,y\\}|=1$ and $|B\cap\\{x,y\\}|=1$. Renaming the sets $A$ and $B$
if necessary, we may assume that $x\in A$ and $y\in B$, and that $|A|\geq 2$.
Let $w$ be a vertex in $A$ different from $x$. Thus either $w=v$ or $w\in U$.
In both cases, the set $A$ is a dominating set of $G$, a contradiction. Hence,
$c_{\min}(G)\geq 3$.

We show next that $c_{\min}(G)\geq 4$. Suppose, to the contrary, that
$c_{\min}(G)=3$. Let ${\cal X}=\\{A,B,C\\}$ be a $c_{\min}$-partition of $G$.
Since $G$ has no universal vertex, none of the sets $A$, $B$ or $C$ is a
dominating set of $G$. We therefore infer that the set $\\{x\\}$ forms a
singleton set in ${\cal X}$, as does the set $\\{y\\}$. Renaming the sets $A$,
$B$ and $C$ we may assume that $A=\\{x\\}$ and $B=\\{y\\}$, and so
$C=V\setminus\\{x,y\\}$. However, such a set $C$ is a dominating set of $G$, a
contradiction. Hence, $c_{\min}(G)\geq 4$. The partition
$\Psi=(\\{v\\},\\{x\\},\\{y\\},U)$ is a $c$-partition of $G$, implying by
Proposition 1 that $c_{\min}(G)\leq 4$. Consequently, $c_{\min}(G)=4$. $\Box$

##  5 Concluding remarks

In this paper we address an open problem posed by Haynes, Hedetniemi,
Hedetniemi, McRae, and Mohan [2] to study the minmin coalition number
$c_{\min}(G)$ of a graph $G$. We show that if $G$ is a graph of order $n$,
then $2\leq c_{\min}(G)\leq n$. Among other results, we characterized graphs
$G$ of order $n$ satisfying $c_{\min}(G)=n$ and we provided polynomial time
algorithm to determine if $c_{\min}(G)=2$. It would be intriguing to
investigate the open question of whether a polynomial time algorithm exists to
determine larger values of $c_{\min}(G)$.

## References

  * [1] D. Bakhshesh, M. A. Henning, and D. Pradhan, On the coalition number of trees. Bull. Malays. Math. Sci. Soc. 46 (2023), no. 3, Paper No. 95.
  * [2] T. W. Haynes, J. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Introduction to coalitions in graphs. AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659.
  * [3] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Upper bounds on the coalition number. Australas. J. Combin. 80 (2021), 442–453.
  * [4] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs. Commun. Comb. Optim. 8 (2023), no. 2, 423–430.
  * [5] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs of paths, cycles, and trees. To appear in Discuss. Math. Graph Theory.
  * [6] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), _Topics in Domination in Graphs_. Series: Developments in Mathematics, Vol. 64, Springer, Cham, 2020. viii + 545 pp.
  * [7] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), _Structures of Domination in Graphs_. Series: Developments in Mathematics, Vol. 66, Springer, Cham, 2021. viii + 536 pp.
  * [8] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, _Domination in Graphs: Core Concepts_ Series: Springer Monographs in Mathematics, Springer, Cham, 2023. xx + 644 pp.
  * [9] M. A. Henning and A. Yeo, _Total domination in graphs._ Series: Springer Monographs in Mathematics, Springer, Cham, New York, 2013. xiv + 178 pp.