Suppose that a function on subsets of a finite set V satisfies the following three conditions.
Is there a polynomial-time (in |V|) algorithm that recognizes a function f having branch-width at most 3 (assuming that f is given by the oracle function such that a single query takes a unit time)?
Note: For 0, 1, and 2, there are simple algorithms.
A graph is called distance-balanced if for every edge uv the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Classify distance-balanced graphs among the generalized Petersen graphs.
Can you compute the crossing number of a graph efficiently in the case that (any reasonable) "width" parameter of the graph is bounded?
Alternatively, can you prove NP-completeness of crossing number for graphs with a fixed value of some "width" parameter? As the "width" parameter, one may substitute tree-width, clique-width, path-width, cutwidth, etc...
(This problem is based on the original question of Seese concerning crossing number and tree-width.)
If k is length of longest isometric cycle of G, is there a positive constant c so that treelength(G) < c*k?
For which graph classes is it easy to determine whether G has H as an isometric subgraph?
Find an efficient exact algorithm for determining whether G has H as an isometric subgraph.
If G is a graph, then its "square" G2 is the graph on the same set of vertices where two vertices in G2 are adjacent if they share a neighbor in G. By D(G) we denote the maximum degree of G.
Prove or disprove:
For any graph G, tw(G2)≤ O(tw(G) + D(G))