On the Generalized \vartheta-Number and Related Problems for Highly Symmetric Graphs

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Association schemes, strongly regular graphs (05E30) Programming involving graphs or networks (90C35)

Abstract: This paper is an in-depth analysis of the generalized

v a r t h e t a

-number of a graph. The generalized

v a r t h e t a

-number,

v a r t h e t a_{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

v a r t h e t a_{k} (G)

, such as that the sequence

(v a r t h e t a_{k} (G))_{k}

is increasing and bounded from above by the order of the graph

G

. We study

v a r t h e t a_{k} (G)

when

G

is the strong, disjunction or Cartesian product of two graphs. We provide closed form expressions for the generalized

v a r t h e t a

-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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081783)