21 votes

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
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 ...
Greg82's user avatar
  • 251
9 votes

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 ...
Brendan McKay's user avatar
6 votes

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
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
4 votes

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 (...
Brendan McKay's user avatar
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 ...
Noam Zeilberger's user avatar
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: ...
Bill Bradley's user avatar
  • 3,700
2 votes

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\}$).
Zach Hunter's user avatar
  • 2,734
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 ...
didericis's user avatar
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
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, ...
Vinicius dos Santos's user avatar

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