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

**64**

**6**answers

### Which graphs are Cayley graphs?

**62**

**4**answers

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

**58**

**9**answers

### What is a continuous path?

**53**

**4**answers

### What is a chess piece mathematically?

**52**

**4**answers

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

**50**

**17**answers

### Generalizations of the Four-Color theorem

**49**

**1**answer

### Why are there 1024 Hamiltonian cycles on an icosahedron?

**47**

**4**answers

### Do there exist chess positions that require exponentially many moves to reach?

**43**

**2**answers

### Does knight behave like a king in his infinite odyssey?

**43**

**4**answers

### Why are planar graphs so exceptional?

**43**

**3**answers

### History of the four-colour problem

**42**

**1**answer

### Can't one walk to infinity on the prime numbers with finitely many distinct affine steps?

**42**

**0**answers

### Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

**39**

**15**answers

### Strengthening the Induction Hypothesis

**39**

**4**answers

### Why is “P vs. NP” necessarily relevant?

**39**

**6**answers

### Is it easy to produce hard-to-color graphs?

**39**

**1**answer

### What is the sandpile torsor?

**38**

**23**answers

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

**37**

**17**answers

### Linear Algebra Proofs in Combinatorics?

**37**

**5**answers

### Algebraic Proof of 4-Colour Theorem?

**34**

**21**answers

### Generalizations of Planar Graphs

**34**

**14**answers

### What are the Applications of Hypergraphs

**34**

**2**answers

### How to find Erdős' treasure trove?

**34**

**7**answers

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

**33**

**4**answers

### Graph containing all trees?

**33**

**5**answers

### How large is TREE(3)?

**32**

**18**answers

### Interesting and Accessible Topics in Graph Theory

**32**

**2**answers

### A conjecture on planar graphs

**31**

**3**answers

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

**31**

**3**answers

### How much linear algebra can be done with graphs?

**31**

**3**answers

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

**31**

**1**answer

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

**31**

**0**answers

### 3-colorings of the unit distance graph of $\Bbb R^3$

**30**

**9**answers

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

**30**

**3**answers

### Can assignment solve stable marriage?

**30**

**5**answers

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

**30**

**1**answer

### An edge partitioning problem on cubic graphs

**29**

**8**answers

### Is there a “knot theory” for graphs?

**29**

**1**answer

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

**28**

**3**answers

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

**28**

**4**answers

### Adjacency matrices of graphs

**28**

**3**answers

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

**27**

**9**answers

### Is the empty graph a tree?

**27**

**8**answers

### Applications of infinite graph theory

**27**

**10**answers

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

**27**

**2**answers

### An unfair marriage lemma

**27**

**1**answer

### Does this knot invariant distinguish trefoil chiralities?

**27**

**2**answers

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

**26**

**1**answer

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

**26**

**2**answers