Questions tagged [graph-theory]

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, topological-graph-theory, random-graphs, graph-colorings and several others.

3,400 questions
6k 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 ...
9k 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,...
6k 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 ...
12k views

What is a chess piece mathematically?

Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained open for more ...
7k 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 ...
8k 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 ...
4k views

Why are there 1024 Hamiltonian cycles on an icosahedron?

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron. By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$. [But see edit below re directed vs. undirected!] ...
8k 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. ...
3k views

Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy. Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
2k views

Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges? I know that the answer is ...
3k views

An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
4k views

Is there a “knot theory” for graphs?

I think knot theory has been studied for quite a while (like a century or so), so I'm just wondering whether there is a "knot theory" for graphs, i.e. the study of (topological properties of) ...
2k 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 ...
2k views

Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
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 ...
1k 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 ...
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

Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...
2k views

What (fun) results in graph theory should undergraduates learn?

I have the task of creating a 3rd year undergraduate course in graph theory (in the UK). Essentially the students will have seen minimal discrete math/combinatorics before this course. Since 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 ...
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 ...
974 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 ...