11institutetext:  Johns Hopkins University, Baltimore, MD, 21218, USA
11email<EMAIL_ADDRESS>
# Promptable Counterfactual Diffusion Model for Unified Brain Tumor
Segmentation and Generation with MRIs

Yiqing Shen* Guannan He* Mathias Unberath(✉)

###### Abstract

Brain tumor analysis in Magnetic Resonance Imaging (MRI) is crucial for
accurate diagnosis and treatment planning. However, the task remains
challenging due to the complexity and variability of tumor appearances, as
well as the scarcity of labeled data. Traditional approaches often address
tumor segmentation and image generation separately, limiting their
effectiveness in capturing the intricate relationships between healthy and
pathological tissue structures. We introduce a novel promptable counterfactual
diffusion model as a unified solution for brain tumor segmentation and
generation in MRI. The key innovation lies in our mask-level prompting
mechanism at the sampling stage, which enables guided generation and
manipulation of specific healthy or unhealthy regions in MRI images.
Specifically, the model’s architecture allows for bidirectional inference,
which can segment tumors in existing images and generate realistic tumor
structures in healthy brain scans. Furthermore, we present a two-step approach
for tumor generation and position transfer, showcasing the model’s versatility
in synthesizing realistic tumor structures. Experiments on the BRATS2021
dataset demonstrate that our method outperforms traditional counterfactual
diffusion approaches[17], achieving a mean IoU of 0.653 and mean Dice score of
0.785 for tumor segmentation, outperforming the 0.344 and 0.475 of
conventional counterfactual diffusion model. Our work contributes to improving
brain tumor detection and segmentation accuracy, with potential implications
for data augmentation and clinical decision support in neuro-oncology. The
code is available at https://github.com/arcadelab/counterfactual_diffusion.

###### Keywords:

Counterfactual Diffusion Model Deep Learning MRI Tumor Segmentation.

* Equal contributions.

##  1 Introduction

Brain tumor analysis in Magnetic Resonance Imaging (MRI) is an important task
in medical diagnosis and treatment planning[4]. The accurate segmentation and
characterization of tumors from MRI scans are essential for effective patient
care in neuro-oncology[8]. However, this task remains challenging due to the
complexity and variability of tumor appearances across different MRI
modalities and the need for precise delineation of tumor boundaries. Recent
advancements in deep learning, particularly in the fields of computer vision
and medical image analysis, have shown promising results in addressing these
challenges by training an end-to-end model like UNet[5]. Diffusion models,
which have demonstrated remarkable capabilities in image generation tasks,
offer a new perspective on medical image analysis by unifying discriminative
and generative tasks [7].

Despite these advancements, several key challenges persist in brain tumor
analysis. High-quality, annotated MRI datasets for brain tumors are scarce,
hindering the development of robust segmentation models. The diverse
appearance of brain tumors across patients and MRI modalities makes it
difficult for traditional segmentation models to generalize effectively. Many
existing deep learning models operate as “black boxes”, making it challenging
for clinicians to understand and trust their decisions. Furthermore, current
approaches often struggle to generate realistic tumor images or manipulate
tumor characteristics in a controlled manner. To address these challenges, we
innovatively propose a unified approach that combines the strengths of
diffusion models, counterfactual reasoning, and prompt-guided generation. This
combination offers several advantages. Counterfactual reasoning allows the
model to learn the relationship between healthy and pathological tissue,
potentially improving segmentation accuracy and generalization. Prompt-guided
generation enables more controlled and interpretable tumor analysis, allowing
clinicians to interact with the model and explore various scenarios. The
unified framework for both segmentation and generation can leverage the
synergies between these tasks, potentially improving performance on both
fronts. For segmentation, our approach aims to accurately identify and
delineate tumor regions across multiple MRI modalities (T1, T1-ce, T2, and
FLAIR). In terms of tumor generation, we focus on creating synthetic tumor
images and achieving tumor position transfer, which has implications for data
augmentation and hypothetical disease progression modeling.

The key contributions of our work are three-fold. Firstly, we present a
promptable counterfactual diffusion sampling method that outperforms
traditional approaches in both tumor segmentation and generation tasks by
enabling manual intervention in the diffusion denoising process. Secondly, we
provide a comprehensive comparison of Transformer-based and UNet-based
denoising architectures in the context of the counterfactual diffusion model.
We show that Transformer can capture global context more effectively than
traditional convolutional approaches, leading to improved performance in
handling complex tumor morphologies. We also introduce a two-step tumor
generation approach, demonstrating the versatility of our method in
manipulating and synthesizing realistic tumor structures.

Figure 1: The overall pipeline of the promptable counterfactual diffusion
sampling scheme. (A) UNet-based approach: A $128\times 128$ input image is
combined with a binary mask prompt for guided generation through a UNet-based
denoising network, iterated N times. (B) Transformer-based approach: The input
image is replicated, encoded, and processed at multiple resolutions
($128\times 128\times 3$, $16\times 16\times 4$) before undergoing guided
generation through a Transformer-based denoising network, also iterated N
times. Both approaches leverage mask-guided diffusion for region-specific
generation. The final output undergoes post-processing, including thresholding
and weighted sum computation, to produce the segmented tumor region.

##  2 Methods

In this section, we detail the architecture of our promptable counterfactual
diffusion model. We further enhance the diffusion process for the
counterfactual diffusion model [17] by replacing the conventional U-Net
denoising network [6] backbone with a Transformer-based denoising network [13]
to show its improvement is also applicable beyond DDPM. The overall framework
is summarized in Fig. 1.

###  2.0.1 Promptable Counterfactual Diffusion Sampling

Our proposed promptable counterfactual diffusion sampling scheme builds upon
the DDPM [6]. It enables both prompt-guided tumor segmentation [1] and
generation within a unified diffusion model by formulating them uniformly as a
counterfactual diffusion process. Inspired by previous work [10], our
promptable counterfactual diffusion sampling scheme extends this approach to
allow for the generation of specific areas in MRI images as either healthy or
unhealthy, based on a given mask prompt. During the reverse diffusion process,
we incorporate mask prompts to guide the generation of desired regions,
ensuring semantic consistency with the rest of the MR image. By integrating
this prompting mechanism with DDPM’s iterative denoising process, we can
produce high-quality, diverse counterfactual outputs for both healthy and
tumor regions. This flexibility enables the use of a single model for both
segmentation and augmentation in MRI analysis, streamlining the workflow and
potentially improving overall performance. The complete process of our
promptable counterfactual diffusion sampling scheme is detailed in Alg. 1 and
illustrated.

Algorithm 1 Promptable Counterfactual Diffusion Sampling Scheme

1:Clean image $x_{0}$, number of timesteps $T$, mask prompt $m$, guidance
signal $c$, neural network $\epsilon_{\theta}$

2:Generated counterfactual image $x_{0}^{\mathrm{gen}}$

3:Initialize $x_{T}\sim\mathcal{N}(0,\mathbf{I})$

4:for $t=T$ to $1$ do

5: Sample Known Regions:

6: $x_{t-1}^{\mathrm{known}}\sim q(x_{t-1}|x_{t},x_{0})$ where

7:
$q(x_{t-1}|x_{t},x_{0})=\mathcal{N}(\tilde{\mu}_{t}(x_{t},x_{0}),\tilde{\beta}_{t}\mathbf{I})$

8:
$\tilde{\mu}_{t}(x_{t},x_{0})=\frac{\sqrt{\bar{\alpha}_{t-1}}\beta_{t}}{1-\bar{\alpha}_{t}}x_{0}+\frac{\sqrt{\alpha_{t}}(1-\bar{\alpha}_{t-1})}{1-\bar{\alpha}_{t}}x_{t}$

