[Nauty] Efficient workflow for filtering when using a transformation and pickg

[Stephen Hartke]

Hello everyone,

I have been using the wonderful nauty library and its included generating
and filtering programs for many years now.  The recent(-ish) inclusion of
the chromatic number in pickg has been especially useful.

I have a question about workflow using these tools.  I'm hoping that
members of this mailing list might have insights into how to make my
workflow more efficient.

I have recently been studying variants of graph coloring that can be
modeled by standard vertex coloring on a transformed graph.  An example is
"square coloring", which is just vertex coloring the square of a graph
(here, the square of G is a graph H with the same vertex set as G, and
vertices of H are adjacent if and only the vertices have distance at most 2
in G).  When generating data, I usually:
1) Use geng or another tool to generate graphs in an appropriate family,
for example, triangle-free graphs of max degree 4.
2) Apply the transformation, for example, the square of the graph.
3) Use pickg to filter out graphs with given values, say chromatic number
at least 10.  This corresponds to the original graph having square
chromatic number at least 10.

The problem with this approach is that I want to have the actual graphs
with the high square chromatic number, not their transformation.  In many
cases, it is not easy to invert the transformation.

I have gotten around this problem by using a bash script to apply the
transformation and pickg individually to each graph coming out of the
generation step.  The bash script knows the original graph and can output
it if pickg (or countg) accepts the transformed graph.

The difficulty with this approach is there are separate invocations for
each individual graph, and this generates a lot of overhead.  Is there a
smarter way to go about this, using the capability to pipe streams of
graphs between the tools?  It seems that a custom transformation could be
implemented within pickg (I currently have it implemented in a standalone
program), but it seems the output would still be the transformation, not
the original graph.

Thanks for any suggestions!
Stephen Hartke
University of Colorado Denver, USA