Opened 3 years ago
Closed 3 years ago
#27079 closed defect (fixed)
acyclic_edge_coloring(Graph(3), k=None, value_only=True) should not be 2, should it?
Reported by:  mantepse  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Martin Rubey 
Report Upstream:  N/A  Work issues:  
Branch:  2996f7a (Commits, GitHub, GitLab)  Commit:  2996f7a3a05f6d788c80093257b3009d9d7ad82b 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (12)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
 Description modified (diff)
comment:3 Changed 3 years ago by
 Summary changed from acyclic_edge_coloring(Graph(3), value_only=True) should not be 2, should it? to acyclic_edge_coloring(Graph(3), k=None, value_only=True) should not be 2, should it?
Indeed, I made a mistake in the description of the ticket. I corrected it now, thank you!
comment:4 Changed 3 years ago by
 Branch set to public/27079_edgeless_graphs
 Commit set to 7fcd8ae3fc9d8b7146e59af45dd13f9e44a28fe2
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
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?
comment:6 Changed 3 years ago by
 Commit changed from 7fcd8ae3fc9d8b7146e59af45dd13f9e44a28fe2 to 0a9b292a92543e9c4f28c71c3ac9a48554ada2b7
Branch pushed to git repo; I updated commit sha1. New commits:
0a9b292  trac #27079: empty graph

comment:7 Changed 3 years ago by
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.
comment:8 Changed 3 years ago by
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
diff git a/src/sage/graphs/graph_coloring.py b/src/sage/graphs/graph_coloring.py index 9f0c6e47da..5b571a6eca 100644
a b def acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=Non 1546 1546 1547 1547 from sage.rings.integer import Integer 1548 1548 from sage.combinat.subset import Subsets 1549 from sage.plot.colors import rainbow 1549 1550 1550 1551 if not g.order() or not g.size(): 1551 1552 if value_only: 1552 1553 if k is None: 1553 1554 return 0 1554 elif k == 0:1555 if k == 0: 1555 1556 return 2 1556 else: 1557 return k 1557 return k 1558 1558 else: 1559 return {} if hex_colors else [] 1559 if k is None: 1560 return {} if hex_colors else [] 1561 if k == 0: 1562 k = 2 1563 return {c: [] for c in rainbow(k)} if hex_colors else [g]*k 1560 1564 1561 1565 if k is None: 1562 1566 k = max(g.degree()) … … def acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=Non 1577 1581 elif not k: 1578 1582 k = max(g.degree()) + 2 1579 1583 1580 from sage.plot.colors import rainbow1581 1582 1584 p = MixedIntegerLinearProgram(solver=solver)
comment:9 Changed 3 years ago by
 Commit changed from 0a9b292a92543e9c4f28c71c3ac9a48554ada2b7 to 2996f7a3a05f6d788c80093257b3009d9d7ad82b
Branch pushed to git repo; I updated commit sha1. New commits:
2996f7a  trac #27079: further improvements

comment:10 Changed 3 years ago by
I have almost followed your proposal.
comment:11 Changed 3 years ago by
 Reviewers set to Martin Rubey
 Status changed from needs_review to positive_review
comment:12 Changed 3 years ago by
 Branch changed from public/27079_edgeless_graphs to 2996f7a3a05f6d788c80093257b3009d9d7ad82b
 Resolution set to fixed
 Status changed from positive_review to closed
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:
But we can check that a coloring with 1 color exists
The current implementation makes it impossible to return 0. So tests for small cases must be added.