srg-edge-coloring
SageMath code relating to https://arxiv.org/abs/1810.06660
Science Score: 54.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
✓Academic publication links
Links to: arxiv.org -
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (7.1%) to scientific vocabulary
Last synced: 6 months ago
·
JSON representation
·
Repository
SageMath code relating to https://arxiv.org/abs/1810.06660
Basic Info
Statistics
- Stars: 0
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 0
Created over 5 years ago
· Last pushed almost 4 years ago
Metadata Files
Readme
Citation
README.txt
This repository contains SageMath code relating to the paper entitled ``The chromatic index
of strongly regular graphs'' by Sebastian M. Cioaba, Krystal Guo, Willem H. Haemers. A
preprint can be found at https://arxiv.org/abs/1810.06660
srgedgecol.sage contains a function which randomly attempts find a k-edge-coloring of a
k-regular graph on an even number of vertices, within a given number of attempts. If it
is successful, the algorithm returns True and the coloring. Otherwise, it outputs
False and the number of attempts. This file can be run within a SageMath terminal session
as follows:
sage: runfile srgedgecol.sage
sage: G = graphs.CoxeterGraph()
sage: class1test(G, 10)
A sample file containing graph6 strings of all 32,548 strongly regular graphs with
parameters (36,15,6,6), originally obtained (with different formatting) from Ted
Spence (http://www.maths.gla.ac.uk/~es/srgraphs.php). To check all graphs in a list of
k-regular graphs on an even number of vertices to see if they are k-edge-colorable, do
something like the following:
sage: f = file("36sg6.txt", "r")
sage: aa = f.readlines()
sage: f.close()
sage: grs = [Graph(it.strip("\n")) for it in aa]
sage: from sage.graphs.graph_coloring import edge_coloring
sage: results = []
sage: for it in range(now, len(grs)):
sage: results.append(edge_coloring(grs[it], value_only = true))
To do the same, but with the faster, greedy heuristic (does not always succeed even
when the graph is class 1), do the following:
sage: results = []
sage: for it in range(now, len(grs)):
sage: results.append(class1test(it,100))
For larger graphs, computing the edge chromatic number is time-consuming. For these
graphs, class1test can confirm those which are class 1
Owner
- Name: Krystal Guo
- Login: kguo-sagecode
- Kind: user
- Website: http://krystalguo.com/
- Twitter: guo_krystal
- Repositories: 1
- Profile: https://github.com/kguo-sagecode
I do research in algebraic graph theory. Sometimes I write code in SageMath for my research and teaching, which I would like to make freely available.
Citation (CITATION.cff)
cff-version: 1.0.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Guo"
given-names: "Krystal"
orcid: "https://orcid.org/0000-0001-8776-537X"
title: "kguo-sagecode/srg-edge-coloring: Determining if a k-regular graph is k-edge-colorable"
version: v1.0.0
doi: 10.5281/zenodo.4031224
date-released: 2012-09-30