TODO List
Subgraph finding as I started here
Different kinds of relationships based on categories: 1, 2, 3
Other good things to add:
[https://en.wikipedia.org/wiki/Crossing_number_inequality]
Conjecture: μ(G) + 1 >= χ(G)
Conjecture: relationship between μ and χ
Vizing’s theorem
[https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture]
Standard FPT parameters (treewidth/branchwidth/pathwidth/twinwidth)
Queue number (analogous to stacknumber aka book thickness)
k-planarity? - not sure if this is really a parameter
Fractional chromatic number - note that chi_F(G) * alpha(G) >= V, which is coolVarious “quantum homomorphism” and “chromatic” numbers
Linear aboricity, arboricity, Acyclic coloring, and the Thue number are all mentioned on the “Edge coloring” page with different relationships
“Broadcast coloring” aka “Packing coloring” as mentioned in this paper. Also mentions “packing numbers” η_i. Here η_1 is the independence number, and η_2 is the largest independent set with all vertices more than distance 2, etc. Nice fact: η_2 is preserved by the Mycielskian if there’s no isolated vertices, and η_3 is preserved if connected.
See this – maximum induced path length (“detour number”), maximum induced cycle length, induced path number, and induced path cover – seem related to parameterized complexity (detour number ~= tree-depth (only for sparse graphs?)), and it’s cool that detour number is within a constant factor hard to approximate as independent sets. Check Hostad for info on how hard that is
Bandwidth and … broadcast time for “gossip”?
Average distance-ish things: Wiener, Wiener Sum, Balaban, Kirckhoff
Algebraic connectivity describes mixing time. It has good relationships and bounds. Unfortunately, standards are a bit of a mess of which Laplacian matrix you use. See MathWorld too.
Mathjax testing
\[Hi\]It’s $ 5^3 $ and $2_5$. I can write in $ \mathbb{r} \bf{r} \nabla_\boldsymbol{r}$
\[\begin{aligned} E = mc^2 \end{aligned}\]And I can try \[ 3 + 5 \] here and $ 3+5 $ or $3^5$. Symbols:
\[\nabla \delta \Delta \Gamma \gamma \epsilon \varepsilon \times \square \circ \Circle \otimes \oplus\]\(a^2 + b^2 = c^2\) –> note that all equations between these tags will not need escaping!
[ \frac{1}{n^{2}} ]