2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Basic Information

  • Paper ID: 2302.13667
  • Title: Determining the b-chromatic number of subdivision-vertex neighbourhood coronas
  • Authors: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • Classification: math.CO (Combinatorics)
  • Publication Date: February 27, 2023
  • Paper Link: https://arxiv.org/abs/2302.13667

Abstract

Let GG and HH be two graphs, each being a path, cycle, or star graph. This paper determines the b-chromatic number of each subdivision-vertex neighbourhood corona graph G⊡HG\boxdot H or G⊡KnG\boxdot K_n, where KnK_n is the complete graph of order nn. Corresponding results are also established for graphs Kn⊡GK_n\boxdot G with m-degree not exceeding n+2n+2. All proofs are accompanied by illustrative examples.

Research Background and Motivation

Problem Background

  1. b-chromatic number concept: Irving and Manlove introduced the concept of b-chromatic coloring of graphs in 1999, which is a special proper kk-coloring requiring that each color class contains a b-vertex (a vertex adjacent to vertices of all other colors).
  2. Computational complexity: Determining the b-chromatic number of a graph is NP-hard in general, but is polynomial-time solvable for trees.
  3. Graph product research: Extensive research has focused on the b-chromatic numbers of various graph products, such as Cartesian products, direct products, strong products, and lexicographic products.

Research Motivation

  1. Theoretical completeness: The subdivision-vertex neighbourhood (SVN) corona is an important graph construction method, but research on its b-chromatic number is relatively limited.
  2. Systematic methodology: There is a need for systematic study of the b-chromatic numbers of SVN coronas of fundamental graph classes (paths, cycles, stars, complete graphs).
  3. Practical value: The b-chromatic number has important applications in network coloring and frequency allocation problems.

Core Contributions

  1. Complete determination of b-chromatic numbers for SVN coronas of fundamental graph classes: Exact formulas for the b-chromatic numbers are provided for SVN coronas of paths PnP_n, cycles CnC_n, stars SnS_n with paths, cycles, stars, and complete graphs.
  2. Establishment of partial results for complete graph SVN coronas: The b-chromatic number of Kn⊡GK_n\boxdot G is determined for cases where the m-degree does not exceed n+2n+2.
  3. Provision of constructive proof methods: All results are proven through construction of specific optimal b-chromatic colorings, accompanied by detailed illustrative examples.
  4. Development of a systematic analytical framework: A general methodology and technical tools for analyzing the b-chromatic numbers of SVN coronas are established.

Methodology Details

Task Definition

Input: Two graphs GG and HH, where G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}Output: The b-chromatic number φ(G⊡H)\varphi(G\boxdot H) of the SVN corona graph Constraints: For the case Kn⊡GK_n\boxdot G, the requirement is m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

SVN Corona Construction

Given graphs GG and HH, the construction process of the SVN corona G⊡HG\boxdot H:

  1. Begin with the subdivision graph S(G)S(G) of graph GG (inserting a new vertex on each edge)
  2. Add ∣V(G)∣|V(G)| vertex-disjoint copies of HH
  3. Connect all vertices in the neighborhood of each original vertex uiu_i in S(G)S(G) to all vertices of the (i+1)(i+1)-th copy of HH

Key Technical Tools

1. m-degree Concept

For a graph GG of order nn, its m-degree is defined as: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| where vertices are ordered by non-increasing degree.

2. Fundamental Bounds

  • Lower bound: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (chromatic number does not exceed b-chromatic number)
  • Upper bound: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (b-chromatic number does not exceed maximum degree plus one)
  • m-degree bound: φ(G)≤m(G)\varphi(G) \leq m(G)

3. Degree Formula for SVN Coronas

For a vertex vv in G⊡HG\boxdot H:

