New answers tagged graph-theory
1
vote
Can a Feynman graph be an empty set?
Consolidating from comments:
The definitions given in the question are a bit unusual, so it is not straightforward to interpret them.
However, best as I understand the question, it is not about ...
- 3,065
2
votes
The max-clique chromatic number of a graph
Fedor Petrov, in a comment on my previous answer, asked whether there is a countable graph in which every maximal clique is infinite, and the hypergraph of maximal cliques has infinite chromatic ...
- 13.4k
2
votes
Accepted
The max-clique chromatic number of a graph
The answer is yes if infinite graphs are allowed.
Theorem. For any integer $n\ge3$ there is an infinite graph
$G=(V,E)$ such that $\chi_m(G)=\chi(G)=\aleph_0$, and every maximal clique of $G$ has ...
- 13.4k
4
votes
Minimal graphs with a prescribed number of spanning trees
The conjecture has been proved in Spanning trees and continued fractions by Swee Hong Chan, Alex Kontorovich and Igor Pak.
The summary of the proof due to the second author:
We reduce the graph ...
- 8,597
4
votes
The max-clique chromatic number of a graph
If $\chi(G)$ is finite, and all maximal cliques have size at least 3, you may take a graph coloring and unite two colors. This gives a proper coloring of the maximal cliques hypergraph with strictly ...
- 109k
5
votes
Accepted
Is a simply connected locally 2-connected complex a union of spheres and planes?
I checked: Bing's "house with two rooms" (see for instance here for a nice picture) is an example: It is a contractible but not collapsible finite 2-dimensional complex. Since it is ...
- 12.2k
1
vote
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
(I don't have enough reputation to comment).
There are generalizations of Ihara-Bass result for adjacency matrix $A$ with $A_{ij}$ being some real number(see this paper, p. 13 and further). But even ...
- 11
1
vote
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
I do not have a definitive answer, but some thoughts that are too long to go in a comment - I left the question open for a few days in case someone else knew more.
It seems to be the case that all ...
- 12.7k
3
votes
Forbidden minor characterization of polytope skeletons
For $d \geq 4$ what you describe are all graphs. The 1-skeleton of Cyclic polytopes is $K_n$ for $d\geq 4$.
7
votes
Accepted
Matrix-tree theorem for inverse matrices
There is a formula as a sum of forests, i.e., collections of trees, for arbitrary minors of any size and row/column selection, for arbitrary matrices. So it can be applied for the numerator and the ...
4
votes
Accepted
Is there a ternary Cayley graph on 27 vertices that is a non-complete core?
There are two such graphs on $27$ vertices, one with degree $12$ and one with degree $14$.
To get the degree $14$ example, just add $j+k$ to the connection set of your degree $12$ example.
Both of ...
- 12.7k
3
votes
Do triple-linked graphs exist?
I have since come across the following paper which seems to answer the question affirmatively in a very strong sense:
E. Flapan, B. Mellor, R. Naimi, "Intrinsic linking and knotting are ...
- 13.6k
2
votes
Accepted
Do triple-linked graphs exist?
Yes.
Theorem 1.
For every $k$ there exists $N=N(k)$ such that in every embedding of the complete tripartite graph $K_{N,N,N}$ into $\mathbb{R}^3$ there are $k$ disjoint pairwise linked triangles; in ...
- 6,101
Top 50 recent answers are included