Graph Parameters
See also the substructure page
These are different numerical graph parameters that can be computed. They range from very simple (vertex count) to difficult (Shannon capacity). Some are integer, some are real valued.
I try to give the complexity of computing them: P or NPC, mostly. I also try to give their parameterized complexity and their complexity of approximation. When the complexity is already P, I mark the other two complexity columns with 
to show that it’s pretty irrelevant^{1}.
“Monotonic” means “how does this change when you add edges?”. ⬆️ means it’s weakly increasing with edge additions, ⬇️ means it weakly decreasing with edges, and ❌ means that it isn’t monotonic.
The “relationship” column is purely subjective: it’s the one relationship (to other parameters) that I view as most important in summarizing their relationship to each other. There’s certainly room to build this out. If the row says something like i  c  p  a  m  r
, that’s just placeholder for me to fill in later.
Name  Notation  Integer?  Complexity  Parameterized  Approximation  Monotonic  Relationship 

Sizes  
Order  V(G)  Y  P      =  
Size  E(G)  Y  P      ⬆️  E ≤ V*(V1)/2 
Max Degree  Δ(G)  Y  P      ⬆️  
Min Degree  δ(G)  Y  P      ⬆️  
Radius  r(G)  Y  P      ⬆️  
Diameter  d(G)  Y  P      ⬆️  
Girth  g(G)  Y  P      ⬇️  
ConstraintBased  
Clique No.  ω(G)  Y  NPC  W[1]C  a  ⬆️  ceil(V^2/(V^2  2*E)) ≤ ω ^{2} 
Chromatic No.  χ(G)  Y  NPC  paraNPC^{3}  …  ⬆️  ω ≤ χ 
Chromatic Index  χ’(G)  Y  NPC  ⬆️  Δ ≤ χ’ ≤ Δ+1  
Independence No.  α(G)  Y  NPC  p  a  ⬇️  α(G) = ω(G̅) 
Domination No.  γ(G)  Y  NPC  W[2]C  LogAPXC  ⬆️  γ ≤ α 
Independent domination No.  i(G)  Y  c  p  a  r  γ ≤ i ≤ α 
Intersection No.  ?  Y  NPC  FPT  NPC?^{4}  ?  … 
Minimum Vertex Cover  VC(G)  Y  c  p  a  m  r 
Connectivity  
Crossing No.  cr(G)  Y  c  p  a  m  r 
Hadwiger No.  h(G)  Y  NPC  FPT  ⬆️  Does χ(G) ≤ h(G) ? 

Conductance^{5}  ϕ(G)^{5}  N  P      ⬆️  r 
Genus  gn(G)^{6}  Y  NPC  FPT  ⬆️  
Edgeconnectivity  ec(G)^{7}  Y  P      ⬆️  r 
Vertexconnectivity  vcn(G)^{7}  Y  P      ⬆️  r 
Circumference  cfr(G)^{7}  Y  NPC  p  a  ⬆️  r 
Matrix Ranks  
Verdière’s invariant  μ(G)  i  c  p  a  m  r 
Minimum rank  mr(G)  i  c  p  a  m  r 
Independencelike  
Lovasz No.  ϑ(G)  N  P      ?  ω(G) <= ϑ(G̅) <= χ(G) 
Shannon Capacity  ϴ(G)  N  ?^{8}      ⬇️  α <= ϴ <= ϑ 
Entanglementassisted Shannon capacity  ϴ^{*}(G)  i  c  p  a  m  r 
Entanglementassisted OneShot ZeroError capacity  c_{0}^{*}(G)  i  c  p  a  m  r 
“Beta Parameter”^{9}  β(G)  N  P?      ⬇️  α <= β <= ϑ 
Chromaticlike  
Orthogonal rank  ξ(G)  i  c  p  a  m  r 
Normalized orthogonal rank  ξ’(G)  i  c  p  a  m  r 
Projective rank  ξ_{f}(G)  i  c  p  a  m  r 
Circular Chromatic No.  χ_{c}(G)  i  c  p  a  m  r 
Fractional Chromatic No.  χ_{f}(G)  i  c  p  a  m  r 
Vector Chromatic No.  χ_{v}(G)  i  c  p  a  m  r 
Vectorial Chromatic No.  χ_{vect}(G)  i  c  p  a  m  r 
Quantum Chromatic No.  χ_{q}(G)  i  c  p  a  m  r 
Rank1 Quantum Chromatic No.  χ^{(1)}_{q}(G)  i  c  p  a  m  r 
Other?  
Hajós No.  h(G)  Y  ?^{10}      ?  h <= 2^(V^2/3  E + 1) ^{10} 
Parameters and binary operations
This table describes how parameters change under operations. V and E are omitted, as those are already discussed above.
Parameter → ↓ Op 
ω  χ  α  γ  i  ϑ  ϴ  β 

