ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G=(V,E)G=(V,E) be a finite loopless graph (multiple edges permitted). Two edges are adjacent if they share an endpoint.

A proper edge coloring of GG with color set CC is a map c ⁣:E→Cc\colon E\to C such that c(e)≠c(f)c(e)\neq c(f) whenever ee and ff are adjacent. The chromatic index χ′(G)\chi'(G) is the least integer kk for which there is a proper edge coloring of GG using a color set of size kk.

A list assignment for GG is a map LL assigning to each edge e∈Ee\in E a finite set L(e)L(e) of colors. A proper LL-edge-coloring of GG is a map c ⁣:E→⋃e∈EL(e)c\colon E\to\bigcup_{e\in E}L(e) with c(e)∈L(e)c(e)\in L(e) for every e∈Ee\in E and c(e)≠c(f)c(e)\neq c(f) for every pair of adjacent edges e,fe,f. For an integer k≥1k\ge 1, the graph GG is kk-edge-choosable if every list assignment LL with ∣L(e)∣≥k|L(e)|\ge k for all e∈Ee\in E admits a proper LL-edge-coloring. The list chromatic index ch⁡′(G)\operatorname{ch}'(G) is the least kk such that GG is kk-edge-choosable.

Then for every such graph GG,

ch⁡′(G)=χ′(G).\operatorname{ch}'(G)=\chi'(G).

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.