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.