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

**6**

**0**answers

### $R(3,6) = 18$, especially proving that $R(3,6)>17$

**19**

**3**answers

### Does the hypergraph of subgroups determine a group?

**6**

**1**answer

### Blocking $a\to b\to c$ in a DAG with bounded degrees

**12**

**3**answers

### A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

**1**

**1**answer

### $(k,n)$-binary graphs

**13**

**1**answer

### Can the graph of a symmetric polytope have more symmetries than the polytope itself?

**9**

**1**answer

### Representations of the automorphism group of graphs via spectral graphs theory

**19**

**2**answers

### Is it possible that both a graph and its complement have small connectivity?

**1**

**1**answer

### The Kronecker product of two bipartite graphs' biadjacency matrices: what's it called?

**6**

**0**answers

### Combinatorial region-halfplane incidence structures

**2**

**0**answers

### Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?

**1**

**0**answers

### A Random Graph Process

**-1**

**1**answer

### pruning a special graph

**0**

**0**answers

### When is the first blocking flow created in Dinic's algorithm a max flow?

**8**

**0**answers

### Colored weighted Graphs with only monochromatic perfect matchings

**2**

**1**answer

### Graphs with exactly $n$ perfect matchings

**6**

**0**answers

### What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

**0**

**1**answer

### Connected infinite graphs in which all matchings are “small”

**5**

**1**answer

### Two graphs with the same number of walks but without a common equitable partition

**3**

**1**answer

### Asymptotic colouring of edges and vertices, and untwisting cocycles

**1**

**1**answer

### monochromatic induced subgraph in a complete 3-partite graph

**0**

**0**answers

### A series of operations on a graph $G$ to obtain a specific family of subgraphs of $G$

**3**

**1**answer

### Maximal matchings in connected graphs

**2**

**2**answers

### Graphs in which all maximal matchings intersect

**0**

**0**answers

### Search an undirected graph for a path with specified, ordered vertex valencies

**4**

**1**answer

### Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets

**7**

**1**answer

### Number of (distinct) knots with a bounded number of crossings

**0**

**3**answers

### Minimize edge number under diameter and max-degree constraint

**0**

**1**answer

### Find all paths on undirected Graph [closed]

**4**

**2**answers

### Vertex cover number vs matching number

**3**

**0**answers

### $\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

**4**

**0**answers

### Groups inducing edge-colorings on graphs. Is this concept known?

**1**

**2**answers

### Constructing an n-node DAG, with exactly k paths between node 1 and node n [closed]

**2**

**0**answers

### Tutte polynomial from independent sets of a graph

**0**

**1**answer

### How to find a random cycle in a large graph?

**7**

**0**answers

### IH-moves on trivalent graphs, and a complex that might be known to low-dimensional topologists

**5**

**1**answer

### $\{ P_3, P_4 \}$-factor

**6**

**1**answer

### Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?

**5**

**1**answer

### Countable version of Erdös-Lovasz-Faber conjecture

**5**

**1**answer

### Can two non-equivalent polytopes of same dimension have the same graph?

**8**

**1**answer

### Maximum number of triangles no two of which have a common edge

**3**

**1**answer

### Transfer-impedance matrix for edge correlations in random spanning tree

**0**

**0**answers

### Interesting First-Order Properties of Hypercubes and Grids

**4**

**1**answer

### Increasing the chromatic number by “folding” two vertices of distance 2

**3**

**0**answers

### Reconstructing plane graphs from degree- and face-sequences

**4**

**2**answers

### How many vertices can a self-complementary graph have?

**2**

**1**answer

### Compactness of Hadwiger number

**0**

**0**answers

### Graph homomorphism from a high-girth graph to the sub-graph of a high-girth graph

**2**

**0**answers

### Distance-preserving graph contraction to a given set of vertices

**3**

**0**answers