Knowing more about your graph class would be very helpful. I know Bill Cook and Stephan Held are doing some work on lower-bounding $\chi$ using LP duality and branch-and-bound. Basically they look for a lower bound on the fractional chromatic number by finding a reasonably good feasible solution for the dual LP, i.e. a fractional clique.

A fractional clique is just a non-negative vertex weighting on the graph so that no stable set has weight more than 1. The total weight of a fractional clique is a lower bound for the fractional chromatic number, and so is in turn a lower bound for the chromatic number.

Of course, even with only 560 vertices this will not necessarily get you very far in a short amount of time. You can do tricks to help yourself with the time cost. Obviously you can start by throwing away vertices with degree lower than the bound you're hoping for. You can also partition the vertices of the graph into dense subgraphs, then try to bound the chromatic number of these subgraphs individually. Doing this using my RNSC (restricted neighbourhood search clustering) algorithm, which was originally used to find clusters in biological networks, helped a little bit with what Cook and Held were doing, but not too much.

I'm copy-pasting an abstract from a talk that Bill Cook gave this winter, which includes a link to their colouring page:

DATE: Tuesday, February 9

SPEAKER: Bill Cook (Georgia Tech)

TITLE: Computing the chromatic number of graphs

ABSTRACT: It can be very difficult in practice to optimally color a graph. For
example, a set of randomly-generated test instances introduced by David Johnson
in 1989 remain unsolved, the smallest example having only 125 vertices. We
discuss the use of linear-programming methods to compute safe lower bounds on
the chromatic number. Our methods do not depend on the floating-point accuracy
of linear- programming software. This talk is based on joint work with Stephan
Held (University of Bonn). Computational results and computer codes are freely
available at site: http://code.google.com/p/exactcolors/