d_G(v), & \text{if } v \in V(G) \\ 2|V(H)| + 2, & \text{if } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{if } v = v_{i,j} \end{cases}$$ ### Analysis Strategy The paper employs a case-by-case analysis method for different graph class combinations: 1. **SVN coronas of paths** (Section 3) 2. **SVN coronas of cycles** (Section 4) 3. **SVN coronas of stars** (Section 5) 4. **SVN coronas of complete graphs** (Section 6) Each case is proven by constructing specific b-chromatic colorings that demonstrate the tightness of the upper bounds. ## Main Results ### b-chromatic number of Path SVN Coronas **Theorem 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{if } n=3 \text{ and } t \in \{3,4\} \\ 5, & \text{if } (n=3 \text{ and } t \geq 5) \text{ or } n \in \{4,5\} \\ n-1, & \text{if } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{otherwise} \end{cases}$$ **Theorems 7-9**: Similar exact formulas are provided for $P_n \boxdot C_t$, $P_n \boxdot S_t$, and $P_n \boxdot K_t$. ### b-chromatic number of Cycle SVN Coronas **Theorem 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{if } n \in \{3,4\} \\ n, & \text{if } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{otherwise} \end{cases}$$ ### b-chromatic number of Star SVN Coronas **Theorem 17**: Complete b-chromatic number formulas are established for SVN coronas of stars with fundamental graph classes, including the key result: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### b-chromatic number of Complete Graph SVN Coronas **Theorems 20-24**: Under m-degree constraints, the b-chromatic numbers of $K_n\boxdot G$ are provided, for example: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{under certain conditions} \\ n+2, & \text{under other conditions} \end{cases}$$ ## Technical Innovations ### 1. Constructive Proof Method - Not only proves upper bounds but also demonstrates lower bounds through explicit construction of optimal b-chromatic colorings - Each construction is accompanied by detailed graphical examples, enhancing the verifiability of results ### 2. b-rainbow Set Concept Introduces the concept of b-rainbow sets to simplify the identification of b-vertices, using different symbols in graphs: - Cross (×): vertices of specific b-rainbow sets - Triangle (△): other b-vertices - Circle (●): ordinary vertices ### 3. Modular Arithmetic Techniques Extensive use of modular arithmetic in coloring constructions to ensure periodicity and correctness, for example: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. Systematic Case Classification Refined case-by-case classification based on parameter ranges ensures comprehensive coverage of all possible scenarios. ## Experimental Verification ### Graphical Verification The paper provides numerous graphical examples to verify theoretical results: - Figure 2: Optimal b-chromatic coloring of $P_{10} \boxdot P_3$ - Figures 3-4: Colorings of path SVN coronas under different parameters - Figure 11: Coloring examples of cycle SVN coronas - Figures 17-18: Coloring constructions of star SVN coronas ### Construction Verification The proof of each theorem includes concrete coloring construction algorithms that can be directly verified: 1. Correctness of coloring (adjacent vertices have different colors) 2. Existence of b-vertices (each color class contains a b-vertex) 3. Optimality (achieves theoretical bounds) ## Related Work ### History of b-chromatic Number Research 1. **Irving-Manlove (1999)**: First introduced the concept of b-chromatic number 2. **Research on various graph products**: b-chromatic numbers of Cartesian products, direct products, strong products, etc. have been extensively studied 3. **Special graph classes**: b-chromatic numbers of paths, cycles, stars, and complete graphs are known ### Position of This Work - **Filling a gap**: Research on b-chromatic numbers of SVN coronas is relatively limited - **Methodological innovation**: Provides systematic construction methods - **Complete results**: Gives comprehensive results for combinations of fundamental graph classes ## Conclusions and Discussion ### Main Conclusions 1. **Completeness**: Complete determination of b-chromatic numbers is provided for SVN coronas of fundamental graph classes (paths, cycles, stars, complete graphs) 2. **Exactness**: All results are exact values, not approximations or bounds 3. **Constructiveness**: Provides concrete optimal coloring construction methods ### Limitations 1. **Graph class restrictions**: Only fundamental graph classes are considered; results for general graphs require further research 2. **Complete graph constraints**: Results for $K_n\boxdot G$ require m-degree constraint conditions 3. **Complexity**: Case-by-case classification is relatively complex in some situations ### Future Directions 1. **Extension to broader graph classes**: Study b-chromatic numbers of SVN coronas for more general graph classes 2. **Algorithm research**: Develop efficient algorithms for computing b-chromatic numbers 3. **Application exploration**: Apply results to practical network coloring problems ## In-depth Evaluation ### Strengths 1. **Significant theoretical contribution**: Systematically resolves the b-chromatic number problem for an important class of graph products 2. **Rigorous methodology**: Constructive proof methods ensure reliability of results 3. **Clear presentation**: Numerous figures and examples make complex proofs accessible 4. **Complete results**: Covers all important combinations of fundamental graph classes ### Weaknesses 1. **Limited technical innovation**: Primarily systematic application of existing methods, lacking fundamentally new techniques 2. **Unclear practical value**: Lacks discussion of practical application scenarios 3. **Missing complexity analysis**: Does not discuss time complexity of construction algorithms ### Impact 1. **Theoretical value**: Provides important supplement to graph b-chromatic number theory 2. **Methodological value**: Construction methods can be generalized to research on other graph products 3. **Completeness value**: Fills the gap in research on b-chromatic numbers of SVN coronas ### Applicable Scenarios 1. **Theoretical research**: Fundamental research in graph theory and combinatorial optimization 2. **Network design**: Network coloring problems requiring consideration of neighborhood constraints 3. **Algorithm design**: Serves as a foundational module for more complex graph coloring algorithms ## References The paper cites 25 related references, primarily including: - Irving & Manlove (1999): Original definition of b-chromatic number - Kouider & Mahéo et al.: Research on b-chromatic numbers of various graph products - Liu & Lu (2013): Spectral theory research on SVN coronas - Brooks (1941): Classical results in graph coloring