2025/10/01 by Eunice Mphako-Banda, Mphako-Banda, Eunice, Christo Kriel +3
Mathematics · #05C15 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2510.00712
openalex publication_date 2025/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we introduce and study a novel graph parameter called the k-defect number, denoted ϕk(G), for a graph G and an integer 0≤ k≤ |E(G)|. Unlike traditional defective colorings that bound the local degree within monochromatic components, the k-defect number represents the smallest number of colors required to achieve a vertex coloring of G having exactly k monochromatic edges (also termed ``bad edges"). This parameter generalizes the well-known chromatic number of a graph, χ(G), which is precisely ϕ0(G). We establish fundamental properties of the k-defect number and derive bounds on ϕk(G) for specific graph classes, including trees, cycles, and wheels. Furthermore, we extend and generalize several classical properties of the chromatic number to this new edge-centric k-defect framework for values of 1≤ k≤ |E(G)|.