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

**7**

**0**answers

### Is every 1-million-connected graph rigid in 3D?

**2**

**1**answer

### Minimizing the degree of outgoing edges in a digraph, does this problem have a name?

**3**

**1**answer

### Coloring almost-disjointness

**1**

**0**answers

### Another betweenness centrality measure: neighbourhood centrality

**4**

**2**answers

### The number of monochromatic triangles

**1**

**1**answer

### Finite graph not embeddable in $H(n,2)$

**1**

**0**answers

### Is there any theorem similar to the Tutte–Berge formula?

**9**

**1**answer

### Conjecture on minimum size of graph

**0**

**2**answers

### Acyclic proper coloring of 2-degenerate graphs

**0**

**0**answers

### Possible trajectories with time travel [closed]

**0**

**1**answer

### Could you provide some TSP examples from real world to test a new algorithm?

**2**

**1**answer

### For a three-connected graph, is there a contraction edge that strictly increases vertex connectivity?

**0**

**0**answers

### Travelling salesman problem with variable weights

**6**

**1**answer

### Determinant of walk matrix for a skew-symmetric matrix of even order

**4**

**2**answers

### High degree differences in bipartite graphs

**7**

**1**answer

### Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?

**0**

**0**answers

### How to classify rings by combinatorial structures?

**11**

**1**answer

### “Drinking number” of a graph

**8**

**1**answer

### Find all Non-isomorphic good drawings of $K_{3,3}$？

**2**

**0**answers

### Random walk on non-abelian free group

**0**

**0**answers

### Sufficient criterion for unit distance graphs

**3**

**1**answer

### Constructing a 1-planar graph that has no rectilinear drawing

**2**

**0**answers

### Coloring finite subsets of a fixed size with a single modular function

**-1**

**1**answer

### Helsgaun's $k$-Opt moves

**11**

**2**answers

### How many finitely-generated-by-elements-of-finite-order-groups are there?

**1**

**0**answers

### Is this graph theory paper in German translated into English?

**12**

**1**answer

### Is the Petersen graph a “Cayley graph” of some more general group-like structure?

**1**

**1**answer

### Can Tutte embedding be guaranteed that each face is convex?

**5**

**2**answers

### Line graphs called “graph derivatives”: any intuition?

**0**

**0**answers

### Probability that edge exchange yields a tour

**0**

**0**answers

### maximum radius for a $k$-set of vertices in a graph

**1**

**0**answers

### Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

**1**

**0**answers

### Probability that a graph and its complement are connected

**1**

**0**answers

### When are the 3-colorings of vertex subsets uncorrelated?

**1**

**1**answer

### Probability process involving blocking paths of rooted tree

**9**

**3**answers

### Pairs of vertices with high degree difference

**0**

**1**answer

### Is graph's planar embedding unique if each block of one planar graph is 3-connected?

**7**

**2**answers

### Chip-firing clocks

**2**

**1**answer

### Directed version of this lemma

**1**

**0**answers

### Finding a tree with adjacency matrix near a given matrix

**1**

**1**answer

### “Circuit rank” but for vertices

**2**

**1**answer

### Notation for H is isomorphic to a subgraph of G

**2**

**1**answer

### Expansion in hypergraphs

**0**

**1**answer

### Connected graphs on $\omega$ that “doesn't change” whenever 2 points are collapsed

**2**

**1**answer

### Min-sum and min-max node-disjoint path problems

**-1**

**1**answer

### Path sequences and isomorphism of graphs

**3**

**1**answer

### On cospectral graphs

**5**

**2**answers

### Smallest $3$-regular graph with a unique perfect matching

**2**

**0**answers

### Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

**4**

**1**answer