9: Guided Sampling for Unknown Regions:

10: Predict noise: $\hat{\epsilon}=\epsilon_{\theta}(x_{t},t)$

11: Compute denoised estimate:
$x_{0}^{t}=\frac{x_{t}-\sqrt{1-\bar{\alpha}_{t}}\hat{\epsilon}}{\sqrt{\bar{\alpha}_{t}}}$

12: Apply guidance: $x_{0}^{t}\leftarrow
x_{0}^{t}+c\cdot\nabla_{x_{0}^{t}}\log p(x_{0}^{t})$

13:
$x_{t-1}^{\mathrm{guided}}\sim\mathcal{N}(\mu_{\theta}(x_{t},t,x_{0}^{t}),\Sigma_{\theta}(x_{t},t))$

14: Combine Samples:

15: $x_{t-1}=m\odot x_{t-1}^{\mathrm{known}}+(1-m)\odot
x_{t-1}^{\mathrm{guided}}$

16:end for

17:Output: $x_{0}^{\mathrm{gen}}\leftarrow x_{0}$

###  2.0.2 Transformer-based Denoising Network

We further adopt the Diffusion Transformer (DiT) [13] for the promptable
counterfactual diffusion sampling scheme in brain tumor segmentation and
generation from MRI. Specifically, our approach replaces the traditional U-Net
denoising network [16] with a Transformer-based backbone, leveraging the
superior global context capture capabilities of Transformers [18] to enhance
the diffusion model’s performance in generating high-quality MRI images.
Building on the foundational concepts of DiT, we introduce several key
enhancements tailored to MRI. Firstly, we integrate a prompting mechanism for
guided tumor segmentation and generation, enabling the creation of specific
healthy or unhealthy regions in MRI images based on mask inputs and user-
defined prompts. This exploits the Transformers’ global context awareness to
achieve more precise and contextually relevant image generation. Second, the
preprocessing of input MRI data involves utilizing a pre-trained variational
autoencoder (VAE) [9] from Stable Diffusion [15] to encode input images into a
latent space. These latent representations are then transformed into token
sequences through patchification. Our processing pipeline processes these
token sequences through multiple DiT blocks. Each DiT block incorporates in-
context conditioning, cross-attention, and adaptive layer normalization
(adaLN), similar to adaptive normalization layers in GANs [14]. These
components collectively improve the denoising network’s ability to manage
conditioning information, enhancing both performance and scalability. Finally,
in this work, we implement the DiT B-2 architecture size, as a balance between
computational efficiency and model performance. Finally, to address the RGB
input requirement of the pre-trained VAE, we process each MRI modality
separately by replicating it across three channels, creating an RGB-like
input.

###  2.0.3 Initial Segmentation Derivation

The initial segmentation is obtained by comparing the original MRI image
(factual) with the generated healthy version (counterfactual) produced by our
model. Specifically, we compute the difference image between these two:

$D(x,y)=|I_{f}(x,y)-I_{c}(x,y)|,$ (1)

where $I_{f}(x,y)$ is the intensity of the factual image at location $(x,y)$,
and $I_{c}(x,y)$ is the intensity of the counterfactual image at the same
location. This difference image $D(x,y)$ highlights areas where the model has
made changes, potentially indicating tumor regions. The resulting difference
image serves as our preliminary segmentation. However, this raw output may
contain noise or ambiguities, necessitating further refinement through post-
processing.

###  2.0.4 Post-Processing Refinement for Segmentation

After obtaining preliminary tumor segmentation results using the proposed
promptable counterfactual diffusion sampling scheme, we apply a series of
post-processing techniques to refine these results, ensuring higher accuracy
and robustness. Our post-processing pipeline consists of three main steps:
contrast and brightness adjustment, thresholding, and channel-weighted sum
computation.

First, we enhance the initial segmentation output, which represents the
difference image between the ground truth and the generated healthy image, by
adjusting its contrast and brightness. This step amplifies the contrast and
highlights tumor regions more clearly, facilitating easier distinction. Next,
we convert the contrast-adjusted image into a binary image using Otsu’s
thresholding method [12] from the skimage.filters module. It determines the
optimal threshold value to effectively separate tumor regions from the
background. Finally, we process each of the four channels corresponding to the
four MRI modalities separately. We assign an equal weight of 0.25 to each
modality’s result and integrate them by summing the weighted outputs. A voxel
is classified as having a tumor if the cumulative weight is 0.5 or more,
ensuring that tumor presence is determined based on majority overlap across
channels. This process is formalized as

$S(x,y)=\sum_{i=1}^{4}w_{i}\cdot M_{i}(x,y)$ (2)

where $w_{i}=0.25$ for each modality $i$, and $M_{i}(x,y)$ represents the
binary mask for modality $i$ at location $(x,y)$. A tumor is identified at
location $(x,y)$ if $S(x,y)\geq 0.5$. It ensures that a location is classified
as a tumor if half or more of the modalities indicate the presence of a tumor.

##  3 Results

###  3.0.1 Datasets

Our model training and experiments utilized the BRATS2021 (Brain Tumor
Segmentation Challenge 2021) dataset [2, 11, 3], a well-established MRI
benchmark for brain tumor segmentation tasks. This dataset comprises
multimodal MRI scans from patients, featuring four MRI sequences per patient:
T1-weighted (T1), post-contrast T1-weighted (T1ce), T2-weighted (T2), and
Fluid Attenuated Inversion Recovery (FLAIR).

###  3.0.2 Implementation Details

We employed data from 1,000 patients for training, with each patient
contributing 155 2D slices per modality, where we randomly split 104 slices as
the test set. All implementations are made on the 2D slice level. For each
slice, we concatenated the four modalities along the channel dimension into a
single file. These images were then resized to $128\times 128$ pixels and
normalized. In our training process, we classified axial slices containing at
least one tumor pixel as “unhealthy,” while those without any tumor pixels
were considered “healthy”. These two categories of data were used to train the
conditional diffusion model. We conducted the training process on a single
NVIDIA RTX A6000 48 GB GPU, optimizing our model with a learning rate of 1e-4,
the AdamW optimizer, a batch size of 128, and training for 15,000 steps. We
assessed the performance of tumor segmentation using two primary metrics: (i)
the Dice coefficient and (ii) Intersection over Union (IoU). To evaluate our
promptable counterfactual diffusion sampling method, we compared it with the
traditional counterfactual sampling method[17]. We assessed four methods in
total: (i) Promptable counterfactual diffusion sampling with a Transformer
denoising network (our proposal), (ii) Promptable counterfactual diffusion
sampling with a UNet denoising network (our proposed method, but as ablation),
(iii) Counterfactual sampling with a Transformer denoising network (i.e.,
without mask prompt, baseline), and (iv) Counterfactual sampling with a UNet
denoising network (i.e., without mask prompt, baseline).

Table 1: Comparison of brain tumor segmentation performance on the BRATS2021 dataset. We compare against promptable vs. traditional counterfactual diffusion model[17] with Transformer and UNet as denoising networks. Method | Mean IoU | Mean Dice
---|---|---
Promptable Counterfactual w/ Transformer | 0.653 | 0.785
Promptable Counterfactual w/ UNet | 0.647 | 0.772
Counterfactual Diffusion w/ Transformer | 0.366 | 0.479
Counterfactual Diffusion w/ UNet | 0.344 | 0.475
Figure 2: Comparative visualization of brain tumor segmentation results across
four MRI modalities (T1, T1-ce, T2, and Flair). The columns show: Input
(original MRI), GT (ground truth), UNet (our PCF+UNet), Ours (our
PCF+Transformer), UNet+CF (Counterfactual Diffusion with UNet), and DiT+CF
(Counterfactual Diffusion with Transformer). Red boxes highlight areas where
methods struggled to accurately segment or remove tumors. Our PCF+Transformer
method (Ours) demonstrates superior tumor removal across all modalities.

