Skip to content

Problems · Vela Mathematics Program

Narrowed toopen ×chromatic number ×Clear all

Problem ledger

27 problemsGraph view
declared open · formalized · $500erdos:74
∀ {V : Type u} {G : SimpleGraph V} (A : G.Subgraph), (Erdos74.SimpleGraph.edgeDistancesToBipartite A).Nonempty
graph theorychromatic numbercyclesN/A2 sources
declared open · formalizederdos:75
True ↔ ∃ V G, G.chromaticCardinal = Cardinal.aleph 1 ∧ Cardinal.mk V = Cardinal.aleph 1 ∧ ∀ ε > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (H : G.Subgraph), H.verts.ncard = n → ∃ I, ↑I ⊆ H.verts ∧ G.IsIndepSet ↑I ∧ ↑I.card > ↑n ^ (1 - ε)
graph theorychromatic numberN/A3 sources
declared open · formalizederdos:108
True ↔ ∀ r ≥ 4, ∀ k ≥ 2, ∃ f, ∀ (V : Type u) (G : SimpleGraph V), Nonempty V → ↑f ≤ G.chromaticNumber → ∃ H, H.coe.girth ≥ r ∧ H.coe.chromaticNumber ≥ ↑k
graph theorychromatic numbercyclespossible2 sources
declared openerdos:111
Erdős problem 111
graph theorychromatic numberset theoryN/A
declared open · formalizederdos:130
For an infinite planar set in strong general position, how large can the chromatic and clique numbers of its positive-integer-distance graph be - in particular, can the chromatic number be infinite? Yes: there is such a set, no three collinear and no four concyclic, with infinite chromatic number.
graph theorychromatic numberN/A4 sources
declared open · formalized · $500erdos:593
Erdos Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system. The answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations. Problem #1177 on exact spectra is settled alongside it.
set theorygraph theoryhypergraphsN/A4 sources
declared open · $1000erdos:625
Erdős problem 625
graph theorychromatic numberN/A
declared openerdos:626
Erdős problem 626
graph theorychromatic numbercyclespossible
declared openerdos:627
Erdős problem 627
graph theorychromatic numberpossible
declared openerdos:629
Erdős problem 629
graph theorychromatic numberpossible2 sources
declared openerdos:640
Erdős problem 640
graph theorychromatic numberN/A
declared openerdos:704
Erdős problem 704
graph theorygeometrychromatic numberN/A
declared openerdos:706
Erdős problem 706
graph theorychromatic numberpossible
declared openerdos:738
Erdős problem 738
graph theorychromatic numberN/A
declared open · formalizederdos:740
True ↔ ∀ (V : Type u_1) (G : SimpleGraph V), Cardinal.aleph0 ≤ G.chromaticCardinal → ∀ (r : ℕ), ∃ H, H.coe.chromaticCardinal = G.chromaticCardinal ∧ Erdos740.NoShortOddCycle H.coe r
graph theorychromatic numberN/A2 sources
declared openerdos:761
Erdős problem 761
graph theorychromatic numberN/A
declared openerdos:836
Erdős problem 836
graph theoryhypergraphschromatic numberN/A2 sources
declared openerdos:917
Erdős problem 917
graph theorychromatic numberN/A
declared open · formalizederdos:918
True ↔ ∃ V G, Cardinal.mk V = Cardinal.aleph 2 ∧ G.chromaticCardinal = Cardinal.aleph 2 ∧ ∀ (W : Set V), Cardinal.mk ↑W = Cardinal.aleph 1 → (SimpleGraph.induce W G).chromaticCardinal ≤ Cardinal.aleph0
graph theorychromatic numberN/A2 sources
declared openerdos:919
Erdős problem 919
graph theorychromatic numberN/A
declared open · formalizederdos:944
True ↔ ∀ k ≥ 4, ∀ r ≥ 1, ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k r
graph theorychromatic numberN/A2 sources
declared openerdos:1032
Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?
graph theorychromatic numberpossible3 sources
declared open · formalizederdos:1068
True ↔ ∀ (V : Type) (G : SimpleGraph V), G.chromaticCardinal = Cardinal.aleph 1 → ∃ s, s.Countable ∧ (SimpleGraph.induce s G).InfinitelyConnected
graph theoryset theorychromatic numberN/A2 sources
declared open · formalizederdos:1104
∃ c₁, 0 < c₁ ∧ c₁ ≤ 1 ∧ ∀ᶠ (n : ℕ) in Filter.atTop, c₁ * √↑n / √(Real.log ↑n) ≤ ↑(Erdos1104.triangleFreeMaxChromatic n)
graph theorychromatic numberA2925282 sources
declared openerdos:1156
Erdős problem 1156
graph theorychromatic numberN/A
declared open · formalizederdos:1175
True ↔ ∀ (κ : Cardinal.{u_1}), Cardinal.aleph0 < κ → ∃ μ, ∀ (V : Type u_1) (G : SimpleGraph V), G.chromaticCardinal = μ → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ
set theorychromatic numberN/A2 sources
declared openerdos:1177
For a finite forbidden triple system GG, what exact uncountable chromatic cardinalities occur among GG-free triple systems, and how do those spectra interact? The revised manuscript answers the three exact-cardinal questions and claims a complete spectrum dichotomy.
set theorychromatic numberhypergraphsN/A3 sources