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

829 questions
1k views

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

A very specific case of Reed's Conjecture Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
972 views

1k views

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

Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
582 views

398 views

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

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
774 views

### Hamiltonian cycles and fundamental groups

I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing ...
409 views

### Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
304 views

### Is there a weak strong regularity lemma?

A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
229 views

### Fixed point property for simple undirected graphs

We say that a simple, undirected graph $G=(V,E)$ has the fixed point property (FPP) if for every graph homomorphism $f:G\to G$ there is a vertex $v\in V$ such that $f(v) = v$. If $G$ has the FPP, ...
137 views

### Cospectral mate of rhombic dodecahedron

I am wondering if the following pair of cospectral graphs was previously known. The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'): As far as I know, it was ...
168 views

### Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
541 views

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

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...
229 views

### Is there a Rado category?

The Rado graph appears to have a nice universality property (it contains all finite and all countably infinite graphs as induced subgraphs) and homogeinety property (any isomorphism between finite/...
488 views

### Abelian sandpile models

This question is about a popular probabilistic model on graphs studied in physics, mostly, for the standard lattice in ${\mathbb R}^n$ but also on other graphs (this model is of the same spirit as ...
431 views

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

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
151 views

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

In a short 1946 paper "On Hamiltonian Circuits", Tutte proved the famous result that an edge in a cubic graph lies in an even number of Hamilton circuits. He attributed the result to his friend CAB ...
223 views

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

Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent: 1) there exist a perfect matching in $G$; 2) there exist non-negative weights on edges such that the sum of ...
368 views

### Torus Graph Dynamics

Consider the torus graph, or the toroidal grid, which looks like (The graph's vertices are the bold dots). I will discuss only square torus graphs, where there is an equal number of vertices in a "...
217 views

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

Consider a graph $G$ with a particular node $i$ labeled as “infected”. Other nodes start uninfected, and will become infected over time according to the following process: To each edge of the graph, ...
143 views

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

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$. ...
804 views

### Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...
119 views

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

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring. Problem. Is it true that each biconnected graph possesses a distinguishing ...
349 views

### Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics. Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex \$v \in V \...