Reputation
1,251
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
13 15
Newest
 Yearling
Impact
~105k people reached

  • 0 posts edited
  • 0 helpful flags
  • 97 votes cast
Oct
5
comment Prof. Murty's B. Sc. Thesis
I would do two things. First, I would call the library and see if they are even remotely willing to loan it. Second, I would change the title of this to mention Carleton University, so it might attract more useful attention.
Oct
2
comment Compute number vertex disjoint cycles in graph surrounding a face
I don't understand why you don't just say that the closest cycle to $t$ is $t$ itself. Or are you now dropping the assumption that the graph is 2-connected?
Oct
2
answered Optimization over permutation?
Sep
30
answered Strengthening the Induction Hypothesis
Sep
19
comment Value of “of course” in the mathematical literature
I think anybody who has graded undergraduate analysis assignments has said that at least once.
Sep
19
comment Smallest non-isomorphic strongly regular graphs
Thanks for the clarification, David. Do you know if they are indeed the smallest, as they seem to be?
Sep
19
answered Smallest non-isomorphic strongly regular graphs
Sep
19
comment Bounds on strong vertex colourings of regular hypergraphs?
As you probably realize, this is equivalent to colouring the graph that you get by replacing the hyperedges with cliques. Doing this gives you an upper bound of $k(\omega-1)+1$ if the hypergraph has maximum edge size $\omega$, by Brooks' Theorem. That's a pretty lousy bound, though, and I imagine you can do better.
Sep
16
comment What introductory book on Graph Theory would you recommend?
I was starting to think nobody would mention it!
Sep
7
comment Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
Good question; it is known to hold, without the round-up. Reed never published the result in a paper but it's in Graph Colouring and the Probabilistic Method (with Molloy), in the chapter on hard-core distributions (Chapter 23 I think). (It wouldn't let me comment twice in a row, so I deleted the old comment to add: ) A proof of a stronger result, noted by McDiarmid, appears in Section 2.2 of my thesis, which is here: columbia.edu/~ak3074/papers/phdthesis.pdf
Sep
7
awarded  Nice Question
Sep
6
comment Covering of a graph via independent sets
In that case I would consider how to ask the question in terms of hypergraphs and ask a question in this context. I'm confident somebody will know a better bound than $\Delta+1$. See, for example, this conjecture: garden.irmacs.sfu.ca/?q=op/a_generalization_of_vizings_theorem
Sep
6
revised Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
removed latex from title
Sep
6
awarded  Student
Sep
6
asked Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
Sep
4
answered Covering of a graph via independent sets
Sep
2
answered What are your favorite instructional counterexamples?
Sep
2
comment Lower bounds for chromatic number of a graph
By the way, you mention the Kneser graph. This is one graph class that can be used as a nasty example showing that the chromatic number is not necessarily upper-bounded by any function of the fractional chromatic number, meaning that in the worst case, the fractional chromatic number will give you a really lousy approximation.
Sep
2
answered Lower bounds for chromatic number of a graph
Sep
2
awarded  Supporter