An Experiment with Property-derived Invariants

We’ve coded a number of graph invariants and properties. One easy way to get more invariants is to use the characteristic functions of the properties we’ve already coded. That is, if P is a property then P_value is an invariant where P_value = 1 if a given object has property P and 0 otherwise.

So, for instance, the following upper bound conjectures for the chromatic number for a graph include invariants like “is_eulerian_value” which is 1 if the graph is eulerian and 0 otherwise. So the Conjecture 7, for instance, “chromatic_num(x) <= card_periphery(x)/is_eulerian_value(x)”, should be interpreted as “if graph G is eulerian then the chromatic number is no more than the cardinality of the periphery (the vertices of maximum eccentricity) and if graph G is not eulerian then the chromatic number is no more than the cardinality of the periphery divided by 0 (which Sage interprets as Infinity and the relation as True)”. Since the second part is trivially true, Sage’s conjecture is really about the special case where the graph is eulerian.

  1. chromatic_num(x) <= card_periphery(x) + 1
  2. chromatic_num(x) <= average_distance(x)/is_semi_symmetric_value(x). This conjecture should be interpreted: “If a graph is semi-symmetric then the chromatic number is less than average distance”. The program only knows two of these, the Gray graph and the Folkman graph, so this is a very bold conjecture.
  3. chromatic_num(x) <= maximum(clique_number(x), min_degree(x) + 1)
  4. chromatic_num(x) <= min_degree(x)/is_cartesian_product_value(x)
  5. chromatic_num(x) <= matching_number(x)/is_strongly_regular_value(x)
  6. chromatic_num(x) <= card_periphery(x)^card_center(x)
  7. chromatic_num(x) <= card_periphery(x)/is_eulerian_value(x)
  8. chromatic_num(x) <= card_periphery(x)/is_bipartite_value(x)
  9. chromatic_num(x) <= -is_cartesian_product_value(x) + wilf(x)
  10. chromatic_num(x) <= brooks(x) – is_semi_symmetric_value(x)
  11. chromatic_num(x) <= -is_cartesian_product_value(x) + szekeres_wilf(x)
  12. chromatic_num(x) <= number_of_triangles(x) + rank(x)
  13. chromatic_num(x) <= clique_number(x)/is_bipartite_value(x)
  14. chromatic_num(x) <= clique_number(x)^2 + 1
  15. chromatic_num(x) <= girth(x)^2/is_overfull_value(x)
  16. chromatic_num(x) <= brooks(x) + chi_equals_min_theory_value(x) – 1
  17. chromatic_num(x) <= number_of_triangles(x) + residue(x) + 1
  18. chromatic_num(x) <= (different_degrees(x) + 1)^clique_number(x)
  19. chromatic_num(x) <= has_lovasz_theta_equals_alpha_value(x)+szekeres_wilf(x)-1


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s