## New answers tagged graph-theory

3
votes

### Real-world examples of unweighted directed graphs

It's been recognized that adjacency matrix approaches to forming a spectral graph theory is problematic. It's been rediscovered that Eckmann's Combinatorial Hodge theory removes the problems and gives ...

4
votes

### Real-world examples of unweighted directed graphs

Disclaimer: I am not an applied mathematician at all and I found this just via some basic Goolging. But the "Stanford Large Network Dataset Collection" (https://snap.stanford.edu/data/) ...

2
votes

### When are (Abelian) Cayley graphs also expanders?

For what it's worth, a stronger statement is possible. Suppose $(G_n)$ is a sequence of finite groups. Moreover, suppose that there is an integer $k$ such that for all $n$, the derived length of $...

1
vote

### Deciding homomorphic images of De Bruijn graphs

This is quite relevant to my article Local Loop Lemma.
I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph ...

18
votes

Accepted

### Can the Pythagorean Graph be finitely colored?

This paper shows that the chromatic number is infinite.
Indeed, Theorem 1.1 part (i) with $a=b=c=1$ is what you want.

3
votes

### Topology of directed graph $G$ with non-singular adjacency matrix

Well, if $V=\{1,\ldots,n\}$, $(a_{ij})_{1\leqslant i,j\leqslant n}$ is the adjacency matrix, and it is non-singular, then its determinant (considered as a sum over permutations) has a non-zero term $\...

3
votes

Accepted

### Topology of directed graph $G$ with non-singular adjacency matrix

There is an edge emanating from any vertex of $G$ because otherwise the corresponding row (or column, according to our convention for forming the adjacency matrix) would be zero. Label the vertices as ...

1
vote

### Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

It seems that the answer is negative.
A graph $G$ is a co-comparability graph if its complement is a comparability graph. The comparability graphs of posets of dimension 2 are exactly the ...

1
vote

### Complexity of maximum weight-sum matching for cycle graphs

With inspiration from the comments I arrived at the following idea:
the maximum weight matching on the cycle is converted to a maximum weight matching on a path that is generated by splitting a vertex,...

1
vote

### Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein.
...

0
votes

### Efficient Hamiltonian cycle algorithms for graph classes

Even though the Hamilton path problem is NP-hard, in practice it is usually easy. An efficient algorithm has been known for 50 years. It is "A Search Procedure for Hamilton Paths and Circuits.&...

0
votes

### Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

The most efficient exact algorithm for finding Hamilton paths and circuits is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850....

0
votes

### Interpreting positive semidefinite matrix as a graph

One characterization of semidefinite positive matrices among symetric matrices is that all their principal minors are positive.
The determinant of the adjacency matrix of a graph has a graph-theoritic ...

3
votes

### Why do we get a connected 2-regular graph?

The construction makes $U$ the Cayley graph associated to an abelian group $G$
and a pair $\pm g$ of elements of $G$.(*) In such a graph all the components
are cycles of the same length, namely the ...

6
votes

Accepted

### Chromatic number of the insert-and-shift graph on $S_n$

$\mathbf G_n$ contains the complete graph $K_n$. Consider the set of all permutations where the elements $1,\dots, n-1$ are in the usual order in the sense that $\sigma(1) < \dots < \sigma(n-1)$,...

4
votes

### What is this Ramsey problem?

A good reference is Radziszowski's article Small Ramsey Numbers, which gets updated as new results are proven. In particular, this refers to basically all known Ramsey style results. The ones you're ...

4
votes

### A question related to "Locally Sidorenko" type problem

If I understand your question correctly, you are asking if there is a sparse graph counting lemma assuming only that the graphon is within $o(p)$ to the density $p$ in cut norm; the Lovasz result ...

2
votes

Accepted

### Homology of independence complex after removing a vertex

There is a fairly standard splitting technique as suggested in the comment, although not necessarily using $v$.
Let $G$ be a graph and $v$ is a simplicial vertex. Let $w$ be any neighbor of $v$. Then ...

0
votes

### Isometric path cover number of the 2 dimensional grid graph

Assume you have $a$ increasing paths (where both coordinates non-strictly increase) and $b$ decreasing ones. We may assume that all of them start and finish at the vertices of the square.
Now perform ...

2
votes

Accepted

### Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph ...

Top 50 recent answers are included

#### Related Tags

graph-theory × 5162co.combinatorics × 2238

graph-colorings × 525

reference-request × 445

algorithms × 338

pr.probability × 280

spectral-graph-theory × 269

random-graphs × 205

extremal-graph-theory × 199

gr.group-theory × 192

computational-complexity × 190

discrete-geometry × 175

linear-algebra × 173

mg.metric-geometry × 137

matching-theory × 125

combinatorial-optimization × 123

trees × 105

set-theory × 103

infinite-combinatorics × 103

hypergraph × 99

bipartite-graphs × 99

hamiltonian-graphs × 97

matrices × 96

perfect-matchings × 96

algebraic-graph-theory × 89