2
$\begingroup$

1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts?

  • The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable,

  • The degree of each vertex, and

  • The number of paths of length $j$ in the graph for all $j \in \{1,...,n\}$.

Keep in mind that graph is not given (so in particular the neighbors of each vertex are not known).

2) What computations can be performed on a graph given in this manner that are more efficient than the corresponding computations on a general graph?

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ There is a lot of work on graphs with a given degree sequence, at least as far back as the Erdős-Gallai theorem. Path sequences have been less studied, perhaps just limited to a 2015 paper by Bakalarski and Zygadło. I'm not aware of any work that combines both degree and path sequences. $\endgroup$
    – András Salamon
    Commented Mar 7, 2017 at 13:20
  • 1
    $\begingroup$ One of these things is not like the others. "The fact that the graph is planar" is something that constrains the graph, and might lead to algorithms more efficient than for arbitrary graphs. "The degree of each vertex" is a piece of information that every graph has, so unless you tell us something more about what these degrees are, you can't use it to differentiate your graphs from arbitrary graphs. Same for "the number of paths". $\endgroup$
    – David Eppstein
    Commented Mar 11, 2017 at 8:11
  • $\begingroup$ You're right, I just wanted to make clear that not given information about the neighbors of the nodes. And that information is different than the general graph in a given situation. In addition I want to understand is there anything smart we can say from those given (and by combination of them), when we specifically deal with a planar graph. $\endgroup$
    – user1387682
    Commented Mar 11, 2017 at 11:13

0

Reset to default