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

**3**answers

### Bijective operations on finite simple graphs

**6**

**1**answer

### Strongly rigid regular graphs

**-3**

**1**answer

### Maximum chromatic number of a $k$-regular graph [on hold]

**-4**

**1**answer

### Regular graph such that $2$ distinct vertices have same neighborhood set [on hold]

**0**

**1**answer

### Literature about most basic existence proofs in graph theory [closed]

**1**

**1**answer

### Literature on the controllability of networks under attack

**6**

**0**answers

### How sensitive are Neural Networks to weight change?

**0**

**0**answers

### How to prove the exact top degree of the polynomial coming from each Feynman diagram?

**11**

**1**answer

### To find a longer path with fixed endvertices in a graph satisfies the following property

**6**

**0**answers

### Is there a version of Weyl's law for graph Laplacians?

**2**

**0**answers

### Flat or linkless embeddings of graph with fixed projection

**-1**

**1**answer

### $2n$-regular graphs with maximal chromatic number

**2**

**1**answer

### Minimum dominating sets in tournaments

**-1**

**1**answer

### Version of Hall's marriage theorem in arbitrary finite graphs [closed]

**15**

**1**answer

### Chromatic numbers of infinite abelian Cayley graphs

**11**

**4**answers

### Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?

**1**

**0**answers

### Hypergraph partitioning and bipartite graph partitioning

**0**

**0**answers

### Hypergraph mapping's projection

**2**

**0**answers

### Total Coloring Conjecture for Cayley Graphs

**0**

**1**answer

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

**5**

**1**answer

### Finding a semi-sparse vertex in a grid

**2**

**0**answers

### Obtaining the reduced incidence algebra in QPA

**0**

**1**answer

### Average Edge-cost Optimality of MSTs

**1**

**0**answers

### Are there half-transitive convex polytopes?

**9**

**1**answer

### Origin of the banana graph

**0**

**0**answers

### Lower bound on the nonzero Laplacian eigenvalue with the smallest real part

**6**

**2**answers

### Do you know a faster algorithm to color planar graphs?

**4**

**1**answer

### Hamming representability of finite graphs

**1**

**1**answer

### On a theorem of Chetwynd and Hilton in Graphs

**0**

**1**answer

### Conjecture on representing graphs within $\{0,1\}^n$

**3**

**1**answer

### Induced minors of $\{0,1\}^\omega$

**2**

**1**answer

### H-generalized join graph

**0**

**1**answer

### Is there any solution that currently exists for the graph automorphism problem in the general case?

**1**

**1**answer

### Enumerating isomorphic subgraphs

**3**

**1**answer

### Generalized digraph homomorphisms and graph cores

**5**

**2**answers

### The number of Dyck paths of length $2n$ and height exactly $k$

**1**

**1**answer

### Bounds on degrees of minors obtained by edge contractions of regular graphs

**8**

**5**answers

### How to find central vertex in a graph?

**2**

**1**answer

### Is it true that centrality measures in SNA are indicative for most important vertices only?

**0**

**1**answer

### Finding a good transversal basis

**4**

**1**answer

### The existence of a specific kind of independent set in a connected graph satisfying the following property

**0**

**3**answers

### Is every graph an incomparability graph?

**5**

**1**answer

### Cut sets in 2-connected 3-regular graphs?

**3**

**1**answer

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

**0**

**1**answer

### Description of Linear Time Algorithm for TSP in Halin Graphs

**8**

**0**answers

### Colored weighted Graphs with only monochromatic perfect matchings

**0**

**0**answers

### Examples of Binary Functions that Yield Regular Graphs with Invertible Adjacency Matrix

**4**

**1**answer

### Applications of De-Bruijn Sequences in “Pure Mathematics”

**4**

**1**answer

### New edge coloring problem in graph theory

**2**

**1**answer