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.

Component: graph theory

Author: David Coudert

Branch/Commit: 2996f7a

Reviewer: Martin Rubey

Issue created by migration from https://trac.sagemath.org/ticket/27079

[dcoudert]

comment:1

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]

comment:3

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

[dcoudert]

comment:4

This should fix the reported issue.

---

New commits:

7fcd8ae

trac #27079: edgeless graph

[dcoudert]

Commit: 7fcd8ae

[dcoudert]

Author: David Coudert

[dcoudert]

Branch: public/27079_edgeless_graphs

[mantepse]

comment:5

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?

[sagetrac-git]

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

0a9b292

trac #27079: empty graph

[sagetrac-git]

Changed commit from 7fcd8ae to 0a9b292

[dcoudert]

comment:7

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]

comment:8

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:

diff --git a/src/sage/graphs/graph_coloring.py b/src/sage/graphs/graph_coloring.py
index 9f0c6e47da..5b571a6eca 100644
--- a/src/sage/graphs/graph_coloring.py
+++ b/src/sage/graphs/graph_coloring.py
@@ -1546,17 +1546,21 @@ def acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=Non
 
     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,8 +1581,6 @@ def acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=Non
     elif not k:
         k = max(g.degree()) + 2
 
-    from sage.plot.colors import rainbow
-
     p = MixedIntegerLinearProgram(solver=solver)

[sagetrac-git]

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

2996f7a

trac #27079: further improvements

[sagetrac-git]

Changed commit from 0a9b292 to 2996f7a

[dcoudert]

comment:10

I have almost followed your proposal.

[mantepse]

Reviewer: Martin Rubey

[vbraun]

Changed branch from public/27079_edgeless_graphs to 2996f7a