###  3.0.3 Evaluation of Tumor Segmentation

Our assessment encompassed four distinct methods: Promptable Counterfactual
with Transformer (PCF+Transformer), Promptable Counterfactual with UNet
(PCF+UNet), Counterfactual Diffusion Sampling with Transformer
(CF+Transformer), and Counterfactual Diffusion Sampling with UNet (CF+UNet)
[17]. The quantitative results of this evaluation are presented in Table 1.
Our proposed method (i.e., PCF+Transformer) demonstrated superior performance,
achieving the highest Mean IoU of 0.653 and Mean Dice score of 0.785. This
outstanding performance underscores the effectiveness of our approach in
accurate tumor segmentation. Notably, both promptable counterfactual methods
(PCF+Transformer and PCF+UNet) consistently outperformed their traditional
counterfactual diffusion[17] counterparts, highlighting the significant
advantages of guided generation in medical imaging tasks. The visual examples
of our segmentation results, as illustrated in Fig. 2, provide further insight
into the performance of each method. PCF+Transformer exhibited the most
impressive results, effectively identifying and delineating tumor regions
across all MRI modalities. While PCF+UNet also showed strong performance, it
occasionally fell short of completely delineating tumor boundaries. In
contrast, the CF methods demonstrated inconsistent performance across
different MRI modalities, with some instances of incomplete tumor
identification or false positives. These results collectively emphasize the
superiority of our promptable counterfactual approach, particularly when
coupled with a Transformer denoising network.

Figure 3: Visualization of the tumor regeneration process: (a) Original
unhealthy slice, (b) Mask for removing the tumor, (c) Healthy slice after
tumor removal, (d) Random mask for tumor generation (e) Regenerated tumor in a
new location.

###  3.0.4 Evaluation of Tumor Generation

We developed a two-step approach to generate tumor images and achieve tumor
position transfer, leveraging the capabilities of our promptable
counterfactual model. The first step is tumor removal, where we utilize our
promptable counterfactual model to transform unhealthy slices containing
tumors into healthy slices. This process involved the precise erasure of tumor
regions while preserving the integrity of surrounding brain tissues. It
demonstrates the model’s ability to comprehend and manipulate complex
anatomical structures within MRI images. The second step is tumor
regeneration, which employs randomly generated masks to guide the regeneration
of tumors within the previously “healed” slices. By placing these masks, we
were able to generate new tumor regions in different locations, effectively
achieving tumor position transfer. This capability showcases the model’s
flexibility in synthesizing realistic tumor structures while maintaining
anatomical plausibility. The results of this two-step process are visually
demonstrated in Fig. 3. This figure illustrates the progression from original
tumor-containing images, through the tumor removal phase, to the final images
with regenerated tumors in new positions. This approach not only demonstrates
the versatility of our promptable counterfactual model but also opens up new
possibilities for data augmentation. By generating diverse tumor
presentations, we can potentially provide valuable training data for medical
professionals.

##  4 Conclusion

In this paper, we introduced a promptable counterfactual diffusion sampling
method, which demonstrates the unification of tumor segmentation and
generation tasks. Our experiments revealed important distinctions between the
UNet and DiT denoising network backbones. The UNet-based model, while
effective in many scenarios, occasionally generated black regions when
presented with large masks or those extending beyond the brain shape in the
MRI. In contrast, the DiT backbone, operating in the latent space,
demonstrated superior robustness and stability in handling these complex
cases. Despite the lower resolution resulting from latent space processing,
the DiT backbone excelled in managing intricate masks more effectively than
its UNet counterpart. Our approach can remove the tumor while maintaining the
integrity of the original image structure, representing a significant
improvement in the field. Future work could explore its application to other
medical imaging domains and investigate its potential in clinical decision
support systems.

## References

  * [1] Amit, T., Shaharbany, T., Nachmani, E., Wolf, L.: Segdiff: Image segmentation with diffusion probabilistic models. arXiv preprint arXiv:2112.00390 (2021)
  * [2] Baid, U., Ghodasara, S., Mohan, S., Bilello, M., Calabrese, E., Colak, E., Farahani, K., Kalpathy-Cramer, J., Kitamura, F.C., Pati, S., et al.: The rsna-asnr-miccai brats 2021 benchmark on brain tumor segmentation and radiogenomic classification. arXiv preprint arXiv:2107.02314 (2021)
  * [3] Bakas, S., Akbari, H., Sotiras, A., Bilello, M., Rozycki, M., Kirby, J.S., Freymann, J.B., Farahani, K., Davatzikos, C.: Advancing the cancer genome atlas glioma mri collections with expert segmentation labels and radiomic features. Scientific data 4(1), 1–13 (2017)
  * [4] Cè, M., Irmici, G., Foschini, C., Danesini, G.M., Falsitta, L.V., Serio, M.L., Fontana, A., Martinenghi, C., Oliva, G., Cellina, M.: Artificial intelligence in brain tumor imaging: a step toward personalized medicine. Current Oncology 30(3), 2673–2701 (2023)
  * [5] Conze, P.H., Andrade-Miranda, G., Singh, V.K., Jaouen, V., Visvikis, D.: Current and emerging trends in medical image segmentation with deep learning. IEEE Transactions on Radiation and Plasma Medical Sciences 7(6), 545–569 (2023)
  * [6] Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. Advances in neural information processing systems 33, 6840–6851 (2020)
  * [7] Kazerouni, A., Aghdam, E.K., Heidari, M., Azad, R., Fayyaz, M., Hacihaliloglu, I., Merhof, D.: Diffusion models in medical imaging: A comprehensive survey. Medical Image Analysis 88, 102846 (2023)
  * [8] Khalighi, S., Reddy, K., Midya, A., Pandav, K.B., Madabhushi, A., Abedalthagafi, M.: Artificial intelligence in neuro-oncology: advances and challenges in brain tumor diagnosis, prognosis, and precision treatment. NPJ Precision Oncology 8(1), 80 (2024)
  * [9] Kingma, D.P., Welling, M.: Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 (2013)
  * [10] Lugmayr, A., Danelljan, M., Romero, A., Yu, F., Timofte, R., Van Gool, L.: Repaint: Inpainting using denoising diffusion probabilistic models. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 11461–11471 (2022)
  * [11] Menze, B.H., Jakab, A., Bauer, S., Kalpathy-Cramer, J., et al.: The multimodal brain tumor image segmentation benchmark (brats). IEEE Transactions on Medical Imaging 34(10), 1993–2024 (2015). https://doi.org/10.1109/TMI.2014.2377694
  * [12] Otsu, N.: A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics 9(1), 62–66 (1979). https://doi.org/10.1109/TSMC.1979.4310076
  * [13] Peebles, W., Xie, S.: Scalable diffusion models with transformers. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4195–4205 (2023)
  * [14] Perez, E., Strub, F., De Vries, H., Dumoulin, V., Courville, A.: Film: Visual reasoning with a general conditioning layer. In: Proceedings of the AAAI conference on artificial intelligence. vol. 32 (2018)
  * [15] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 10684–10695 (2022)
  * [16] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18. pp. 234–241. Springer (2015)
  * [17] Sanchez, P., Kascenas, A., Liu, X., O’Neil, A.Q., Tsaftaris, S.A.: What is healthy? generative counterfactual diffusion for lesion localization. In: MICCAI Workshop on Deep Generative Models. pp. 34–44. Springer (2022)
  * [18] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)


