Skip to main content
MathOverflow
Emil's user avatar
Emil's user avatar
Emil's user avatar
Emil
  • Member for 15 years, 1 month
  • London
Profile Activity

88 Actions

All Accepts Posts Badges Comments Revisions Reviews Suggestions
revised
Bound on the number of unlabeled cographs on n vertices
edited body
answered
Bound on the number of unlabeled cographs on n vertices
comment
Degree Sequences and Graph Enumeration
I don't understand the use of the term "recreational math". This seems to be a perfectly good graph theory question.
comment
Efficient way to count Hamiltonian paths in a grid graph for a given pair of vertices
Then answer is sometimes zero. Color the vertices like a chessboard. If there are an odd number of vertices you can't start and end on a white vertex.
awarded
 Popular Question
comment
Simple proof that these graphs are perfect
Wikipedia page is not bad: en.wikipedia.org/wiki/Cograph
comment
Cover time of weighted graphs
So the question now seems to be: does the conditions on the weights given in the first paragraph cause the cover time to be $O(n^2\log n)$, rather than merely $O(n^3)$?
answered
What is the relationship between "translation" and time complexity?
comment
Examples of self-centered graphs (with large radius)
Any vertex transitive graph.
comment
Is this measure related to treewidth?
(I know how to get it. It will just make things easier for everyone.)
comment
Is this measure related to treewidth?
Could you give a hyperlink to the arxiv paper?
comment
Problems known to be in both NP and coNP, but not known to be in P
So, presumably you are taking a definition of NP that includes things that are not decision problems? Or can you formulate integer factorization as a decision problem?
comment
Decision problem restricted to inputs that satisfy some necessary condition.
@shreevasta: Well Garey and Johnson stated all their problems like "INPUT: A graph G" etc. It is the normal way to state decision problems.
revised
Decision problem restricted to inputs that satisfy some necessary condition.
Added what I think is an answer
comment
Decision problem restricted to inputs that satisfy some necessary condition.
@shreevatsa: Ah, I think I see your point now.
revised
Decision problem restricted to inputs that satisfy some necessary condition.
removed comment at the end
comment
Decision problem restricted to inputs that satisfy some necessary condition.
@Rune: Thanks for modifying your answer. However, I believe I am defining a language: the language consists of strings that represent graphs that satisfy NC and are 3-colorable.
comment
Decision problem restricted to inputs that satisfy some necessary condition.
OK, so I can phrase Problem 2 as: "Decide if the input string represents a graph that satisfies NC and is 3-colorable."
comment
Decision problem restricted to inputs that satisfy some necessary condition.
Well a decision problem is just one with a yes/no answer, surely? Consider the following problem: Let G be a planar graph. Decide if G is 3-colorable. Is this a promise problem?
comment
Colourings of Graphs with extra conditions
"NP-complete" should be changed to "NP-hard".