8k views

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 ...

5k views

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 ...

4k views

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

776 views

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

258 views

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 ...

323 views

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 ...

375 views

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$, ...

128 views

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 ...

544 views

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 ...

162 views

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 ...

426 views

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 ...

911 views

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 ...

938 views

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 ...

3k views

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 ...

891 views
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, ...