# The $b$-Chromatic Number of Certain Graphs and Digraphs

Johan Kok  Tshwane Metropolitan Police Department
City of Tshwane, Republic of South Africa
<EMAIL_ADDRESS>Naduvath Sudev Department of Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur - 680501, India.
<EMAIL_ADDRESS>
###### Abstract

The $b$-chromatic number of a graph is the maximum number $k$ of colors that
can be used to color the vertices of $G$, such that we obtain a proper
coloring and each color $i$, with $1\leq i\leq k$, has at least one
representant $x_{i}$ adjacent to a vertex of every color $j$, $1\leq j\neq
i\leq k$. The studies on $b$-chromatic number attracted much interest since
its introduction. In this paper, we discuss the $b$-chromatic number of
certain classes of graphs and digraphs. The notion of a new general family of
graphs called the Chithra graphs of a graph $G$ are also introduced in this
study and the corresponding $b$-chromatic numbers are studied.

Keywords: $b$-Chromatic number, set-graphs, edge-set graphs, Jaco graph,
ornated graphs, Rasta graph, Chithra graph.

Mathematics Subject Classification: 05C05, 05C20, 05C38, 05C62.

##  1 Introduction

For general notation and concepts in graph and digraph theory, we refer to [1,
2, 4, 16]. Except for Jaco and Ornated graphs, all graphs mentioned in this
paper are simple, non-trivial, connected, finite and undirected graphs.

Let us denote the set of $k$ colors by
$\mathcal{C}=\\{c_{1},c_{2},c_{3},\ldots,c_{k}\\}$. Then, a proper
$k$-coloring of a graph $G$ is a function $f:V(G)\to\mathcal{C}$ such that
$f(u)\neq f(v);\forall uv\in E(G)$. The color class $V_{c_{i}}$ is the subset
of $V(G)$ that are assigned to the color $c_{i}$. The chromatic number
$\chi(G)$ is the minimum integer $k$ for which $G$ admits proper $k$-coloring.

A proper $k$-coloring $\mathcal{C}$ of a graph $G$ is called a $b$-coloring if
for every color class $\mathcal{C}_{i}$, there is a vertex with color $i$
which has at least one neighbour in every other color classes. Such a vertex
$v$ in $G$ is called a b-vertex of $G$.

The $b$-chromatic number, denoted $\varphi(G)$, of a graph $G$ had been
introduced in [5] as the largest integer $k$ for which $G$ admits a
$b$-coloring using $k$ colors. If $G$ admits a $b$-coloring, then it is called
b-colorable graph.

In other words, the $b$-chromatic number of a graph $G$ is defined (see [3])
as follows.

Let $G$ be a graph on $n$ vertices, say $v_{1},v_{2},v_{3},\ldots,v_{n}$. The
$b$-chromatic number of $G$ is defined as the maximum number $k$ of colors
that can be used to color the vertices of $G$, such that we obtain a proper
coloring and each color $i$, with $1\leq i\leq k$, has at least one
representant $x_{i}$ adjacent to a vertex of every color $j$, $1\leq j\neq
i\leq k$.

For more literature on $b$-chromatic number of graphs, we refer to [3, 5, 13,
14, 15]. Motivated from these studies, in this paper, we discuss the
$b$-chromatic number of certain types of graphs and digraphs

The following is an important and useful result provided in [13].

######  Proposition 1.1.

[13] For the the complete graph $K_{n},n\geq 1$, the path $P_{n},n\geq 2$, the
cycle $C_{n},n\geq 3$ we have

  1. (i)

$\varphi(K_{n})=n;~{}\forall~{}n\in\mathbb{N}$,

  2. (ii)

$\varphi(P_{n})=2;~{}n=2,3$ and $\varphi(P_{n})=3,n\geq 4$.

  3. (iii)

$\varphi(C_{n})=3,\forall n\neq 4$ and $\varphi(C_{4})=2$.

  4. (iv)

$\varphi(K_{m^{\prime}n})=2$.

##  2 New Directions

Recently, the families of graphs namely, Jaco graphs, linear Jaco graphs,
ornated graphs, Rasta graphs, set-graphs, edge-set graphs and edge-joint
graphs were introduced in different studies in [6, 7, 8, 10, 11, 12].

We present a slightly modified definition of the $b$-chromatic number, perhaps
slightly different from those found in the current literature will be
presented hereafter the $b$-chromatic number for these families of graphs as
follows.

Consider a proper $k$-coloring of a graph $G$ and denote the set of $k$ colors
by $\mathcal{C}=\\{c_{1},c_{2},c_{3},\ldots,c_{k}\\}$. Define the subsets
$V_{c_{i}}$, of $V(G)$ by $V_{c_{i}}=\\{v_{j}:v_{j}\mapsto c_{i},v_{j}\in
V(G),c_{i}\in\mathcal{C}\\}$, where $1\leq i\leq k$. The subset $V_{c_{i}}$ is
called a color class of $G$. Clearly, the collection of all such color classes
form a partition of $V(G)$.

The largest possible value of $k\in\mathbb{N}$ such that there exists a proper
$k$-coloring such that there exist two adjacent vertices $v_{s}\in V_{c_{i}}$
and $v_{t}\in V_{c_{j}}$, for all distinct pairs of colors $c_{i},c_{j}$, is
called the $b$-chromatic number of $G$, denoted by $\varphi(G)$. Such a
coloring of the graph $G$ is called a $b$-coloring of $G$.

###  2.1 $b$-Chromatics Number of Linear Jaco Graphs

Let $\mathbb{N}$ denotes the set of all natural numbers and $\mathbb{N}_{0}$
denotes the set of all non-negative integers. The notion of the family of
linear Jaco graphs has been introduced in [11] as given below.

######  Definition 2.1.

[11] Let $f(x)=mx+c;~{}x,m\in\mathbb{N}$, $c\in\mathbb{N}_{0}$. The family of
infinite linear Jaco graphs, denoted by $\\{J_{\infty}(f(x))$, is defined as a
directed graph such that

  1. (i)

$V(J_{\infty}(f(x)))=\\{v_{i}:i\in\mathbb{N}\\}$,

  2. (ii)

$A(J_{\infty}(f(x)))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\\}$,

  3. (iii)

$(v_{i},v_{j})\in A(J_{\infty}(f(x)))$ if and only if
$(f(i)+i)-d^{-}(v_{i})\geq j$.

The function $f(x)$, we mention in this section is a linear function of the
form $f(x)=mx+c;~{}x,m\in\mathbb{N},c\in\mathbb{N}_{0}$. Then, a finite linear
Jaco graph can be defined as follows.

######  Definition 2.2.