Cartesian Prod  ?  = Max  some bounds  ≥ Prod?  ?  ?  ?  ? 
Tensor Prod  ?  ≤ Min^{11}  ?  ?  ?  ?  ?  ? 
Strong Prod  = Prod  ?  ?  ?  ?  ?  ?  ? 
Conormal Prod  ?  ?  ?  ?  ?  ?  ?  ? 
Modular Prod  ?  ?  ?  ?  ?  ?  ?  = Prod 
Lexico. Prod  ?  ?  ?  ?  ?  ?  ?  ≥ Prod 
Homomorphic Prod  ?  ?  ?  ?  ?  ?  ?  ? 
Disjoint Union  = Max  = Max  = Sum  = Sum  ?  ?  ?  ? 
Graph Join  = Sum  = Sum  = Max  ≤ 2^{12}  ?  ?  ?  ? 
Unary  
Mycielskian  Max(2,ω)  χ+1  a formula  γ+1  ?  ?  ?  ? 
Footnotes
I have a todo list for this page.

It would be an interesting question to see if there are parameters in P that can be efficiently approximated much faster. Spectral radius is an obvious candidate, as current SOTA algorithms compute it in O(n^2.38), which might be slow for some people’s tastes. Something like “average pairwise distance” can be computed in O(n^3) time but maybe approximated better. The Lovasz number can be efficiently computed with an SDP but that’s moderately slow. Have at it, ye lovers of the finegrained! ↩

This is an equivalent way of writing Turán’s theorem. ↩

ParaNPC means that deciding a fixed parameter (e.g. k=3 – is the graph 3colorable?) is already NPComplete, this gives the parameterized class paraNPcomplete, or paraNPC. ↩

If I write that something is “NPC” to approximate, this means that I’ve come across a statement that it’s “NPhard to approximate” and haven’t investigated as to how hard to approximate. ↩

Conductance is also often called the Cheeger constant, which is more typical for unweighted graphs. In those contexts, it is written
h(G)
. We use the conductance notation ofϕ(G)
to avoid conflict with the Hadwiger number. ↩ ↩^{2} 
Graph genus is often notated as
γ(G)
. We writegn(G)
to avoid conflict with the domination numberγ(G)
and girthg(G)
. ↩ 
This is nonstandard notation that I’ve invented here, because it doesn’t seem to have a standard number in the literature (except perhaps a generic k). ↩ ↩^{2} ↩^{3}

It is unknown whether the Shannon capacity is even decidable. ↩

I’d personally propose naming this the “quantum independence radius”. The authors simply call it the “beta parameter”. ↩

Proving that
h <= poly(V)
would imply that NP=coNP, see the discussion here. Little is know about how hardh
is to compute, except that (trivially) it’s inNEXP
because of the exponential bounds on its size. ↩ ↩^{2} 
It was believed that the chromatic number of tensor product was exatly the minimum of the chromatic number of the factors, known as Hedetniemi’s_conjecture. It is easy to see that it is at most the minimum of the factors. In 2019 the conjecture was disproved, that the
< Min
case can occur too. ↩ 
The domination number of a graph join is always exactly two (by taking one vertex from each half of the join), unless either factor has a universal vertex (i.e. has a domination number of one), in which case the domination number is one; unless both addends are the empty graph, in which case the domination number is zero. ↩