List edge-coloring

Key takeaways

List edge-coloring belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect List edge-coloring to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of List edge-coloring from memory before moving on to harder problems.

Reference excerpt

In graph theory, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color. A graph G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring. In other words, when the list for each edge has length k, no matter which colors are put in each list, a color can be selected from each list so that G is properly colored. The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, ch'(G) of graph G is the least number k such that G is k-edge-choosable. It is conjectured that it always equals the chromatic index.

Properties Here χ′(G) is the chromatic index of G; and Kn,n, the complete bipartite graph with equal partite sets. Some properties of ch'(G):

ch ′ ⁡ ( G ) < 2 χ ′ ( G ) . {\displaystyle \operatorname {ch} '(G)<2\chi '(G).}

ch ′ ⁡ ( K n , n ) = n . {\displaystyle \operatorname {ch} '(K_{n,n})=n.} This is the Dinitz theorem, proven by Galvin (1995).

ch ′ ⁡ ( G ) < ( 1 + o ( 1 ) ) χ ′ ( G ) , {\displaystyle \operatorname {ch} '(G)<(1+o(1))\chi '(G),} i.e. the list chromatic index and the chromatic index agree asymptotically (Kahn 2000). For bipartite graphs, c h ′ ( G ) = χ ′ ( G ) {\displaystyle ch'(G)=\chi '(G)} . For every simple bipartite graph, c h ′ ( G ) = Δ {\displaystyle ch'(G)=\Delta } .

List coloring conjecture The most famous open problem about list edge-coloring is probably the list coloring conjecture.

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

This conjecture has a fuzzy origin; Jensen & Toft (1995) overview its history. The Dinitz conjecture, proven by Galvin (1995), is the special case of the list coloring conjecture for the complete bipartite graphs Kn,n.

References

Galvin, Fred (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory, Series B, 63: 153–158, doi:10.1006/jctb.1995.1011. Jensen, Tommy R.; Toft, Bjarne (1995), "12.20 List-Edge-Chromatic Numbers", Graph Coloring Problems, New York: Wiley-Interscience, pp. 201–202, ISBN 0-471-02865-7. Kahn, Jeff (2000), "Asymptotics of the list chromatic index for multigraphs", Random Structures & Algorithms, 17 (2): 117–156, doi:10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9

Illustrations

Worked examples

Example 1 — a first encounter with List edge-coloring

Start with the simplest possible case. Write down what List edge-coloring claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to List edge-coloring before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about List edge-coloring ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of List edge-coloring

In research: List edge-coloring appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses List edge-coloring in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: List edge-coloring is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph coloring, so understanding it makes those chapters shorter.
In everyday life: Look for List edge-coloring outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study List edge-coloring in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what List edge-coloring means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain List edge-coloring out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is List edge-coloring in simple terms?

In graph theory, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge.

Why does List edge-coloring matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study List edge-coloring?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on List edge-coloring.