[11] The family of finite linear Jaco graphs, denoted by $\\{J_{n}(f(x))$, is
defined by $V(J_{n}(f(x))=\\{v_{i}:i\in\mathbb{N},i\leq n\\}$,
$A(J_{n}(f(x)))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\leq n\\}$ and
$(v_{i},v_{j})\in A(J_{n}(f(x)))$ if and only if $(f(i)+i)-d^{-}(v_{i})\geq
j$.

The underlying graph of a finite linear Jaco graph is denoted by
$J^{\ast}_{n}(f(x))$, and is referred simply as the linear Jaco graph.

The vertices of a finite linear Jaco graph $J_{n}(f(x))$ with degree
$\Delta(J_{n}(f(x)))$ is called Jaconian vertices of $J_{n}(f(x))$ and the set
of vertices with maximum degree is called the Jaconian set of the linear Jaco
graph $J_{n}(f(x))$, denoted, $\mathbb{J}(J_{n}(f(x)))$ or simply
$\mathbb{J}_{n}(f(x))$ (see [11]). The lowest numbered (indexed) Jaconian
vertex is called the prime Jaconian vertex of a linear Jaco graph.

If $v_{i}$ is the prime Jaconian vertex of the finite linear Jaco graph
$J_{n}(f(x))$, the complete subgraph induced by the vertex subset
$\\{v_{i+1},v_{i+2},\ldots,v_{n}\\}$ is called the Hope subgraph of
$J_{n}(f(x))$, denoted by $\mathbb{H}(J_{n}(f(x)))$ or $\mathbb{H}_{n}(f(x))$.

Invoking the above notions, we establish the following result on the
$b$-chromatic number of a finite linear Jaco graph.

######  Theorem 2.3.

For $n\geq 2$, the $b$-chromatic number of a linear Jaco graph
$J^{\ast}_{n}(f(x))$, with prime Jaconian vertex $v_{i}$ is given by
$\varphi(J^{\ast}_{n\geq 2}(f(x)))=(n-i)+1$.

###### Proof.

If vertex $v_{1}$ is the prime Jaconian vertex of $J_{n}(f(x))$, then
$J^{\ast}_{n}(f(x))\cong K_{n}$ and the result follows from Proposition 1.1.
If vertex $v_{2}$ is the prime Jaconian vertex, then the Hope graph induced by
the set $\\{v_{3},v_{4},v_{5},\ldots v_{n}\\}$ is complete. Color these
vertices as follows. $v_{3}\mapsto c_{1},v_{4}\mapsto c_{2},v_{5}\mapsto
c_{3},\ldots v_{n}\mapsto c_{n-2}$. Also, color $v_{1}\mapsto c_{n-2}$ and
$v_{2}\mapsto c_{n-1}$. Clearly, this proper $k$-coloring with
$k=(n-2)+1=n-1$, is a maximum $k$-coloring and hence, $\varphi(J^{\ast}_{n\geq
2}(f(x)))=(n-i)+1$.

Now, assume the result holds for the prime Jaconian vertex $v_{i}$, $3\leq
i\leq k$ for the corresponding Jaco graph $J^{\ast}_{m}(f(x))$. Now, consider
the Jaco graph $J^{\ast}_{m+1}(f(x))$. Then, we have to consider the following
cases.

Case-1: If $v_{i}$ is the prime Jaconian vertex of $J^{\ast}_{m+1}(f(x))$,
then the corresponding Hope graph is
$\mathbb{H}(J^{\ast}_{m+1}(f(x)))=K_{(m-i)+1}$. We color these vertices as
$v_{i+1}\mapsto c_{0},v_{i+2}\mapsto c_{1},v_{i+3}\mapsto c_{2},\ldots
v_{m+1}\mapsto c_{(m+1)-(i+1)}$. Let $t=(m+1)-i$. Color the vertices
$v_{i}\mapsto c_{((m+1)-i)},v_{i-1}\mapsto c_{m-i},v_{i-2}\mapsto
c_{(m-i)-1},\ldots,v_{2i-n}\mapsto c_{0}$. Repeat the coloring procedure
iteratively until $v_{1}\mapsto c_{i}$, $0\leq i\leq t$ is colored. Note that
$\lceil\frac{i}{t}\rceil$ iterations are required to color all the vertices
completely. Clearly, this is a maximal proper coloring.

Assume without loss of generality that it is possible to color $v_{1}\mapsto
c_{t+1}$. Then, if $v_{i+1}\mapsto c_{j}$, and since $v_{1}v_{i+1}\notin
E(J^{\ast}_{m+1}(f(x)))$ the coloring is not a $b$-coloring.

Case-2: If $v_{i}$ is not the prime Jaconian vertex of $J^{\ast}_{m+1}(f(x))$
then by necessity vertex $v_{i+1}$ is the prime Jaconian vertex. The Hope
graph, $\mathbb{H}(J^{\ast}_{m+1}(f(x)))=K_{(m+1)-(i+1)}=K_{m-i}$. In this
case also the result follows by proceeding as explained in Case-1
alternatively, as applicable in the assumption.

Therefore, in both cases we have $\varphi(J^{\ast}_{m+1}(f(x)))=((m+1)-i)+1$
or $(m-i)+1$. Hence, the given result follows by mathematical induction. ∎

###  2.2 $b$-Chromatics Number of Ornated Graphs

The class of ornated graphs is a family of directed non-simple finite graphs
which is defined in [10] as given below.

######  Definition 2.4.

[10] An ordered string, denoted $s_{l}$, is defined as an $l$-tuple
$(a_{j})^{l}_{j=1}$ where $a_{j}\in\mathbb{N}_{0}$, $1\leq j\leq l$ for
$j,l\in\mathbb{N}$. For brevity, we write $s_{l}=(a_{j});1\leq j\leq l$.

######  Definition 2.5.

[10] Let $n$ be a positive integer and $s_{l}=(a_{j});1\leq j\leq l$ be an
ordered string of non-negative integers. An ornated graph on $n$ vertices,
associated with an ordered string $s_{l}$ is denoted by $O_{n}(s_{l})$ and is
defined as a directed graph with vertex set
$V=V(O_{n}(s_{l}))=\\{v_{i}:i\in\mathbb{N},i\leq n\\}$ and the arc set
$A=A(O_{n}(s_{l}))\subseteq V\times V$ such that for $i,j\in\mathbb{N}$,
$(v_{i},v_{j})\in A$ if and only if $(i+a_{t})\geq j,i<j$, for odd indices $t$
and $(i-a_{s})\leq j,~{}i>j$, for even indices $s$.

The underlying graph of $O_{n}(s(l))$ is denoted $O^{\ast}_{n}(s_{l})$. For
determining $\varphi(O^{\ast}_{n}(s_{l}))$ we only have to determine
$\varphi(O^{\ast}_{n}(s^{\prime}_{l}))$ called the maximal reach subgraph with
$s^{\prime}_{l}=(a_{i});a_{i}\geq a_{j}$, $1\leq j\leq n$. In view of all
these facts, we determine the $b$-chromatic number of ornated graphs in the
following theorem.

######  Theorem 2.6.

For an Ornated graph $O_{n}(s_{l})$, $a_{j}>0$ for some $i$, and $a_{i}\geq
a_{j}$, $1\leq j\leq n$, we have

$\varphi(O^{\ast}_{n}(s_{l}))=\begin{cases}n,&\text{if $n\leq a_{i}+1$,}\\\
a_{i}+2,&\text{if $n>a_{i}+1$}.\end{cases}$

###### Proof.

First assume that $n\leq a_{i}+1$. Then, since $O_{n}(s^{\prime}_{l})$,
$s^{\prime}_{l}=(a_{i})$ is the maximum reach subgraph of $O_{n}(s_{l})$, the
graph $O^{\ast}_{n}(s^{\prime}_{l})$ is a complete graph on $n$ vertices.
Therefore, by Proposition 1.1,
$\varphi(O^{\ast}_{n}(s_{l}))=O^{\ast}_{n}(s^{\prime}_{l})=n$.

Next, assume that $n\geq a_{i}+2$. Initially, color the vertices as
$v_{1}\mapsto c_{1},v_{2}\mapsto c_{2},v_{3}\mapsto
c_{3},\ldots,v_{a_{i}+2}\mapsto c_{a_{i}+2}$. Since the edge
$v_{1}v_{a_{i}+2}\notin E(O^{\ast}_{n}(s^{\prime}_{l}))$, we must color
$v_{a_{i}+3}\mapsto c_{1}$. Then, by mathematical induction it follows that
$\varphi(O^{\ast}_{n}(s_{l}))=\varphi(O^{\ast}_{n}(s^{\prime}_{l}))=a_{i}+2$.
∎

###  2.3 $b$-Chromatics Number of Rasta Graphs

The notion of Rasta graphs had been introduced in [7], which can be
constructed as explained below.

Constructing a Rasta graph: Consider a t-term sum set
$\\{t_{1},t_{2},t_{3},...,t_{l}\\}$ with $t_{1}>t_{2}>t_{3}>...>t_{l}>1$.

  1. (S-1)

Consider $t_{1}$ vertices in the left column (the first column) and $t_{2}$
vertices in the Right column (the second column) and construct
$K_{t_{1},t_{2}}$.

  2. (S-2)

Add the third column of $t_{3}$ vertices and add the edges of
$K_{t_{2},t_{3}}$.

  3. (S-3)

Repeat Step 2 iteratively up to $t_{\ell}$.

  4. (S-4)

Exit.

It is noted in [7]that a Rasta graph is the underlying graph of a directed
graph defined as follows.

######  Definition 2.7.

[7] For a $l$-term sum set $\\{t_{1},t_{2},t_{3},\ldots,t_{l}\\}$ with
$t_{1}>t_{2}>t_{3}>\ldots>t_{l}>1$, we can define the directed graph $G^{(l)}$
with vertices $V(G^{(l)})=\\{v_{i,j}:1\leq j\leq t_{i},1\leq i\leq l\\}$ and
the arcs, $A(G^{(l)})=\\{(v_{i,j},v_{(i+1),m}):1\leq i\leq(l-1),1\leq j\leq
t_{i}$ and $1\leq m\leq t_{(i+1)}\\}$.

######  Theorem 2.8.

For a Rasta graph $R$ corresponding to the underlying graph of $G^{(\ell)}$ we
have $\varphi(R)=2$.

###### Proof.

We know that $\varphi(K_{n,m})=2$ (see [13]). For the complete bi-partite
graph $K_{t_{1},t_{2}}$ color the vertices in the left column, $c_{1}$ and
those in the right column, $c_{2}$. From the construction of a Rasta graph
mentioned above, we can observe that no vertex in the first column (that is,
in the leftmost column) is adjacent to any vertex in the third column and
hence the vertices in the third column can be be colored $c_{1}$. Similarly,
the vertices in the second column and those in the fourth column are not
adjacent and hence the vertices in the fourth column can be colored using the
color $c_{2}$. Proceeding like this, the vertices at the odd position columns
have the color $c_{1}$ and the vertices at the even position columns have the
color $c_{2}$. Therefore, we have $\varphi(R)=2$. ∎

###  2.4 Chithra Graphs of a Graph

In this section, we introduce a new family of graphs, namely Chithra
graphs111The first author wishes to dedicate these graphs to a research
colleague, Mrs. Chithra Sudev., of a given graph G as follows.

Consider the set $\mathcal{V}(G)$ of all subsets of the vertex set, $V(G)$.
Select any number, say $k$, non-empty subsets $W_{i}\in\mathcal{V}(G)$,
$\bigcup^{k}_{i=1}W_{i}=V(G)$, with repetition of selection allowed. For the
additional vertices $u_{1},u_{2},u_{3},\ldots,u_{k}$, add the additional edges
$u_{i}v_{j}$, $\forall v_{j}\in W_{j}$. This new graph is called a Chithra
graph of the given graph $G$ and the family of Chithra graphs of the graph $G$
is denoted by $\mathfrak{C}(G)$.

Note that in general the empty subset of $V(G)$ may be selected as repetition
of selection is permitted. However, the empty subset does not represent an
additional vertex. This argument implies that $G\in\mathfrak{C}(G)$ as well.

Also, note that the Chithra graphs can be constructed from non-connected
(disjoint) graphs and for edgeless (null) graphs. It means that for the
edgeless graph on $n$ vertices denoted $\mathcal{N}_{n}$, the complete bi-
partite graph, $K_{n,m}\in\mathfrak{C}(\mathcal{N}_{n})$. Equally so,
$K_{n,m}\in\mathfrak{C}(\mathcal{N}_{m})$. Constructing paths from an edgeless
graph are excluded.

A number of well-known classes of graphs are indeed Chithra graphs of some
graph $G$. Small graphs such as sun graphs, sunlet graphs, crown graphs and
helm graphs are all Chithra graphs of some graph $G$.

The $b$-chromatic number of the Chithra graphs of the given graphs is
determined in the following theorem.

######  Theorem 2.9.

Let $G$ be a graph and $G^{\prime}\in\mathfrak{C}(G)$ and $G^{\prime}\neq
P_{n},n\geq 4$. Then $\varphi(G^{\prime})=\varphi(G)+1$.

###### Proof.

Clearly, if the color $c_{\varphi+1}$ is allocated to each additional vertex
$u_{i}$, $1\leq i\leq k$, the coloring $\mathcal{C}\cup\\{c_{\varphi+1}\\}$ is
a proper coloring of $G^{\prime}$. Since the edges $u_{i}u_{j}\notin
E(G^{\prime})$, for all $i,j$, no vertex $u_{i}$ can be colored other than
with $c_{\varphi+1}$. Hence, $\mathcal{C}\cup\\{c_{\varphi+1}\\}$ is a
$b$-coloring of $G^{\prime}$. Therefore, $\varphi(G^{\prime})=\varphi(G)+1$. ∎

Some trivial applications of Theorem 2.9 are the following.

  1. (i)

Since $\varphi(K_{1})=1$, and $P_{3}\in\mathfrak{C}(K_{1})$, it follows that
$\varphi(P_{3})=2$.

  2. (ii)

Since $\varphi(C_{n})=3$, $n\geq 5$, and the sunlet graph
$S_{n}\in\mathfrak{C}(C_{n})$, it follows that $\varphi(S_{n})=4$ (see [15]).

  3. (iii)

Since $\varphi(C_{n})=3,~{}n\geq 5$, and the wheel graph
$W_{n+1}\in\mathfrak{C}(C_{n})$, it follows that $\varphi(W_{n+1})=4$.

  4. (iv)

A sun graph $S_{2n}$ (see [17]) has $V(S_{2n})=\\{d_{i}:1\leq i\leq 2n\\}$ and
$E(S_{2n})=E(K_{n})\bigcup\\{d_{i}d_{i+n}:1\leq i\leq
n\\}\bigcup\\{d_{i+n}d_{(i+1)+n}:1\leq i\leq n-1\\}\bigcup\\{d_{2n}d_{1}\\}$.
Now, since a sun graph $S_{2n}\in\mathfrak{C}(K_{n})$, it follows that
$\varphi(S_{2n})=n+1$.

  5. (v)

Since a helm graph $H_{2n+1}$ is obtained from a wheel $W_{n+1}$ by attaching
one pendant vertex to each vertex of the outer cycle $C_{n}$, it follows that
$H_{2n+1}\in\mathfrak{C}(W_{n+1})$. Therefore, $\varphi(H_{2n+1})=5$.

Consider a graph $G$ on $n$ vertices. If the maximum number of mutually non-
adjacent vertices in $G$ is $k$, label them $u_{1},u_{2},u_{3},\ldots,u_{k}$.
We recall that the open neighbourhood of a vertex $v\in V(G)$ is denoted by
$N_{G}(v)$.

In view of the above notions and fats, we have the following result.

######  Lemma 2.10.

If for a graph $G$ on $n$ vertices with a maximum of $k$ mutually non-adjacent
vertices, $U=\\{u_{1},u_{2},u_{3},\ldots,u_{k}\\}$ we have
$\bigcup^{k}_{i=1}N_{G}(u_{i})=V(G)$, then $G\in\mathfrak{C}(G-U)$.

###### Proof.

Since $G$ is connected, $N_{G}(u_{i})\neq\emptyset$, $\forall u_{i}$. Also,
each $N_{G}(u_{i})\subseteq V(G)$ and $\bigcup^{k}_{i=1}N_{G}(u_{i})=V(G)$.
Hence, from the construction of a Chithra graph of $G$, it is evident that
$G\in\mathfrak{C}(G-U)$. ∎

In other words it can be said that if $\sum\limits^{k}_{i=1}d_{G}(u_{i})\geq
n-k$ then $G\in\mathfrak{C}(G-U)$.

###  2.5 $b$-Chromatics Number of Set-Graphs

The notion of a set-graph was introduced in [8] as explained below.

######  Definition 2.11.

[8] Let $A^{(n)}=\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\}$, $n\in\mathbb{N}$ be a
non-empty set and the $i$-th $s$-element subset of $A^{(n)}$ be denoted by
$A^{(n)}_{s,i}$. Now, consider
$\mathcal{S}=\\{A^{(n)}_{s,i}:A^{(n)}_{s,i}\subseteq
A^{(n)},A^{(n)}_{s,i}\neq\emptyset\\}$. The set-graph corresponding to set
$A^{(n)}$, denoted $G_{A^{(n)}}$, is defined to be the graph with
$V(G_{A^{(n)}})=\\{v_{s,i}:A^{(n)}_{s,i}\in\mathcal{S}\\}$ and
$E(G_{A^{(n)}})=\\{v_{s,i}v_{t,j}:A^{(n)}_{s,i}\cap
A^{(n)}_{t,j}\neq\emptyset\\}$, where $s\neq t$ or $i\neq j$.

