Skip to main content
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
Search options not deleted user 17798

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.

3 votes
2 answers
2k views

Proving that every strongly connected tournament T on at least 4 vertices contains distinct ...

I have a two part question: Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected …
2 votes

Does a strong digraph always admit a vertex that lies on some path between $\Theta(n^2)$ pai...

I don't have an answer, but I do have an idea for how a proof could go. I would make this a comment, but it is too long. (i) Prove that every 2-strongly connected digraph (i.e. remains strongly conne …
Louis D's user avatar
  • 1,701
4 votes
Accepted

Is König's Property for graphs inheritable from finite subgraphs?

(Just making my comment an answer as suggested.) If every finite subgraph of $G$ satisfies Kőnig's Property, then $G$ has no odd cycles and is thus bipartite. Aharoni (König's Duality Theorem For Infi …
LSpice's user avatar
  • 12.9k
1 vote

Graph $G$ such that removing an edge leaves $G$ "unchanged"

How about a graph $G=(V,E)$ consisting of infinitely many isolated vertices and infinitely many disjoint edges. Like the random graph it has the property that for all $e\in E$, $G\simeq (V, E\setminu …
Louis D's user avatar
  • 1,701
3 votes

Induced subgraphs of the almost-disjointness graph

My first thought for the case where $|V|\leq \aleph_0$ is that surely the Rado graph can be constructed as an induced subgraph of $([\omega]^{\omega}, E)$ (since the Rado graph contains a copy of ever …
Louis D's user avatar
  • 1,701
1 vote

Pairs of vertices with high degree difference

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post, the proof becomes even simpler and it shows that $$ …
Louis D's user avatar
  • 1,701
1 vote

Directed version of this lemma

Regarding your Lemma 1.1, see Lemma 4.4 in Ben-Eliezer, Ido; Krivelevich, Michael; Sudakov, Benny, The size Ramsey number of a directed path, J. Comb. Theory, Ser. B 102, No. 3, 743-755 (2012). ZBL124 …
Louis D's user avatar
  • 1,701
6 votes
1 answer
194 views

Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three co...

Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color …
4 votes
1 answer
267 views

Dominating sets in subtournaments of the Paley tournament

For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices. Is i …
1 vote

Proving that every strongly connected tournament T on at least 4 vertices contains distinct ...

After reading relep's answer I revisited the problem and came up with a different fairly simple proof for Question 1, but before I get to that, I recently found that this problem has a long history al …
Louis D's user avatar
  • 1,701
5 votes

What are efficient pooling designs for RT-PCR tests?

This isn't a full answer, but too long for a comment. I suppose it comes closest to trying to answer Question 3 or the general question of whether the hypercube design can be improved. Definition Giv …
Louis D's user avatar
  • 1,701
4 votes
1 answer
133 views

Replacing maximum degree with degeneracy in Brooks' theorem

This is related to a previous question that I asked. The degeneracy of a graph $G$, denoted $\mathrm{degen}(G)$, is given by $\max\{\delta(H): H\subseteq G\}$. It is well known that for all graphs $G …
3 votes
1 answer
292 views

Perfect matchings in infinite regular bipartite graphs

This question was motivated by a discussion here and is related to a previous question here. Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a bipart …
8 votes
1 answer
162 views

Replacing maximum degree with degeneracy in Reed's conjecture

Reed's conjecture says that $\chi(G)\leq \lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$. One can think of $\lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$ as the (rounded-up) average of the trivial lower …
4 votes
2 answers
252 views

Relationship between minimum vertex cover and matching width

Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$). Question: Is $\ …

15 30 50 per page