On the generalized $\vartheta$-number and related problems for highly symmetric graphs
Abstract: This paper is an in-depth analysis of the generalized $\vartheta$-number of a graph. The generalized $\vartheta$-number, $\vartheta_k(G)$, serves as a bound for both the $k$-multichromatic number of a graph and the maximum $k$-colorable subgraph problem. We present various properties of $\vartheta_k(G)$, such as that the series $(\vartheta_k(G))_k$ is increasing and bounded above by the order of the graph $G$. We study $\vartheta_k(G)$ when $G$ is the graph strong, disjunction and Cartesian product of two graphs. We provide closed form expressions for the generalized $\vartheta$-number on several classes of graphs including the Kneser graphs, cycle graphs, strongly regular graphs and orthogonality graphs. Our paper provides bounds on the product and sum of the $k$-multichromatic number of a graph and its complement graph, as well as lower bounds for the $k$-multichromatic number on several graph classes including the Hamming and Johnson graphs.
Keywords: $k$--multicoloring, $k$-colorable subgraph problem, generalized $\vartheta$-number, Johnson graphs, Hamming graphs, strongly regular graphs.
Category 1: Linear, Cone and Semidefinite Programming
Category 2: Combinatorial Optimization (Graphs and Matroids )
Entry Submitted: 04/24/2021
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|