Edge-contraction clique-monotone graph characterization
Characterization of Social Graphs · arXiv:1603.07056
Status open high confidence
Fox and Wei introduce social graphs—graphs $G$ in which contracting any edge does not increase the total number of cliques—as a key structural tool for bounding the number of cliques in $K_t$-minor-free graphs, proving that any very dense social graph is, apart from a small set of vertices, the complement of a matching. The full characterization of social graphs is explicitly flagged in the paper as a challenging open problem. A 2024 preprint (arXiv:2408.12082) on extremal clique counts with forbidden clique minors references questions of Wood and Fox–Wei in a related direction, but does not resolve the social graph characterization. No subsequent paper settling the characterization was found in the indexed literature through May 2026.
Reviewer notes. The term 'social graph' in Fox–Wei 2016 is a technical graph-theoretic concept (edge contraction does not increase clique count), distinct from the colloquial 'social network graph'. Searches using the term return mostly unrelated social-network papers. The conjecture is from a 2016 arXiv paper published in J. Combin. Theory Ser. B in 2017; no resolution found after wide search.
Context
Social graphs are introduced as a key structural tool in the proof of Theorem 1.2: the authors show that any very dense social graph is, apart from a small number of vertices, the complement of a (not necessarily perfect) matching. The paper explicitly notes that a full characterization of social graphs appears to be a challenging problem.
Notes. Stated in running prose: 'It appears to be a challenging problem to characterize social graphs.'
Source paper
On the number of cliques in graphs with a forbidden minor
Jacob Fox, Fan Wei · 2016-03-23
https://arxiv.org/abs/1603.07056
PDF source