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

DOI10.1137/21M1414620zbMath1494.05048arXiv2104.11910OpenAlexW3158620435MaRDI QIDQ5081783

Publication date: 17 June 2022

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.11910

zbMATH Keywords

strongly regular graphs Johnson graphs Hamming graphs $k$-colorable subgraph problem $k$-multicoloring generalized $\vartheta$-number

Mathematics Subject Classification ID

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

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Estimation of Laplacian spectra of direct and strong product graphs
Solving VLSI design and DNA sequencing problems using bipartization of graphs
$k$-fold coloring of planar graphs
Spectra of graphs
Kneser's conjecture, chromatic number, and homotopy
Multicoloring and Mycielski construction
Eigenvalue bounds for independent sets
Finding a maximum-weight induced $k$-partite subgraph of an $i$-triangulated graph
Extremal problems concerning Kneser-graphs
Hamiltonian uniform subset graphs
Orthogonal vectors in the $n$-dimensional cube and codes with missing distances
The maximum k-colorable subgraph problem for chordal graphs
The node-deletion problem for hereditary properties is NP-complete
Generalized k-tuple colorings of cycles and other graphs
The ellipsoid method and its consequences in combinatorial optimization
n-tuple colorings and associated graphs
Every planar map is four colorable. I: Discharging
Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
The sandwich theorem
Lifted, projected and subgraph-induced inequalities for the representatives $k$-fold coloring polytope
On optimal $k$-fold colorings of webs and antiwebs
Planar graphs are $9/2$-colorable
The chromatic number and other functions of the lexicographic product
Minimizing the sum of the $k$ largest functions in linear time.
Symmetry groups, semidefinite programs, and sums of squares
Coloring graph products---a survey
A survey of Nordhaus-Gaddum type relations
Counterexamples to Hedetniemi's conjecture
The independence number of the orthogonality graph in dimension $2^k$
Algorithmic and explicit determination of the Lovász number for certain circulant graphs
On the theta number of powers of cycle graphs
An evolutionary approach for bandwidth multicoloring problems
Edmonds polytopes and a hierarchy of combinatorial problems
A note on the stability number of an orthogonality graph
On Complementary Graphs
Graphs with Given Group and Given Graph-Theoretical Properties
Circulants and their connectivities
A Branch-And-Price Approach for Graph Multi-Coloring
Multi-coloring the Mycielskian of graphs
Coloring an Orthogonality Graph
The Operator $\Psi$ for the Chromatic Number of a Graph
Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
Forbidden Intersections
Applications of product colouring
On the Shannon capacity of a graph
A (<5)-Colour Theorem for Planar Graphs
Exact Formulae for the Lovász Theta Function of Sparse Circulant Graphs
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
The Maximum k-Colorable Subgraph Problem and Related Problems
Mathematical Foundations of Computer Science 2004
Approximation and Online Algorithms
Maximum distance<tex>q</tex>-nary codes
The Erdős-Ko-Rado theorem for integer sequences

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