New answers tagged

6 votes
Accepted

Sum of squares of chromatic roots of a bipartite graph

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - ...
1001's user avatar
  • 526
1 vote

Clique number of $k$-critical graphs

For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and ...
Tony Huynh's user avatar
  • 30.3k
4 votes

Three-dimensional triangulations with fixed number of vertices

$\def\RR{\mathbb{R}}\def\ZZ{\mathbb{Z}}\def\Hull{\text{Hull}}$ This is a broken answer; it gives a triangulation of the lens space $L(3,1)$, not $S^3$. Step 1 The cylinder: Inside $\RR^3$, define $$\...
David E Speyer's user avatar
21 votes
Accepted

Parity and the Axiom of Choice

The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another ...
bof's user avatar
  • 10.1k

Top 50 recent answers are included