New answers tagged graph-colorings
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} - ...
- 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 ...
- 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
$$\...
- 148k
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 ...
- 10.1k
Top 50 recent answers are included