[sage-devel] Re: New algorithm for graph edge coloring

2022-12-04 Thread dmo...@deductivepress.ca
This is now trac ticket #34809 . On Tuesday, November 29, 2022 at 9:11:31 AM UTC-7 Matheus Maldonado wrote: > There are some other points I forgot to mention: > > Figuring out if the optimal edge coloring of a graph takes Delta or > Delta+1 colors is an NP

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-29 Thread Matheus Maldonado
There are some other points I forgot to mention: Figuring out if the optimal edge coloring of a graph takes Delta or Delta+1 colors is an NP-hard problem and can take exponential time. This is not what my algorithm does. It may return a Delta coloring, but in a non-deterministic way. What I su

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-29 Thread Matheus Maldonado
On Tuesday, 29 November 2022 at 05:05:50 UTC-3 David Coudert wrote: > FYI, the current Vizing algorithm is not well tested and the returned edge > coloring may have an empty set of colors > > sage: from sage.graphs.graph_coloring import edge_coloring > sage: G = graphs.PetersenGraph() > sage: e

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-29 Thread David Coudert
FYI, the current Vizing algorithm is not well tested and the returned edge coloring may have an empty set of colors sage: from sage.graphs.graph_coloring import edge_coloring sage: G = graphs.PetersenGraph() sage: edge_coloring(G, vizing=True) [[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)], [(0, 4),

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-28 Thread Matheus Maldonado
On Monday, 28 November 2022 at 03:48:18 UTC-3 dmo...@deductivepress.ca wrote: > I agree that this seems to be a good improvement. I think it should > replace the current "vizing" algorithm, instead of adding a new function to > the namespace. > > A minor issue is that (if I understand correc

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-27 Thread dmo...@deductivepress.ca
I agree that this seems to be a good improvement. I think it should replace the current "vizing" algorithm, instead of adding a new function to the namespace. A minor issue is that (if I understand correctly) the current vizing algorithm always gives a colouring with Delta + 1 colours. If tha

[sage-devel] Re: New algorithm for graph edge coloring

2022-11-27 Thread David Coudert
Feel free to open a ticket for this code. It's seems a good improvement. On Sunday, November 27, 2022 at 5:39:34 PM UTC+1 Matheus Maldonado wrote: > Hello everyone, > > I just developed a new function for coloring graph edges based on > this article: > https://www.sciencedirect.com/science/arti