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 2233
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
Characterizing the family of maximal cliques of a cograph
Here is a proof of Conjecture 1.
Proof. We prove the contrapositive. Suppose that $G$ is not a cograph. Then $G$ has an induced subgraph $H$ such that $H \simeq P_4$. Let $V(H)=\{1,2,3,4\}$ and …
- 32.1k
5
votes
Accepted
Approximation of Hamiltonian cycles
Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP.
Proof. Let $G$ be an instance of the Travelling Salesman Problem (TS …
- 32.1k
3
votes
Accepted
Bounds on lengths of intervals in bounded-degree interval graphs
Yes, we may take the function to be $2\Delta$.
Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum d …
- 32.1k
3
votes
Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,...
Here are some upper and lower bounds.
The paper On the chromatic number of some flip graphs proves that the chromatic number of $G_k$ is at most $4k-4$.
Therefore, in every proper colouring of $G_k$ t …
- 32.1k
6
votes
Accepted
Double cover the edges of a complete graph by smaller complete graphs
This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(v,k,t,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$- …
- 32.1k
5
votes
Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgra...
Yes, this is true. See my paper Subgraph densities in a surface with Gwenaël Joret and David Wood. We prove that for every $s \geq 5$, the number of $s$-cliques in a graph of Euler genus $g$ is at mo …
- 32.1k
8
votes
Accepted
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3...
No, this is false even in the planar case. Let $G=W_n$ be a wheel graph with $n \geq 6$. Deleting any edge of the outercycle yields a fan graph, which is not $3$-connected. On the other hand, contr …
- 32.1k
4
votes
Accepted
Does every graph admit an embedding such that identically-colored edges do not cross?
As requested by Jukka Kohonen, I'll turn my comment into an answer.
The answer is in general no. If such an embedding exists, then the red subgraph and blue subgraph are both planar. However, every …
- 32.1k
8
votes
Accepted
Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$
With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. The required embedding $f$ is easy to define. …
- 32.1k
11
votes
Accepted
Random sample of spanning trees
One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree o …
- 32.1k
6
votes
Accepted
Do longest paths in 4-connected graphs intersect?
According to Gallai’s question and constructions of almost hypotraceable graphs
by Wiener and Zamfirescu, this is an open problem (see the beginning of Section 4). Note that a graph is $G$ hypotrace …
- 32.1k
5
votes
Accepted
Sharp upper bound of the number of edges for graphs of thickness two
There is no such graph on $11$ vertices, but for all $n \geq 12$, there exists a thickness-$2$ graph with $6n-12$ edges. Both these results were proved by Boswell and Simpson in Edge-disjoint maximal …
- 32.1k
2
votes
Clique number of $k$-critical graphs
For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and …
- 32.1k
3
votes
Accepted
Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$
This follows from Proposition 2.1 of the paper Many $T$ copies in $H$-free graphs by Alon and Shikhelman.
Theorem (Alon and Shikelman)
Let $T$ be a fixed graph with $t$ vertices. Then $ex(n,T,H)=\Ome …
- 32.1k
2
votes
Ramsey-Kuratowski numbers
Here are some bounds that I can extract from the dynamic survey Small Ramsey Numbers by Stanisław Radziszowski. Recall that for two graphs $G$ and $H$, $R(G,H)$ is the smallest integer $n$ such that e …
- 32.1k