Algebras, Graphs and Thetas

We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such g...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2019-08, Vol.346, p.275-283
Main Authors: de Carli Silva, Marcel K., Coutinho, Gabriel, Godsil, Chris, Roberson, David E.
Format: Article
Language:English
Subjects:
clique-coclique inequality
coherent configuration
Lovász theta function
matrix ⁎-algebra
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such graph, and some theta variants, including characterizations of the equality.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2019.08.025