JuliaGraphs / JuliaGraphs/Graphs.jl
Add Mycielskian construction
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
A hereditary family $\mathcal{G}$ of graphs is $\chi$-bounded with $\chi$-binding function $f: \mathbb{N} \to \mathbb{N}$ if $\chi(G) \leq f(\omega(G))$ for all $G$ in $\mathcal{G}$. A classical result of Erdős shows that the gap between the clique number and the chromatic number of a graph can be arbitrarily large. Multiple interesting research questions arise from this result. The most prominent one asks: when is a family of graphs $\chi$-bounded?
The most famous construction that yields a triangle-free graph with an arbitrary large chromatic number is the Mycielskian construction. Obviously, a consequence of this result is that not all graph families are $\chi$-bounded. The Mycielskian contruction is therefore often used as a counterexample in this field of study. Thus, it would make sense to include this graph family as a static construction in Graphs.jl (staticgraphs.jl) and the Grötzsch graph (3rd Mycielskian) (in small graphs.jl).
I'd like to implement both in Graphs.jl, if there is nothing against it.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Read the linked Mycielskian and Grötzsch graph descriptions, then inspect staticgraphs.jl and small graphs.jl to understand how static constructions are represented. Add both graph families in their respective files; done means the Mycielskian construction and the 3rd Mycielskian (Grötzsch graph) are available in Graphs.jl.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100