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

**0**

**0**answers

### Distance between colored rooted graphs

**3**

**0**answers

### Bayesian Networks and Polytree

**11**

**1**answer

### When is the poset of acyclic orientations of a graph a lattice?

**3**

**1**answer

### Martingales and intersection of random walks

**1**

**0**answers

### Beck-Fiala Discrepency Type Results for Arbitrary Graph Labelings

**0**

**1**answer

### Elusive groups and vertex-transitive graphs

**2**

**0**answers

### The graph polynomial of the Total Graph of a Graph

**2**

**0**answers

### Mod $2$ of $\#PM(G)$ for arbitrary G?

**1**

**1**answer

### Embedding a graph in $\mathbb{R}^3$ with partial geometric information

**2**

**1**answer

### Characterization of nilpotent adjacency matrices [closed]

**5**

**0**answers

### Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?

**3**

**1**answer

### Induced subgraphs of $\text{Exp}(G, K_2)$

**0**

**0**answers

### Random graphs - multiple giant components

**2**

**0**answers

### Expander graphs with many 4-cycles

**5**

**1**answer

### Do the Odd Cycles of a Graph Define a Matroid?

**4**

**1**answer

### The list chromatic number of some special toroidal grid graphs

**-1**

**0**answers

### Correlated tree interval and existence of unary subtree

**2**

**2**answers

### What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?

**7**

**0**answers

### Correspondence between matrix multiplication and a graph operation of Lovasz

**3**

**0**answers

### Polynomial Graph Isomorphism from Star System Reconstruction?

**1**

**0**answers

### A regular independence induced graph in a $\Delta+1$ coloring

**3**

**1**answer

### Asymptotic formula for the number of connected graphs

**7**

**1**answer

### Understanding Gillman's proof of the Chernoff bound for expander graphs

**2**

**1**answer

### Proving a theorem on coloring a peculiar graph

**4**

**1**answer

### Hamiltonian paths on the space of graphs

**0**

**1**answer

### Latent Dirichlet allocation and properties of digamma function

**12**

**0**answers

### Is there an algorithm to compute a Belyi map for the Riemann surface?

**3**

**1**answer

### Strong chromatic index of some cubic graphs

**2**

**0**answers

### Calculating Minimum Spanning Trees in Very Big Graphs

**2**

**0**answers

### Complexity of weighted fractional edge coloring

**1**

**0**answers

### Planar graphs with perfect matching count in linear time?

**5**

**1**answer

### For what graph does the following algebraic property hold?

**1**

**1**answer

### Bookthickness of covering space

**7**

**1**answer

### Co-spectral fractional isomorphic graphs with different Laplacian spectrum

**0**

**1**answer

### A vertex transitive graph has a near perfect/ matching missing an independent set of vertices

**1**

**1**answer

### Shortest path on graphs

**2**

**0**answers

### Can entropy of a network be written as a polynomial?

**1**

**0**answers

### Sufficient Condition for the Existence of Vertex Disjoint Shortest Paths

**1**

**1**answer

### Finding an element of the homology group of a graph which is everywhere nonzero

**0**

**1**answer

### Highly asymmetric regular graph

**5**

**1**answer

### Existence of regular factors in dense graphs

**1**

**0**answers

### Finding fundamental Kempe-locking configurations

**3**

**1**answer

### Equitable edge coloring of graphs

**5**

**0**answers

### Normal colorings of bridgeless cubic graphs

**0**

**0**answers

### Helly vs Strong p-Helly Property of Hypergraphs

**1**

**0**answers

### Bounds on chromatic number when maximum degree is large

**2**

**1**answer

### Chromatic number of the linear graph on $[\omega]^\omega$

**1**

**1**answer

### Clarifications regarding conformability in graph colorings

**1**

**0**answers

### A simple case of a strong version of the Berge-Fulkerson conjecture

**1**

**0**answers