**HUJI**Combinatorics Seminar

**When:**Monday May 3rd, 2021, at 10:30AM

**Where:**Sprinzak 28

**Live session:**https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=03278ccf-3d56-4125-b089-ad16005d68e2

**Speaker:**Eli Shamir (HUJI)

**Title:**List Coloring of Latin Graphs

**Abstract:**

For G(V,E) **list coloring** each vertex v has a **palette** P(V) of allowed colors it can get. It is harder than standard coloring and often max I(P(v)I is higher than chi(G). But it is amenable to stepwise coloring and validity proof by induction on IVI.

For the next step let

A(c)={v I c is in P'(v),the current palette) ; K(c)=some maximal independent set in A(c)

**Color K(c) by c ,delete it from V and c from P’(v). **Induction on IVI will prove success if for v in A(c)\K(c) the degree and P(v) .

decrease by the same amount.

Question is :how to to specify K(c) and **INV** -the invariant decease relation.

Consider this process for the family of simple[single] latin graphs [ SLG ] on nXn domain D, in which the edges form cliques on all rows and columns { or on similar double partitions of D to n sets of size n.}

This G is a line graph of a [complete] bipartite **graph H** with sides C and R of size n.

This G is known to **be perfect**:: for all induced subgraphs G’ **chi(G’) =max clique size of G’**.

**Dinitz problem is: **does this equality extend to list coloring number[the choice number]?

**Galvin** solved it for SLG; using stable matching algorithm on sets of lines **in H**; to define the kernels K(c) in A(c).

Our method connects a pair of maximal semi-matchings in the sides C and R of H by a **mirror map. **This pair "incarnate” to the same set K(c) of entries in D; and due to maximality the degrees of C- and R cliques attached to any v in A(c) \K(c) decrease by 1 and the same for P'(v). Thus the perfection of G is directly proved [on top of Dinitz ] while in Galvin proof it is complicated due to recourse to digraph, and using outdegree instead of degree for **INV **relation.

Next -the list coloring and perfection is proved for twins latin graphs**[TLG**]: two single SLGs load their edges on the same domain D. Here G is line graph of H which is not bipartite but 4-partite: Lines running top to bottom sides and left to right sides of a square.

The maps between the semi-matches heavily rely on a balanced indexing of the 2 sides C and R of H by a pair d,d’ in [p] ; e,e’ in [q] The additive groups of size p and q. This bypasses the adjoint map which arises when rows to columns are mapped using indexing by [n]. Here n=p.q but the case of prime n is obtained from n+1 by a subgraph of deficiency 1.