ChromaticCliqueGap
The chromatic number less the clique number.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St001793via LabeledGraph✓ChromaticCliqueGap(graph)The chromatic number less the clique number.Typed signatures
| Type | Package | Applies |
|---|---|---|
(labeled_graph) -> number | combinatorics | always |
Details
- Defined over
LabeledGraphas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
LabeledGraphand nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer. - FindStat's St001793, which is 0 on a weakly perfect graph. The graph with no vertices gives 0.
Definition
Epsil, as the implementation runs it.
on LabeledGraph, over _x
0 if _x[1] == 0 else Apply((n: integer) => Apply((edges: list<list<integer>>) => Apply(
(inside: list<integer>) => Apply(
(totals: list<integer>) => Apply(
(within: list<integer>) => Min(Map(Function(k if Max(Sum(Map(Function((1 if (n -
totals[m + 1]) %
2 ==
0 else -1) *
within[m + 1] ^
k, m), Range(0, 2 ^ n -
1))), 0) >
0 else n, k), Range(1, n))),
Apply(
(a_init: list<integer>) => Fold((a: list<integer>, k) => Apply(
(a_next: list<integer>) => a_next,
Map(Function(a[m + 1] +
a[m -
2 ^
(k - 1) +
1] if m %
2 ^ k >=
2 ^
(k - 1) else a[m + 1], m), Range(0, 2 ^ n -
1)),
), a_init, Range(1, n)),
Map(Function(1 if inside[m + 1] ==
0 else 0, m), Range(0, 2 ^ n -
1)),
),
) -
Max(Map(Function((1 if 2 *
inside[m + 1] ==
totals[m + 1] *
(totals[m + 1] -
1) else 0) *
totals[m + 1], m), Range(0, 2 ^ n -
1))),
Map(
Function(Max(Sum(Map(Function(1 if m %
2 ^ v >=
2 ^
(v - 1) else 0, v), Range(1, n))), 0), m),
Range(0, 2 ^ n -
1),
),
),
Map(
Function(Max(Sum(Map(Function((1 if m %
2 ^ e[1] >=
2 ^
(e[1] - 1) else 0) *
(1 if m %
2 ^ e[2] >=
2 ^
(e[2] - 1) else 0), e), edges)), 0), m),
Range(0, 2 ^ n -
1),
),
), _x[2]), _x[1])Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |