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.
2
votes
Accepted
Graph with finite chromatic number but infinite total chromatic number
Yes there is: consider the complete bipartite graph $K_{\omega,\omega}$, which has chromatic number 2, but every total coloring requires infinitely many colors.
- 48.9k
0
votes
1
answer
649
views
Sizes of maximum matchings in a finite, simple, undirected graph
Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a matching $M\subseteq E$ is a maximum matching if for all $e\in (E\setminus M)$ the set $M\cup\{e\}$ is not a matching any more.
Maxi …
- 48.9k
0
votes
2
answers
188
views
"Nice" and "nasty" partitions in graphs
Let $G=(V,E)$ be a simple, undirected graph, that is $V$ is a set and $E \subseteq [V]^2 = \{\{v,w\}: v,w \in V \land v\neq w\}$.
For $v\in V$ and $S\subseteq V$ we set $$N(v,S) = \{w\in S: \{v,w\} \ …
- 48.9k
2
votes
1
answer
154
views
Maximum and minimum diameter of categorical graph product
Let $G_i$ be connected finite simple undirected graphs with diameter $d_i$ for $i=1,2$. Assume that $G_1\times G_2$ is connected. (Here $G_1\times G_2$ denotes the categorical product.)
In terms of $ …
- 48.9k
0
votes
1
answer
134
views
Different graphs with the same open neighborhood hypergraph
For any set $X$ we let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Let $G=(V,E)$ be a simple, undirected graph. Its open neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a …
- 48.9k
-2
votes
1
answer
147
views
Graphs such that contracting an edge decreases the chromatic number [closed]
Let $G = (V,E)$ be a finite, simple, undirected, connected graph, such that contracting an edge reduces the chromatic number. Does this imply that $G$ is complete?
- 48.9k
0
votes
1
answer
138
views
Cycle-intersecting subsets
Let $G=(V,E)$ be a finite, simple, undirected graph. We call $D\subseteq V$ cycle-intersecting if for every simple cycle $C\subseteq V$ we have $C\cap D \neq \emptyset$.
Is there a graph $G$ such tha …
- 48.9k
2
votes
0
answers
141
views
Tree-chromatic number and Hadwiger number
Let $G=(V,E)$ be a finite, simple, undirected graph. For any set $X$ we set $[X]^2 := \big\{\{x,y\}: x\neq y \in X\big\}$. If $T$ is a tree, then a map $W: V(T)\to {\cal P}(V(G))$ is called a tree-dec …
- 48.9k
-2
votes
1
answer
559
views
Degrees and common neighbors
For any simple, finite, undirected graph $G=(V,E)$ and $v\in V$ let $N(v) = \{w\in V:\{v,w\}\in E\}$.
Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex …
- 48.9k
1
vote
0
answers
47
views
Infinite graphs with number of common neighbors given for each pair of vertices
This is a follow-up to this question.
For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. If $G=(V,E)$ is a simple undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in …
- 48.9k
-3
votes
1
answer
70
views
Hamiltonian path in countable connected graph such that $\text{deg}(v)=\omega$ for all $v$ [closed]
Is there a countable connected graph $G=(\omega, E)$ such that $\text{deg}(v)=\omega$ for all $v\in\omega$, but there is no Hamiltonian path in $G$?
- 48.9k
-3
votes
1
answer
365
views
Connected homogeneous graphs [closed]
Let's call a simple, undirected graph $G=(V,E)$ homogeneous if for every $v,w\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(v)=w$.
It is clear that every finite homogeneous g …
- 48.9k
0
votes
1
answer
377
views
Total chromatic number and total clique number
Let $G=(V,E)$ be a finite, simple, unconnected graph. We define the total graph $T(G)$ of $G$ as follows:
$V(T(G)) = (V\times\{0\}) \cup (E\times\{1\})$,
$E(T(G)) = E_v \cup E_e \cup E_{v+e}$, where …
- 48.9k
1
vote
1
answer
130
views
Hadwiger number of total graph
Let $G=(V,E)$ be a finite, simple, undirected graph, and let $T(G)$ be its total graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Is there an ex …
- 48.9k
1
vote
1
answer
58
views
Regularization of arbitrary graphs
Let $G=(V,E)$ be a finite, simple, undirected graph. Let $\Delta(G)$ be the maximal degree of $G$. Is there a finite graph $G'=(V', E')$ with the following properties?
$V\subseteq V'$,
$E \subseteq …
- 48.9k