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

**42**

**0**answers

### Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

**31**

**0**answers

### 3-colorings of the unit distance graph of $\Bbb R^3$

**24**

**0**answers

### Non-linear expanders?

**23**

**0**answers

### Planar minor graphs

**21**

**0**answers

### How much of the plane is 4-colorable?

**21**

**0**answers

### Zero curves of Tutte Polynomials?

**20**

**0**answers

### Is the Poset of Graphs Automorphism-free?

**18**

**0**answers

### Simpler proofs of certain Ramsey numbers

**18**

**0**answers

### Reference request: Parallel processor theorem of William Thurston

**16**

**0**answers

### Straight-line drawing of regular polyhedra

**16**

**0**answers

### Maximum automorphism group for a 3-connected cubic graph

**15**

**0**answers

### Is every k-edge-connected graph also k-trail-ordered?

**15**

**0**answers

### Optimal Monotone Families for the Discrete Isoperimetric Inequality

**14**

**0**answers

### Monotone embedding of complete binary tree in hypercube

**14**

**0**answers

### A Conjecture About Directed Graphs that are the Union of Two Trees

**13**

**0**answers

### Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

**13**

**0**answers

### A new lower bound for the chromatic number of a graph?

**13**

**0**answers

### $\epsilon$-nets with respect to the cut norm

**13**

**0**answers

### How much must deleting a spanning tree reduce edge-connectivity?

**12**

**0**answers

### The number of labeled pairs of edge disjoint trees and related questions

**12**

**0**answers

### The threshold for a perfect matching in a random subgraph of a regular bipartite graph?

**12**

**0**answers

### Approximation of the effective resistance on Cayley graph

**12**

**0**answers

### A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?

**12**

**0**answers

### Matroids with prescribed independent sets

**12**

**0**answers

### Finding a chromatic polynomial by polynomial fitting

**11**

**0**answers

### Quantitatively characterizing the failure of the converse of Dirac's theorem

**11**

**0**answers

### Is there a term for this graph subset?

**11**

**0**answers

### The Universal Labeling of graph

**11**

**0**answers

### How many n/2-cycles can a cubic graph have

**11**

**0**answers

### Colouring a graph whose edge set is a special union of cliques

**11**

**0**answers

### Hamiltonian cycles and fundamental groups

**11**

**0**answers

### Reconstruction Conjecture and Partial 2-trees

**10**

**0**answers

### Is there a weak strong regularity lemma?

**10**

**0**answers

### Fixed point property for simple undirected graphs

**10**

**0**answers

### Cospectral mate of rhombic dodecahedron

**10**

**0**answers

### Asymptotics of subgraph densities in graphons

**10**

**0**answers

### Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

**10**

**0**answers

### Is there a Rado category?

**10**

**0**answers

### Abelian sandpile models

**10**

**0**answers

### Has the technique of “sprinkling” been used in studying random matrices?

**9**

**0**answers

### What was Smith's proof of Smith's theorem on Hamilton cycles in cubic graphs?

**9**

**0**answers

### Fractional Matching version of Hall's Marriage theorem

**9**

**0**answers

### Torus Graph Dynamics

**9**

**0**answers

### Among regular graphs, do cliques have the highest infection rate?

**9**

**0**answers

### Cycles of length $2^n - 2$ in the De Bruijn graph

**9**

**0**answers

### Shortest path in Cayley graphs

**8**

**0**answers

### Minimal number of colours in distinguishing colouring of biconnected graphs

**8**

**0**answers

### Colored weighted Graphs with only monochromatic perfect matchings

**8**

**0**answers

### Two-player independent set game

**8**

**0**answers