7
$\begingroup$

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

Should we merge them?

$\endgroup$
9
  • $\begingroup$ We discussed this a long time ago but didn't come to a solid conclusion. $\endgroup$
    – Gilles 'SO- stop being evil' Mod
    Commented Dec 12, 2018 at 7:52
  • $\begingroup$ I don't think they're synonymous, but people are bad at tagging. $\endgroup$
    – Raphael Mod
    Commented Dec 12, 2018 at 18:19
  • 1
    $\begingroup$ Can you give an example of the difference? $\endgroup$
    – Yuval Filmus
    Commented Dec 12, 2018 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 Mod
    Commented Dec 27, 2018 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 Mod
    Commented Dec 27, 2018 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
    Commented Dec 27, 2018 at 14:44
  • $\begingroup$ Based on the positive consensus here, I was about to do the merge... but I want to check if we have consensus on the direction of the merge. We're getting rid of graph-theory and keeping graphs? Do I have that right? $\endgroup$
    – D.W. Mod
    Commented Oct 17, 2019 at 21:46
  • $\begingroup$ I don't have strong feelings either way. Someone has to make this arbitrary decision, it might as well be you. $\endgroup$
    – Yuval Filmus
    Commented Oct 17, 2019 at 22:06
  • 1
    $\begingroup$ Done! I have merged them. $\endgroup$
    – D.W. Mod
    Commented Oct 20, 2019 at 18:54

2 Answers 2

Reset to default
5
$\begingroup$

+1

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.

$\endgroup$
2
$\begingroup$

+1

From Wikipedia,

... graph theory is the study of graphs, ...

I don't think there is any difference between "graphs" and "the study of graphs".

$\endgroup$

You must log in to answer this question.

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