The largest complete graph in the given set-graph $G_{A^{(n)}}$, $n\geq 2$ is
$K_{2^{n-1}}$ and the number of such largest complete graphs in the given set-
graph $G_{A^{(n)}}$, $n\geq 2$ is provided in the following proposition.

######  Proposition 2.12.

[9] The set-graph $G_{A^{(n)}},n\geq 2$ has exactly $2^{n-1}$ largest complete
graphs $K_{2^{n-1}}$.

Invoking the above notion of set-graphs and Proposition 2.12, we can establish
the following result on the $b$-chromatic number of a set-graph.

######  Theorem 2.13.

A set-graph $G_{A^{(n)}}$, $n\geq 2$ has $\varphi(G_{A^{(n)}})=2^{n-1}+1$.

###### Proof.

By Proposition 2.12, we know that a largest complete subgraph of the set-graph
$G_{A^{(n)}}$, $n\geq 2$ is $K_{2^{n-1}}$. Furthermore, there exists such a
complete graph, say $K^{\ast}_{2^{n-1}}$, such that the vertices
$v_{1,i}\notin V(K^{\ast}_{2^{n-1}})$, $1\leq i\leq n$. Let the $b$-coloring
of $K^{\ast}_{2^{n-1}}$ be the set
$\mathcal{C}^{\ast}=\\{c_{1},c_{2},c_{3},\ldots,c_{2^{n-1}}\\}$.

