On Graphs With Prescribed Chromatic Number and Subset Index
Gary Chartrand, Ebrahim Salehi, Ping Zhang · Contributions to Mathematics · 2022
For a nontrivial graph G, a subset labeling of G is a labeling of the vertices of G with nonempty subsets of the set [r] = {1, 2, . . ., r} for a positive integer r such that two vertices of G have disjoint labels if and only if the vertices are adjacent.The subset index of G is the minimum positive integer r for which G has such a subset labeling from the set [r]. Structures of graphs with prescribed subset index are investigated.It is shown that for every two integers a and b with 2 ≤ a ≤ b, there exists a connected graph with chromatic number a and subset index b.