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: | sage-8.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.