Since the vertices in the set $U=\\{v_{1,i}:1\leq i\leq n\\}$ are mutually
non-adjacent and $\bigcup^{n}_{i=1}N_{G}(v_{1,i})=V(K^{\ast}_{2^{n-1}})$, the
subgraph $K^{\ast}_{2^{n-1}}+U$ is a Chithra graph of $K^{\ast}_{2^{n-1}}$.
Hence, $\varphi(K^{\ast}_{2^{n-1}}+U)=2^{n-1}+1$. In the remaining subset of
vertices $V^{\prime}=V(G_{A^{(n)}})-V(K^{\ast}_{2^{n-1}}+U)$ each vertex
$v_{m}\in V^{\prime}$ is adjacent to at least one other vertex
$v_{m^{\prime}}\in V^{\prime}$. The latter argument implies that new colors
cannot be added and all vertices $v_{m}\in V^{\prime}$ must be colored from
$\mathcal{C}^{\ast}$, which is always possible because
$|V^{\prime}|=(2^{n}-1)-2^{n-1}-n<\frac{1}{2}(2^{n}-1)$. Hence, we have
$\varphi(G_{A^{(n)}})=2^{n-1}+1$. ∎

Another class of graphs similar to the set-graphs is the class of edge-set
graphs which has been introduced in [12] as follows.

######  Definition 2.14.

[12] Let $G(V,E)$ be a non-empty finite graph with $|E|=\epsilon$ and
$\mathcal{E}=\mathcal{P}(E)-\\{\emptyset\\}$, where $\mathcal{P}(E)$ is the
power set of the edge set $E(G)$. For $1\leq s\leq\epsilon$, let $\mathcal{S}$
be the collection of all $s$-element subsets of $E(G)$ and $E_{s,i}$ be the
$i$-th element of $\mathcal{S}$. Then the edge-set graph corresponding to $G$,
denoted by $G_{E^{(\epsilon)}}$ or $\mathcal{G}_{G}$, is the graph with the
following properties.

  1. (i)

$|V(\mathcal{G}_{G})|=2^{\epsilon}-1$ so that there exists a one to one
correspondence between $V(\mathcal{G}_{G})$ and $\mathcal{E}$.

  2. (ii)

Two vertices, say $v_{s,i}$ and $v_{t,j}$ in $\mathcal{G}_{G}$ are adjacent if
some elements (edges of $G$) in $E_{s,i}$ is adjacent to some elements of
$E_{t,j}$ in $G$.

Clearly, the edge-set graph is dependent on both the number of edges and the
structure of $G$. It is known that $\varphi(G)\leq\Delta(G)+1$ (see [5, 13]).
In [12] it is proved that the edge-set of $G$ on $n$ vertices is a complete
graph if and only if $G$ is a star graph. Hence, it can be said that
$\varphi(\mathcal{G}_{G})\leq\varphi(K_{n})$. Because the vertices of the
edge-set graph is determined by the non-empty subsets of the number of edges
of $G$ while the adjacency structure of $\mathcal{G}_{G}$ depends on the
adjacency structure of $G$, the bound $\varphi(\mathcal{G}_{G})\leq n$ is
optimal. For all non-star graphs, this bound improves to
$\varphi(\mathcal{G}_{G})\leq n-1$.

###  2.6 Edge-joint Graphs

The notion of an edge-joint graph is simple. It is an operation between two
graphs $G$ and $H$ and requires the addition of an arbitrary edge to join the
graphs into a connected structure (see [6]).

######  Definition 2.15.

[6] The edge-joint of two graphs $G$ and $H$ is the graph obtained by adding
the single arbitrary edge $vu$, $v\in V(G)$, $u\in V(H)$, and is denoted,
$G\rightsquigarrow_{vu}H$.

Clearly, the edge-joint operation establishes minimal connectivity between two
graphs and results in the existence of at least one bridge in
$G\rightsquigarrow_{vu}H$. For parameters which are reliant on the orientation
of a graph such as determining the brush number of a graph it is seen that the
commutative property does not necessarily hold.

