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} - ...
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 ...
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
$$\...
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 ...
Top 50 recent answers are included
Related Tags
graph-colorings × 610graph-theory × 511
co.combinatorics × 326
hypergraph × 54
reference-request × 40
infinite-combinatorics × 38
algorithms × 31
set-theory × 30
computational-complexity × 23
discrete-geometry × 21
extremal-graph-theory × 21
ramsey-theory × 18
matching-theory × 13
combinatorial-optimization × 12
cayley-graphs × 11
bipartite-graphs × 10
graph-minors × 10
chromatic-polynomial × 10
perfect-matchings × 9
lo.logic × 8
pr.probability × 7
planar-graphs × 7
extremal-combinatorics × 6
directed-graphs × 6
colorings × 6