## 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