The tags and seem to cover much of the same ground.

Should we merge them?

  • $\begingroup$ We discussed this a long time ago but didn't come to a solid conclusion. $\endgroup$ – Gilles Dec 12 '18 at 7:52
  • $\begingroup$ I don't think they're synonymous, but people are bad at tagging. $\endgroup$ – Raphael Dec 12 '18 at 18:19
  • 1
    $\begingroup$ Can you give an example of the difference? $\endgroup$ – Yuval Filmus Dec 12 '18 at 18:31
  • $\begingroup$ Off the top of my head, two types of questions come to mind: 1) complexity-theory+graphs such as "Is this problem similar to Vertex Cover also NP-complete?".You'd ask a complexity theorist about that, not a graph theorist. 2) algorithms+graphs/modelling+graphs -- if it's about modelling a domain problem using graphs and then solving the problem using textbook algorithms, you don't delve into graph theory per se. You're using graphs as a tool. (Of course, this is a question of semantics, and yes, there are overlapping areas of expertise.) $\endgroup$ – Raphael Dec 27 '18 at 14:40
  • $\begingroup$ For me, graph theory is about the structural properties of graphs; a usual theorem is not bothered with algorithms or computational problems. $\endgroup$ – Raphael Dec 27 '18 at 14:43
  • 1
    $\begingroup$ Your two examples are both appropriate for the graphs tag. My conclusion is that questions on graph theory just don’t belong here. Questions such as the number of leaves in a complete binary tree (hardly deep graph theory as well; more like discrete math) are more suitable for Mathematics. Perhaps we should add a graph algorithms tag? $\endgroup$ – Yuval Filmus Dec 27 '18 at 14:44


I would say applications of graphs in CS do not fall in under graph theory as a mathematical field (research area), e.g. all the A* questions should be labeled graph.

On the other hand, questions regarding graph classes and their complexity (recognition, modification, operations etc.), as well as classical problems like chromatic number etc., should possibly be graph-theory.

That said, the distinction is rarely interesting here at cs.sx.

Therefore I vote yes: merge.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .