#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) Commit: 2996f7a3a05f6d788c80093257b3009d9d7ad82b
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (12)

comment:1 Changed 21 months ago by 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.

comment:2 Changed 21 months ago by mantepse

  • Description modified (diff)

comment:3 Changed 21 months ago by mantepse

  • 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 21 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/27079_edgeless_graphs
  • Commit set to 7fcd8ae3fc9d8b7146e59af45dd13f9e44a28fe2
  • Status changed from new to needs_review

This should fix the reported issue.


New commits:

7fcd8aetrac #27079: edgeless graph

comment:5 Changed 21 months ago by 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?

comment:6 Changed 21 months ago by git

  • Commit changed from 7fcd8ae3fc9d8b7146e59af45dd13f9e44a28fe2 to 0a9b292a92543e9c4f28c71c3ac9a48554ada2b7

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

0a9b292trac #27079: empty graph

comment:7 Changed 21 months ago by 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.

comment:8 Changed 21 months ago by 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

    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 
    15461546
    15471547    from sage.rings.integer import Integer
    15481548    from sage.combinat.subset import Subsets
     1549    from sage.plot.colors import rainbow
    15491550
    15501551    if not g.order() or not g.size():
    15511552        if value_only:
    15521553            if k is None:
    15531554                return 0
    1554             elif k == 0:
     1555            if k == 0:
    15551556                return 2
    1556             else:
    1557                 return k
     1557            return k
    15581558        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
    15601564
    15611565    if k is None:
    15621566        k = max(g.degree())
    def acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=Non 
    15771581    elif not k:
    15781582        k = max(g.degree()) + 2
    15791583
    1580     from sage.plot.colors import rainbow
    1581 
    15821584    p = MixedIntegerLinearProgram(solver=solver)

comment:9 Changed 21 months ago by git

  • Commit changed from 0a9b292a92543e9c4f28c71c3ac9a48554ada2b7 to 2996f7a3a05f6d788c80093257b3009d9d7ad82b

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

2996f7atrac #27079: further improvements

comment:10 Changed 21 months ago by dcoudert

I have almost followed your proposal.

comment:11 Changed 21 months ago by mantepse

  • Reviewers set to Martin Rubey
  • Status changed from needs_review to positive_review

comment:12 Changed 21 months ago by vbraun

  • Branch changed from public/27079_edgeless_graphs to 2996f7a3a05f6d788c80093257b3009d9d7ad82b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.