JuliaGraphs / JuliaGraphs/Graphs.jl

Add Mycielskian construction

Open
#238 2 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.