erdos-gyarfas
Program to validate Erdős–Gyárfás conjecture on graphs without any induced copies of P_k, for various values of k.
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 (6.0%) to scientific vocabulary
Repository
Program to validate Erdős–Gyárfás conjecture on graphs without any induced copies of P_k, for various values of k.
Basic Info
- Host: GitHub
- Owner: rbsandeep
- License: mit
- Language: C++
- Default Branch: main
- Size: 371 KB
Statistics
- Stars: 1
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
Erdős-Gyárfás conjecture on graphs without long induced paths
Here you can see an implementation of an algorithm to validate Erdős–Gyárfás conjecture on P_k-free graphs (graphs without any induced copies of a path on k vertices): every graph with minimum degree at least 3 has a cycle with length a power of 2. The algorithm can be found at this link: http://arxiv.org/abs/2410.22842
To prove that the conjecture is true for P_t-free graphs: run the program with a command line argument k, for 3 <= k <= t. If there is a counterexample of the required kind, the program will print the details.
Steps to compile:
make clean && make
Usage: ./out/a.out <k>
The above steps will build the serial implementation. For cilk based parallel implementation, please see the branch cilk.
Contributors: Anand Hegde, R. B. Sandeep, and P. Shashank.
Owner
- Login: rbsandeep
- Kind: user
- Repositories: 1
- Profile: https://github.com/rbsandeep
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: Hegde
given-names: Anand Shripad
- family-names: Sandeep
given-names: R. B.
- family-names: Shashank
given-names: P.
title: "Verifier for Erdős–Gyárfás conjecture on P_k-free graphs"
version: 2.0
date-released: 2024-10-28
GitHub Events
Total
- Watch event: 3
- Delete event: 7
- Issue comment event: 1
- Public event: 1
- Push event: 30
- Pull request event: 2
- Create event: 10
Last Year
- Watch event: 3
- Delete event: 7
- Issue comment event: 1
- Public event: 1
- Push event: 30
- Pull request event: 2
- Create event: 10
Issues and Pull Requests
Last synced: 10 months ago
All Time
- Total issues: 0
- Total pull requests: 1
- Average time to close issues: N/A
- Average time to close pull requests: about 1 month
- Total issue authors: 0
- Total pull request authors: 1
- Average comments per issue: 0
- Average comments per pull request: 1.0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 1
- Average time to close issues: N/A
- Average time to close pull requests: about 1 month
- Issue authors: 0
- Pull request authors: 1
- Average comments per issue: 0
- Average comments per pull request: 1.0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
Pull Request Authors
- AnandShegde (1)