A note on simplicial cliques

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.disc.2021.112470

A note on simplicial cliques

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.

Original language	American English
Article number	112470
Journal	Discrete Mathematics
Volume	344
Issue number	9
DOIs	https://doi.org/10.1016/j.disc.2021.112470
State	Published - Sep 2021

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Claw-free
Even-hole-free
Induced subgraphs
Simplicial clique

Access to Document

10.1016/j.disc.2021.112470

Cite this

@article{4bcfb6be61664dd0bff591468c5b3288,

title = "A note on simplicial cliques",

abstract = "Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.",

keywords = "Claw-free, Even-hole-free, Induced subgraphs, Simplicial clique",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = sep,

doi = "10.1016/j.disc.2021.112470",

language = "American English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9",

}

TY - JOUR

T1 - A note on simplicial cliques

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2021/9

Y1 - 2021/9

N2 - Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.

AB - Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.

KW - Claw-free

KW - Even-hole-free

KW - Induced subgraphs

KW - Simplicial clique

UR - http://www.scopus.com/inward/record.url?scp=85111074712&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85111074712&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112470

DO - 10.1016/j.disc.2021.112470

M3 - Article

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

M1 - 112470

ER -

A note on simplicial cliques

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this