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

15
votes

### Who is M. Meyniel?

This "M. Meyniel" is indeed, and definitively, Henri Meyniel (sometimes spelled Henry Meyniel). Note that the article you mention was communicated by Berge, at a time (1972) when Meyniel was ...

9
votes

Accepted

### Is there an algorithm to generate graphs with given order and diameter?

About 58% of the graphs on 12 vertices have diameter 3, so filtering a complete generation will be as fast as any. On 20 vertices the fraction has dropped to about 31% but the total is so vast that ...

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} - ...

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
$$\...

4
votes

Accepted

### Determining graph Isomorphism: combining invariants

There will be strongly-regular graphs of the same parameters with equal values of all those invariants. Since the parameters determine the eigenvalues, all the invariants determined by the spectrum (...

4
votes

### Enumerating all inequivalent planar embeddings of a planar graph

As suggested by Henrik Rüping in the comments, this problem can be solved in principle using the representation of embeddings by permutations, i.e., using combinatorial maps (aka "rotation ...

2
votes

### Graph alignment by considering node and edge weights

This is a very interesting problem, although I'm not sure if it's a mathematical problem exactly (as opposed to one of algorithmic modeling). That said, here are some two suggestions.
Suggestion #1: ...

2
votes

Accepted

### Isomorphism of two regular hypergraphs

No. There are already multiple isomorphism classes of regular graphs. Consider two disjoint triangles (i.e., $\{12,23,31\}\cup \{45,56,64\}$), versus a cycle of length 6 ($\{12,23,34,45,56,61\}$).

2
votes

### Enumerating all inequivalent planar embeddings of a planar graph

I had this same problem. I couldn't find any actually implemented code after a lot of looking, but I did find some papers describing how to do it.
The most promising was "A linear algorithm for ...

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

1
vote

### Tree decomposition of graphs with low height

One way to address this question is to think of a tree decomposition as an unrooted tree. Then, it is easy to see that its diameter is related to the depth by a factor of 2. Searching for diameter, ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

graph-theory × 5001co.combinatorics × 2145

graph-colorings × 511

reference-request × 440

algorithms × 334

pr.probability × 272

spectral-graph-theory × 255

random-graphs × 199

gr.group-theory × 189

computational-complexity × 189

extremal-graph-theory × 179

linear-algebra × 170

discrete-geometry × 167

mg.metric-geometry × 134

matching-theory × 123

combinatorial-optimization × 116

trees × 103

set-theory × 101

infinite-combinatorics × 99

matrices × 95

hypergraph × 95

perfect-matchings × 95

bipartite-graphs × 91

algebraic-graph-theory × 88

hamiltonian-graphs × 87