Certain structural properties are either enhanced or destroyed through this
operation. By edge joint operations, connectivity in the graphs is enhanced
where as the existence of Hamilton cycles is destroyed. Furthermore, if both
graphs $G$ and $H$ are without bridges, all results for a graph with bridges
can now be applied for the edge joint graph.

In view of these facts, the $b$-chromatic number of an edge joint graph is
determined in the following theorem.

######  Theorem 2.16.

Let $\varphi(G)\geq\varphi(H)$ for two graphs $G$ and $H$, which are not paths
with $2$ or $3$ vertices. Then,
$\varphi(G\rightsquigarrow_{vu}H)=\varphi(H\rightsquigarrow_{uv}G)=\varphi(G)$.

###### Proof.

Assume that the $b$-colorings of two graphs $G$ and $H$ are respectively given
by $\mathcal{C}=\\{c_{1},c_{2},c_{3},\ldots,c_{\varphi(G)}\\}$ and
$\mathcal{C}^{\prime}=\\{c^{\prime}_{1},c^{\prime}_{2},c^{\prime}_{3},\ldots,c^{\prime}_{\varphi(H)}\\}$
and $c_{i}\neq c^{\prime}_{j},\forall i,j$. Since
$|\mathcal{C}^{\prime}|\leq|\mathcal{C}|$, it is always possible to construct
a one-on-one mapping $f(c^{\prime}_{i})\mapsto c_{j}\iff
f^{-1}(c_{j})=c^{\prime}_{i}$. Denote the mapping
$F(\mathcal{C}^{\prime})\mapsto\mathcal{C}$. Obviously, the vertex $u$ cannot
be colored with a color $c^{\ast}\notin\mathcal{C}$ and
$c^{\ast}\notin\mathcal{C}^{\prime}$ else
$\mathcal{C}^{\prime}\cup\\{c^{\ast}\\}$ is a $b$-coloring of $H$ larger than
the $b$-coloring $\mathcal{C}^{\prime}$ which is a contradiction.

Since $|V(H)|\geq 2$, there exists a vertex $u^{\prime}\neq u$,
$u^{\prime},u\in V(H)$. Clearly, vertex $u^{\prime}$ cannot be colored with
$c^{\ast}\notin\mathcal{C}$, else the $b$-coloring property is destroyed.
Hence, the vertices of $H$ must be colored by the mapping
$F(\mathcal{C}^{\prime})\mapsto\mathcal{C}$. Thus,
$\varphi(G\rightsquigarrow_{vu}H)=\varphi(H\rightsquigarrow_{uv}G)=\varphi(G)$.
∎

######  Remark 2.17.

For the graphs $G=P_{n},~{}n\leq 3$ and $H=P_{m},~{}m\leq 3$, we can apply
Proposition 1.1 to find the $b$-chromatic number of the edge joint graph of
the graphs $G$ and $H$.

##  3 Conclusion

In this paper, we have discussed the $b$-chromatic number of certain classes
of graphs and digraphs.

The concept of Chithra graphs allows another interesting observation namely,
the smallest graph from which the complete graph $K_{n},~{}n\geq 2$ can be
constructed recursively is $K_{1}$. This is true because
$K_{n}\in\mathfrak{C}(K_{n}),~{}K_{n}\in\mathfrak{C}(K_{n-1}),K_{n-1}\in\mathfrak{C}(K_{n-2}),K_{n-2}\in\mathfrak{C}(K_{n-3}),\ldots,K_{2}\in\mathfrak{C}(K_{1})$.
In other words,
$\mathfrak{C}(K_{n})\subset\mathfrak{C}(K_{n-1})\subset\mathfrak{C}(K_{n-2})\subset\ldots\subset\mathfrak{C}(K_{1})$.
In this sense, $K_{1}$ is called the root Chithra graph of $K_{n}$.

For the sun graph $S_{2n}$, the root Chithra graph is $K_{1}$ as well. For the
sunlet graph $S_{n}$ the cycle $C_{n}$ is the root Chithra graph. Note that
the root Chithra graph may not be unique in general. For example, a root
Chithra graph for the complete bi-partite graph $K_{n,m}$ may be
$\mathcal{N}_{n}$ or $\mathcal{N}_{m}$.

Finally, for some graphs $G$, the root Chithra graph is $G$, itself, of which
the Jaco graph $J^{\ast}_{n}(f(x))$ serves as an example. Hence, a root
Chithra graph exists for all graphs because amongst the families of Chithra
graphs of $G$, it is true that $G\in\mathfrak{C}(G)$ as well. It remains an
open problem to determine the root Chithra graph of general classes of graphs.

With regards to edge-set graphs we have that for all non-star graphs
$\varphi(\mathcal{G}_{G})\leq n-1$. This observation leaves a wide scope for
research into the parameter $\varphi(\mathcal{G}_{G})$ for specialised classes
of graphs with well-defined adjacency structures such as paths, cycles and
more complex graphs such as complete graphs and Jaco graphs.

Some other the open problems, identified during our studies are the following.

######  Problem 3.1.

Determine the root Chithra graph of various other classes of graphs.

######  Problem 3.2.

Determine $\varphi(\mathcal{G}_{G})$ for special classes of graphs with well-
defined adjacency structures.

## References

  * [1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, 1976.
  * [2] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
  * [3] B. Effatin and H. Kheddouci, The b-chromatic number of some power graphs, Discrete Mathematics and Theoretical Computer Science, 6(2003),045-054.
  * [4] J. T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press, 2006.
  * [5] R. W. Irving and D. F. Manlove, The b-chromatic number of a graph, Discrete Applied Mathematics, 91()(1999), 127-141.
  * [6] J. Kok and N. Sudev , Certain Types of Total Irregularities of Graphs and Digraphs, pre-print, arXiv: 1406.6863v3 [math; CO].
  * [7] J. Kok, N. Sudev, C. Sudev, On the Curling Number of Certain Graphs, pre-print, arXiv:1506.00813v2, [math.CO].
  * [8] J. Kok, K.P. Chithra, N.K. Sudev, C. Susanth, A Study on Set-graph, International Journal of Computer Applications, 118(7)(2015), 1-6., DOI:10.5120/20754-3173.
  * [9] J. Kok, K.P. Chithra, N.K. Sudev, C. Susanth, A Corrigendum to the article titled: A Study on Set-graph, International Journal of Computer Applications, ??(?)(2015), 1 page., DOI: .
  * [10] J. Kok, N.K. Sudev, V. Mukungunugwa, A Study on Ornated Graphs, pre-print, arXiv:1403.7916v3, [math.CO].
  * [11] J. Kok, C. Susanth, S. J. Kalayathankal, A Study on Linear Jaco Graphs, pre-print, arXiv:1506.06538v1, [math.CO].
  * [12] J. Kok, N.K. Sudev, K.P. Chithra, A Study on Edge-Set Graphs of Certain Graphs, pre-print, arXiv:1507.02546v1 [math.GM].
  * [13] M. Kouider and M. Mahéo, Some bounds for the $b$-chromatic number of a graph, Discrete Mathematics, (256)()(2002), 267-277.
  * [14] S.K. Vaidya and R.V. Isaac, The b-chromatic number of some path related graphs, International Journal of Mathematics and Scientific Computing, 4(1)(2014), 7-12.
  * [15] J.V. Vivin and M. Vekatachalam, On $b$-chromatic number of sun let graph and wheel graph families, Journal of the Egyptian Mathematical Society, 23(2)(2015), 215-222.
  * [16] D. B. West, Introduction to Graph Theory, Pearson Education Incorporated, 2001.
  * [17] Information System on Graph Classes and their Inclusions, http://www.graphclasses.org/smallgraphs.