# Tagged Questions

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

4k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week,...
5k views

### What is a continuous path?

I would like some help, because I am getting mad trying to answer the following Question: Let $X$ be a topological space, what is a continuous path in $X$? Well, maybe you're already getting ...
5k views

### Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another. My main ...
5k views

### Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
5k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
2k views

### History of the four-colour problem

It is stated in many places that the first published reference to the four-colour problem (aka the four-color problem) was an anonymous article in The Athenæum of April 14, 1860, attributed to de ...
7k views

3k views

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings, fields, graphs, partial orders, etc. ...
1k views

### Should axiomatic set theory be translated into graph theory?

Recently I saw the abstract of a paper by Nash-Williams: Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following: The author ...
3k views

### Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
4k views

### Spectral graph theory: Interpretability of eigenvalues and -vectors

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally ...
1k views

### Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square. $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ ...
2k views

### Does this knot invariant distinguish trefoil chiralities?

Let $C_N$ denote the labelled configuration of $N^{th}$ roots of unity with $p_J = e^{\frac{2\pi iJ}{N}}$ for $J = 1\ldots N$. As a corollary of something else I was playing around with, I recently ...
909 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
518 views

### What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation: $$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$ $a$ is an ...
3k views

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the ...
4k views

### Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], [3]...
28k views

### How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
437 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph? I'd like to avoid exhaustive ...
12k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
41k views

### Good programs for drawing graphs ( directed weighted graphs )

Does anyone know of a good program for drawing directed weighted graphs?
2k views

### Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
2k views

### An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
778 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
883 views

### Disjoint stable sets in tournaments

Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with ...
1k views

### Some models for random graphs that I am curious about

G(n,p) We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
843 views

### Is the Rado graph a Cayley graph? If so, what is the group like? (And other questions…)

The countable random graph, also known as the Rado graph, is characterized as the unique countable graph in which every two disjoint finite sets $A$ and $B$ of vertices admit a vertex $p$ connected to ...
1k views

### Rock-paper-scissors…

A directed graph whose underlying undirected graph is complete is called a tournament. Let us call a (finite) directed graph balanced if every vertex has as many incoming as outgoing edges. The ...
1k views

### Who wins this two-player game based on the sandpile model?

Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an ...
I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed! Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...