Skip to content

Add Mycielskian construction #238

Closed
Closed
@pgrepds

Description

@pgrepds

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions