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

**1**

**1**answer

### Existence of connected component with large boundary?

**3**

**1**answer

### For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

**9**

**0**answers

### Direct combinatorial link between Sperner's and Tucker's Lemma?

**0**

**0**answers

### Complexity of edge coloring of class 1 graphs

**2**

**0**answers

### Path-covering for vertex-transitive graphs

**1**

**0**answers

### Counting number of special subset of vertices in a tree

**1**

**0**answers

### Graphs with vanishing homology and behaviour of the suspension of that graphs

**4**

**0**answers

### Bandwidth of two-dimensional grid graphs

**-4**

**0**answers

### how to find out a node that is not reachable from other nodes in a list and then add an edge b/w that node and a random node in python [closed]

**-1**

**1**answer

### Effect of collapsing two vertices of distance $2$

**0**

**0**answers

### Clustering coefficient in a directed graph

**0**

**1**answer

### Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

**1**

**0**answers

### Finding minimum weight perfect matchings in sparse bipartite graphs

**7**

**1**answer

### Boundedness of total current in electrical network

**1**

**0**answers

### What is known about this generalization of planar dual?

**1**

**1**answer

### Cayley graphs do not have isolated maximal cliques

**11**

**2**answers

### Exponential decay of voltage potential difference

**1**

**0**answers

### What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?

**61**

**28**answers

### Proofs where higher dimension or cardinality actually enabled much simpler proof?

**0**

**0**answers

### Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution

**2**

**1**answer

### Critical probability for Erdos-Renyi digraphs to be strongly connected

**1**

**0**answers

### maximal k-partite subgraph in a complete multipartite graph

**1**

**1**answer

### Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

**3**

**0**answers

### Probability that a random multigraph is simple

**1**

**1**answer

### Explanation of a proof of an embedding lemma of Bollobas and Thomason

**7**

**0**answers

### Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

**2**

**0**answers

### Automated rewriting of string diagrams in symmetric monoidal categories

**2**

**0**answers

### eigenvectors of a graph Laplacian VS Fourier basis

**1**

**1**answer

### Max weighted matching where edge weight depends on the matching

**3**

**1**answer

### The effects of collapsing vs joining non-adjacent vertices on the chromatic number

**0**

**0**answers

### Finding weight minimal swap-free directed vertex covers

**2**

**0**answers

### Graphs which are built from complete graphs : Reference request

**2**

**0**answers

### The expected size of a subtree of any labelled rooted tree

**0**

**0**answers

### Lower bounds on the length of circuits, depending on the number of times it crosses itself

**1**

**0**answers

### Support of random closed walk in arbitrary graph

**0**

**0**answers

### Order-relational conditions for 4 points being in convex configuration

**1**

**0**answers

### Gromov-Hausdorff distance between graphs with edges as part of the space versus not part of the space

**0**

**1**answer

### Value (not position)- based sorting; reference request

**0**

**0**answers

### Expected number of directed cycle in a directed complete graph

**1**

**1**answer

### Outer automorphism group of $F(G)$

**0**

**0**answers

### Antimagic labelings to prove total coloring conjecture

**2**

**0**answers

### Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?

**1**

**1**answer

### Distance pairs in labeled directed graph

**7**

**1**answer

### Natural $\Pi_1$ sentence independent of PA

**11**

**2**answers

### Which curves and surfaces are realizable by linkages? references?

**3**

**1**answer

### Graph structure on $S_\omega$ induced by fixed points on compositions

**14**

**2**answers

### A tree with prime vertices

**4**

**1**answer

### “Total rainbow” trees

**1**

**0**answers

### Clustering number on ring lattice

**8**

**1**answer