simple_graph_wild_number
def
The wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
Statement
noncomputable def simple_graph_wild_number {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) : ℕ
- Defined in
- arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2 (definition of the wild number wld_γ(G)).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
- Used by 26
- simple_graph_wild_number_le_of_is_color_connectingThe wild number is at most the size of any colour-connecting set.
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
- quadripartite_max_wild_number_eq_of_boundsThe maximum wild number equals 2n + 1 as soon as every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1 and some…
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- wild_odd_sharpness_of_weighted_cubic_costAt any positive odd complete-graph order n>=3, for any minimum proper coloring and any finite family of rooted floor(n/3)-block partitions…
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_number_complete_graph_two_coloring_rangeLet n ≥ 4. Every (surjective) 2-edge-colouring of K_n has wild number at most n − 2, and every integer 0 ≤ k ≤ n − 2 is the wild number of…
- wild_number_complete_thirteen_fourteen_eq_nine_or_tenFor n=13 or n=14, every minimum proper edge coloring of K_n has wild number either 9 or 10.
- simple_graph_wild_number_le_card_edge_finsetThe wild number of a finite connected edge-coloured graph is at most its number of edges.
- wild_number_complete_three_min_proper_coloring_eqFor every minimum proper edge colouring of K_3, the wild number is 2 = ⌊4⌈3/2⌉/3⌋: the case n = 3 of the conjecture in Sec. 6.
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_bipartite_min_proper_coloringLet 2 ≤ m ≤ n. For every proper edge colouring of the complete bipartite graph K_{m,n} with n colours (these are exactly its minimum…
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- wild_no_closed_union_of_blocksIf every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of…
- simple_graph_wild_number_attainedFor any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
- quadripartite_exists_wild_number_eq_of_upper_exclusionIf every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1, and some colouring has no colour-connecting set of at…
- wild_number_complete_graph_large_odd_multiple_three_eqFor every odd integer q>=100001, every natural number k equal to the chromatic number of the line graph of the complete graph K_(3q), and…
- wild_number_complete_graph_le_sub_oneFor every n ≥ 1 and every edge colouring γ of K_n, wld_γ(K_n) ≤ n − 1 (a spanning star is colour-connecting).
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- wild_number_complete_graph_formula_iff_odd_ordersThe wild-number sharpness conjecture for minimum proper colorings of every complete graph of order at least three is equivalent to its…
- wild_odd_sharpness_of_adaptive_cubic_momentsFor any minimum proper coloring at odd order n>=3 and any finite family of rooted partitions into floor(n/3) blocks of size at least…
- wild_number_complete_graph_upper_sub_four_add_parityFor every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c…
- wild_number_complete_even_eq_of_preceding_oddFor odd n>=3, if every proper n-coloring of K_n has the conjectured sharp wild number, then every minimum proper coloring of K_(n+1) has…
- quadripartite_max_wild_numberThe maximum wild number of the complete equipartite graph K_{n,n,n,n} over all proper edge colorings using exactly 3n colors.
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
Lean source view module on GitHub
/-- The wild number `wld_γ(G)`: the least size of a finite colour-connecting set (0 if there is none, which cannot happen for a finite connected graph). -/ noncomputable def simple_graph_wild_number {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) : ℕ := sInf {k | ∃ W : Finset (Sym2 V), W.card = k ∧ simple_graph_is_color_connecting G γ ↑W}