Optimization Online


On the generalized $\vartheta$-number and related problems for highly symmetric graphs

Lennart Sinjorgo(l.m.sinjorgo***at***tilburguniversity.edu)
Renata Sotirov(r.sotirov***at***uvt.nl)

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 )


Download: [PDF]

Entry Submitted: 04/24/2021
Entry Accepted: 04/26/2021
Entry Last Modified: 04/24/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society