The firefighter problem has received a fair amount of attention recently, and is (somewhat surprisingly) NP-hard on trees of maximum degree 3. It is actually a fairly natural question, described as ...

Obviously if $f(\Delta)=2\Delta$ then the bound holds. However, I doubt this is what you meant. Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such ...

Every bridgeless cubic planar graph is 3-edge-colourable. (This is equivalent to 4CT, due to Tait.)

Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.

It seems not. Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further ...

Chvátal and Sbihi (Recognizing Claw-free Perfect Graphs, JCTB 44) described the atoms for the class of claw-free perfect graphs, a.k.a. quasi-line perfect graphs. This description was later refined ...

This is NP-complete; reduction from the question, "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?" Construct $G$ as follows. Take two copies of $H-e$, ...

The tree is binary and has depth $O(\log(n))$ and the properties that: for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent. for any node $v$, all descendants in the ...

You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$. It can be computed efficiently, and is an upper bound for the ...

I think you're using a confusing sign convention, but I'll stick with it. It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm ...

One springs to mind and is listed as a maximal subclass in ISGCI, which surprised me: perfect claw-free graphs (a.k.a. perfect quasi-line graphs). This was done by Minty for all claw-free graphs ...

This is obviously a comment and not an answer, but I don't have any reputation points here yet, so sorry about that. For non-bipartite cubic bridgeless graphs, there are exponentially many perfect ...

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute. In the formulation you give for the Ising model, we are trying to ...

Finding a maximum (or at least large) clique is often useful because it gives you a lower bound on the fractional chromatic number and chromatic number of the graph in question. Actually the maximum ...

You may find it useful to look into blocking and anti-blocking pairs of polyhedra. Say you have a packing problem. Then your feasible region $P$ is a corner polyhedron in the nonnegative orthant, ...

It might be useful to store the data in a graph of nodes corresponding to the Delaunay Triangulation of the geometric data points. Then if you wanted to query an area you could do so by starting with ...