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

DOI10.1137/21M1414620zbMATH Open1494.05048arXiv2104.11910OpenAlexW3158620435MaRDI QIDQ5081783FDOQ5081783

Authors: Lennart Sinjorgo, Renata Sotirov 

Publication date: 17 June 2022

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

Abstract: This paper is an in-depth analysis of the generalized $vartheta$-number of a graph. The generalized $vartheta$-number, $varthet{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 $varthet{a}_k(G)$, such as that the sequence $(varthet{a}_k(G){)}_k$ is increasing and bounded from above by the order of the graph $G$. We study $varthet{a}_k(G)$ when $G$ is the strong, disjunction or 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.

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

Recommendations

• On the chromatic number of certain highly symmetric graphs
• scientific article; zbMATH DE number 1285774
• On notions generalizing combinatorial graphs, with emphasis on linear symmetric dihypergraphs
• scientific article; zbMATH DE number 3924813
• Symmetric graphs from polytopes of high rank
• Generalized symmetry of graphs - a survey
• On large vertex-symmetric digraphs
• On a class of finite symmetric graphs
• On Sheehan's Conjecture for Graphs with Symmetry
• On several symmetry conditions for graphs

zbMATH Keywords

strongly regular graphsJohnson graphsHamming graphs\(k\)-colorable subgraph problem\(k\)-multicoloringgeneralized \(\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

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

Cited In (3)

• On large vertex-symmetric digraphs
• On Sheehan's Conjecture for Graphs with Symmetry
• On the chromatic number of certain highly symmetric graphs

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)