All Questions
Tagged with conjectures graph-theory
13 questions
15
votes
3
answers
613
views
Maximum matching in a graph with no "shortcuts"
For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...
- 34.3k
11
votes
1
answer
866
views
Seeking proof of the Cuckoo Cycle Conjecture
Allow me to introduce the Cuckoo Cycle Proof of Work, and conclude with a closely related Conjecture about random graphs, which I hope someone can find a proof for.
Cuckoo Cycle is named after the ...
- 1,734
8
votes
1
answer
449
views
Does Vizing's conjecture hold for the infinite graphs?
In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. ...
7
votes
0
answers
557
views
Graphs with graphic imbalance sequences
Let $G$ be simple undirected graph and $e=uv\in E(G)$.
The imbalance of the edge $e$ is the value $imb(e)=|d(u)-d(v)|$.
Let $M_{G}$ denotes the imbalance sequence (or more correctly, multiset of ...
- 747
6
votes
0
answers
108
views
Localizing Bondy's metaconjecture on hamiltonicity
Definitions:
Let $G$ be a graph on $n$ vertices. $G$ is Hamiltonian provided $G$ has a cycle of length $n$. $G$ is pancyclic provided $G$ has a cycle of length $\ell$ for every $3 \leq \ell \leq n$.
...
- 399
5
votes
2
answers
391
views
Conjecture about minimal number of edge crossings in complete bipartite graphs
I am interested in the status of the conjecture about the minimum number of edge crossings $cr(K_{m,n})$ in a drawing of the complete bipartite graph $K_{m,n}$.
The Wikipedia article https://en....
- 125
4
votes
1
answer
246
views
Total coloring conjecture for Cayley graphs
The total coloring conjecture (TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
- 2,089
4
votes
1
answer
134
views
Common insights into hypothetical complexity of graph problems
I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. ...
- 2,993
3
votes
0
answers
410
views
Equivalence of the union-closed sets conjecture that is locally weaker of any use?
Let $F$ be a union-closed family. We call $F$ minimal if for every $x\in \cup(F)$ we find $S\in F$ such that $S\backslash \{x\} \in F$. It is sufficient to proof the union-closed sets conjecture for ...
- 696
2
votes
1
answer
402
views
Has the Total Coloring Conjecture been proved for complete graphs?
I have a question on the Total Coloring Conjecture in graph theory. This conjecture states that
$$\chi^"(G)\leq \Delta +2,$$
where $\Delta$ is the maximum degree of the graph and $\chi^"(G)$ denotes ...
- 4,195
1
vote
0
answers
158
views
Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$
After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...
- 1,451
0
votes
0
answers
118
views
Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point
In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
- 1,451
0
votes
0
answers
195
views
Dirac's theorem and the 1-factorization conjecture
Let $G=(V,E)$ be a simple, undirected graph. A matching is a subset $M\subseteq E$ such that all members of $M$ are pairwise disjoint; moreover we call $M$ perfect if $\bigcup M = V$.
The 1-...
- 48.9k