acyclic_edge_coloring(Graph(3), k=None, value_only=True) should not be 2, should it?

[mantepse]

I think that the correct value for

acyclic_edge_coloring(Graph(3), k=None, value_only=True)

should be 0, since there is nothing to color.

[dcoudert]

As documented, this method computes by default a coloring of G into \Delta(G) + 2 colors. So the result you get is at least consistent with the documentation.

For the same reason, we get the following:

sage: acyclic_edge_coloring(graphs.PathGraph(2), value_only=True)
3

But we can check that a coloring with 1 color exists

sage: acyclic_edge_coloring(graphs.PathGraph(2), k=1, value_only=True)
1

The current implementation makes it impossible to return 0. So tests for small cases must be added.

[mantepse]

Indeed, I made a mistake in the description of the ticket. I corrected it now, thank you!

[dcoudert]

This should fix the reported issue.

---

New commits:

​7fcd8ae

trac #27079: edgeless graph

[mantepse]

Looks good, thank you! I think it would also be good to change the behaviour of the parameter k slightly, perhaps using k=-1 as default? But not in this ticket!

Finally, I am not sure: should the empty graph also be allowed as input?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0a9b292

trac #27079: empty graph

[dcoudert]

Right, the empty graph was leading to an error. This is now fixed.

I agree that change in default behavior, if done, should be in a specific ticket.

[mantepse]

I am very sorry, but I have to ask:

The documentation currently says:

    - ``k`` -- integer; the number of colors to use.

      - If ``k > 0``, computes an acyclic edge coloring using `k` colors.

      - If ``k = 0`` (default), computes a coloring of `G` into `\Delta(G) + 2`
        colors, which is the conjectured general bound.

Apparently, when k is larger than the acyclic chromatic index of G, the function still returns a list of k graphs, some simply do not contain any edges.

Here is a proposal:

src/sage/graphs/graph_coloring.py

@@ -1546 +1546 @@
 
     from sage.rings.integer import Integer
     from sage.combinat.subset import Subsets
+    from sage.plot.colors import rainbow
 
     if not g.order() or not g.size():
         if value_only:
             if k is None:
                 return 0
-            elif k == 0:
+            if k == 0:
                 return 2
-            else:
-                return k
+            return k
         else:
-            return {} if hex_colors else []
+            if k is None:
+                return {} if hex_colors else []
+            if k == 0:
+                k = 2
+            return {c: [] for c in rainbow(k)} if hex_colors else [g]*k
 
     if k is None:
         k = max(g.degree())
@@ -1577 +1581 @@
     elif not k:
         k = max(g.degree()) + 2
 
-    from sage.plot.colors import rainbow
-
     p = MixedIntegerLinearProgram(solver=solver)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2996f7a

trac #27079: further improvements

[dcoudert]

I have almost followed your proposal.