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
Deleting triangles in a graph
Given a graph $G$, the problem of determining the minimum size $\tau(G)$ of a set of edges $X$ such that $G-X$ is triangle-free is indeed NP-complete. This was proved by Yannakakis. Regarding bounds …
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
4
votes
Proofs of parity results via the Handshaking lemma
The following puzzle can be solved by the same technique. A mountain range is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for al …
- 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
Efficient Hamiltonian cycle algorithms for graph classes
One class of graphs for which many NP-hard problems (including finding a Hamiltonian cycle) are easy (linear-time) are graphs of bounded tree-width. Indeed, by Courcelle's theorem any problem which c …
- 4,713
10
votes
Number of matchings of even cycles
Here is a bijective proof.
Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect mat …
- 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
4
votes
Accepted
Size of forbidden minors for treewidth
Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, the relevant theorem is Theorem 5.9.
If $G$ is an obstruc …
- 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
17
votes
Accepted
Is every 1-million-connected graph rigid in 3D?
Update. The recent paper Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$ by Soma Villányi gives a positive answer to the question.
Old Answer. I think this is still an open problem, …
- 32.1k
3
votes
Minimally 2-vertex-connected graphs?
As the edited question mentions, Dirac did something similar, although minimality is with respect to edge deletion while connectivity is with respect to vertices (hence some confusion arose) The link …
- 32.1k
56
votes
21
answers
14k
views
Linear algebra proofs in combinatorics?
Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, …
- 5,822