bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 5 years, 1 month |
seen | Mar 31 at 22:30 | |
stats | profile views | 1,299 |
I am interested in graph theory and combinatorial optimization.
Apr 21 |
awarded | Favorite Question |
Mar 12 |
awarded | Yearling |
Mar 5 |
comment |
Linear intersection number and coloring (not chromatic) number
What happens if you replace the colouring number with the minimum degree $+1$, or the maximum degree $+1$, or the chromatic number? |
Feb 12 |
comment |
Chromatic number of graphs of tangent closed balls
A clarification: Choose the sphere $S$ to be smallest, and subject to that choose it to be extreme. I claim without proof that if a sphere kisses 12 others of equal or greater radius, then all 13 spheres have equal radius. Furthermore the sphere kissed by 12 others has its centre in the convex hull of the other 12 centres, and therefore is not extreme (of these 13 spheres) in any direction. |
Oct 31 |
awarded | Nice Answer |
Oct 16 |
comment |
Is a rigid cycle a chordal graph?
No to the second question, as exhibited by a graph on five vertices and eight edges with minimum degree 3. |
Jul 2 |
awarded | Curious |
Mar 12 |
awarded | Yearling |
Feb 6 |
comment |
Combinatorial Proof of Weak Perfect Graph Theorem.
Thanks Petr, updated the link. |
Feb 6 |
revised |
Combinatorial Proof of Weak Perfect Graph Theorem.
updated link |
Jan 8 |
comment |
How dense is the set of asymmetric graphs?
Is there a simple justification for your first sentence? |
Dec 6 |
comment |
Expected Value for a Connected Graph
It's easier to think about this in the equivalent model of giving each vertex a uniform random real in $[0,1]$. |
Nov 9 |
awarded | Good Question |
Oct 1 |
answered | Does the notion of graphs with vertex multiplicity exist? |
Jul 29 |
comment |
Hitting all cycles with three disjoint vertex sets
Even any graph containing $K_4$ fails. |
Jun 25 |
awarded | Tumbleweed |
May 21 |
comment |
Removing edges from Erdős–Rényi graph to make two nodes disconnected
You seem to be saying that if $c = \ln n$, then the maximum degree is going to be at most $2 \ln n / \ln \ln n$. I guess that's not the case? |
Apr 6 |
comment |
The probability distribution for vertex degree in a unit disc graph generated from random points on a plane
If you use an arbitrarily large plane, or even better, a sphere or torus, shouldn't the degree of a vertex just be Poisson-distributed? I don't really understand the second paragraph, so maybe it could use some clarification. Colourings of random geometric graphs has been studied quite a lot, including by user RJK, who will probably come by in the near future with a more intelligent response. |
Apr 5 |
comment |
Clique number of a $k$th power of a graph in terms of maximum degree?
Yes; they are related but not equivalent problems, because you could have vertices that are not in your clique, but help to connect vertices. I think the numbers should be close but not equal. (Aside from this question, I have found a better way to solve the problem I was working on.) |
Apr 3 |
revised |
Clique number of a $k$th power of a graph in terms of maximum degree?
added 151 characters in body |