On a conjecture of wang and williams
N. V. R. Mahadev, Uri N. Peled · Journal of Graph Theory · 1991
Abstract Wang and Williams defined a threshold assignment for a graph G as an assignment of a non‐negative weight to each vertex and edge of G, and a threshold t, such that a set S of vertices is stable if and only if the total weight of the subgraph induced by S does not exceed t ‐ 1. This is always possible with zero vertex‐weights, unit edge‐weights, and t = 1. By definition, a threshold graph is a graph having a threshold assignment with zero edge‐weights. The threshold weight of G is the minimum total edgeweight of a threshold assignment of G. A graph G = (V,E) is called heavy if its threshold weight is |E|. A clique C of G is called big if |E(C)| > |E(G ‐ C)|. Wang and Williams showed that graphs with a big clique are not heavy, and conjectured the converse. They verified the conjecture for triangle‐free graphs. We disprove the conjecture in general, but prove it for perfect graphs.