Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 8628
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.
47
votes
Generalizations of the four-color theorem
One of the most important generalizations of the four color theorem is Hadwiger's conjecture. The Hadwiger conjecture asserts that a graph without a $K_{r+1}$ minor is $r$-colorable. There is a furthe …
20
votes
3
answers
987
views
Does the hypergraph of subgroups determine a group?
A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if t …
- 48.9k
17
votes
1
answer
460
views
"Good" edge-colorings
Let $n >1$ be an integer, and suppose $G = (V,E)$ is a simple undirected graph with $V = \{1,\ldots,n\}$. For $v\in V$ set $N(v) = \{w\in V: \{v,w\} \in E\}$.
It is known by Vizing's theorem that the …
- 48.9k
15
votes
1
answer
745
views
Page-turning number of a graph
Motivation. As I was travelling in the UK, I used a physical copy of the "A-Z Road Atlas BRITAIN" for getting around. I was impressed that whenever I wanted to go from the map segment shown on page 23 …
- 48.9k
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\m …
- 48.9k
13
votes
1
answer
512
views
"Drinking number" of a graph
Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half dra …
- 48.9k
12
votes
4
answers
1k
views
Are at most $1/3$ vertices "kings"?
If $G=(V,E)$ is a finite, simple, undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and $\text{deg}(v)= |N(v)|$. We say a vertex $v\in V$ is a king if $\text{deg}(v) > \text{deg …
- 48.9k
12
votes
3
answers
1k
views
Non-isomorphic graphs with bijective graph homomorphisms in both directions between them
Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\ri …
- 48.9k
12
votes
4
answers
539
views
Optimal schedule for a soccer tournament
Motivation. This weekend, my children took part in a soccer tournament consisting of $n$ teams, each of which playing once against every other team. As there was only one soccer field, the schedule co …
- 48.9k
12
votes
1
answer
678
views
Graphs $G$ with $G \cong \text{Aut}(G)$
Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of graph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\va …
- 48.9k
10
votes
1
answer
3k
views
Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the...
This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the near …
- 48.9k
10
votes
1
answer
2k
views
Does the axiom of choice follow from the statement "Every simple undirected graph is either ...
Using the Well-Ordering Principle, which is equivalent to the Axiom of Choice, it can be proved that
(S): for every simple, undirected graph $G$, finite or infinite, either $G$ or its comple …
- 48.9k
10
votes
3
answers
1k
views
Is $\mathrm{Graph}$ cartesian-closed?
Let $\mathrm{Graph}$ be the category of simple, undirected graphs with graph homomorphisms. For any graphs $G, H$ we denote by $\text{Hom}(G, H)$ the set of graph homomorphisms $f:G\to H$. (Note that …
- 48.9k
10
votes
2
answers
264
views
Maximal in-degree in directed voting graph
Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about …
- 48.9k
10
votes
0
answers
254
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, doe …
- 48.9k