Increasing the b-Chromatic Number of Complete Bipartites by Deleting Edges

Authors

Daniel Gawel, DePaul UniversityFollow

Faculty Advisor

Dr.Emily Barnard

Abstract

A b-coloring of a graph, G=〈V,E〉, is a proper coloring in which each color has at least one vertex that is adjacent to every other color. The b-chromatic number for G, denoted φ(G), is the largest number of colors you can use to make a b-coloring. For most graphs, φ(G), is around the m-index, an upper bound for φ(G) based on the graph's degree sequence. However, for the complete bipartite graph K_m,n, φ(K_m,n)=2 even though the m-index can be arbitrarily large. In this paper we will delete edges from complete bipartites so we can increase their b-chromatic number. Specifically, we will delete the fewest amount of edges that it takes to maximize the b-chromatic number of complete bipartites.

Recommended Citation

Gawel, Daniel (2024) "Increasing the b-Chromatic Number of Complete Bipartites by Deleting Edges," DePaul Discoveries: Volume 13, Article 7.
Available at: https://via.library.depaul.edu/depaul-disc/vol13/iss1/7