List Coloring.pptx

List coloring, an intriguing extension of traditional graph coloring, introduces dynamic color assignment by associating each vertex with a list of permissible colors. The list chromatic number, denoted as χl(G), signifies the minimum colors needed to properly color a graph under list constraints. Brooks' Theorem characterizes when a graph is optimally list colorable. Algorithmic techniques, including greedy approaches and backtracking, are pivotal in solving list coloring problems. Applications span various domains such as resource allocation, wireless network frequency assignment, and register allocation. List coloring's link to the classic chromatic number, its variations, computational complexity, and ongoing developments highlight its versatile role in computer science and mathematics, making it a captivating and practical field of study and application.

1. List Coloring Submitted by: Amit Kumar 2019MT60744 Supervised by: Dr. Bhawani Sankar Panda, Professor Department of Mathematics

2. What is a proper colouring of a graph? Painting all the vertices of a graph with colors such that no two adjacent vertices have the same color is called the proper coloring. Example: Improper Coloring Proper colorings

3. What is chromatic number? Chromatic number of a graph or χ(G) is the minimum unique colors needed to provide a proper coloring of graph. χ(K 4,2 ) = 2 Chromatic number of Any bipartite graph is 2.

4. What is list colouring? For a graph G, a list coloring of G is a proper coloring of the vertices of G from color lists L(v) available at each vertex. Let A be a set of colors, let L(v) be some subset of A assigned to the vertex v for each vertex in G. A list coloring is a function f from v to L(v) such that f(v) ≠ f(u) for any two adjacent vertices u, v. A={1,2,3} A valid colouring f: v->L(v) is as follows: f(y 1 ) =1 f(x 1 )=3 f(x 2 )=2

5. K- choosable and List chromatic number We call a graph k-choosable if there exists a proper coloring for any list of k colors assigned to each vertex The list chromatic number (or choice number) of a graph G, denoted χ l (G), is the minimum k for which G is k-choosable Consider the example of K 4,2 , we know that that the chromatic number or χ(K 4,2 ) is 2. In fact χ of any bipartite graph is 2. What about χ l (K 4,2 )?

6. K- choosable and List chromatic number K 4,2 is not 2-choosable, here is a counter example: Consider the following 2-lists for each node: It is impossible to provide an appropriate coloring of the above graph, hence it is not 2 colorable.

7. K- choosable and List chromatic number From the previous example, we can get an intuition of the following result: χ(G)<= χ l (G) Since, if we assign {1,2,3,…, χ(G)-1} to each vertex, we know the graph is not colorable using the definition of χ(G). Also, χ(G)<= Δ (G) + 1, since all the vertices can be colored differently than the neighbors.

8. K- choosability of Trees. We know χ(T)= 2, so χ l (T)>=2. In fact χ l (T)=2. Proof: Let T be a tree, where each vertex v has |L(v)|=2, Let T’ be the tree obtained after removing all the leaves from T. T is colorable if T’ is colorable, Since for any leaf in T we can color it exactly different from its parent’s color in T’. Apply the same process on T’ again and again till we’re left with the root of the tree, Which is colourable.

9. K- choosability of certain Bipartite graphs For complete bipartite graphs G of the form K n^n,n , χ l (G) ≥ n + 1. Proof: Let G=XUY, |X|= n n , and |Y|=n. Let L( y i )={i 1 ,i 2 ,..,i n }, and let L(x i ) be one possible set formed by taking one color from each L( y i ). Then all possible sets will be covered in X with one color from each L( y i ). Now consider any possible coloring f of G. Then there exists an x i with L(x i )={f(y 1 ), f(y 2 ), f(y 3 ),… ,f( y n )}, (since all possible sets were covered), this vertex will hence be uncolorable.

10. K- choosability of certain Bipartite graphs For all complete bipartite graphs G=XUY of the form K n,n , where n= 2k-1 C k , χ l (G) ≥ k + 1 Say we use a total of 2k-1 colors, i.e. |A|=2k-1. Consider n unique subsets of A, of size K, assign each one of these subsets to n vertices in X and Y each. Notice: In coloring n vertices of X, we use at least k colors. Say we use k-1 colours out of 2k-1 not using rest k colors, then there exists a vertex in x with L(x) exactly equal to these k colors.(since all possible subsets are covered) There exists a vertex in Y, y such that L(y) is exactly these k colors.(all possible sets), hence this vertex will be not colorable.

11. K- choosability of planar graphs Proof: Suppose G is maximally planar (i.e. all bounded faces are triangles, and the outer face is a cycle C). We show that if G has two adjacent external vertices with different lists of size 1, all other external vertices have lists of size 3, and all internal vertices have lists of size 5, then G can be properly colored. Since adding edges to a graph cannot reduce its list chromatic number, it is sufficient to prove this claim for maximal G. We perform the proof using induction.

12. K- choosability of planar graphs Proof: Base case: If n = 3, then G is a triangle. Let V (G) = {v1, v2, v3}, and L(v1) = {1} and L(v2) = {2}. Then, since |L(v3)| = 3, there exists a color for v3 that is different from v1 and v2. Induction step: We consider graphs on > 3 vertices. Let C = v1v2v3...vpv1 be the external cycle of G. Suppose that v1 and vp have different color lists both of size 1. We consider two cases: Suppose G has a chord between vertices v i and v j in C. We consider the two smaller cycles C’ = v 1 v 2 ... v i v j ...v p v 1 and C’’ = v i v i+1 ... v j v i . We first apply our induction hypothesis to C’ and its interior. This provides a proper coloring where vi , vj are adjacent and differently colored. We then apply our induction hypothesis to C’’ and its interior. The resulting colorings give us a list coloring of G. If G is chordless ?

13. K- choosability of planar graphs Proof: If G is chordless : (say v 1 and v p are adjacent) Let {v 1 , u 1 , ..., u m , v 3 } be the neighborhood of v 2 . Since G is maximally planar, v 1 u 1 ...u m v 3 must form a path from v 1 to v 3 , since G is chordless , {u 1 , ..., u m } are all internal vertices of G. Consider G’=G-v 2 , Let v1 be colored with color c. Since |L(v2)| = 3, there exist two colors x, y ∈ |L(v2)| such that x ≠ c and y ≠ c. For all u i ∈ {u 1 , ..., u m }, let L’( u i ) = L( u i ) \ {x, y}. This is possible since all such vertices are internal and therefore have lists of size 5. Therefore, |L’( u i )| ≥ 3. Now apply induction to G’ , now only v 3 could be colored x or y, color v 2 differently.

14. Characterisation of Graphs with X l (G)=2 Theorem: G is 2-choosable if and only if the core of G(pruning leaves) lies in T={K 1 , C 2m+2 , Θ 2,2,2 m }. We call a graph G a Θ-graph if G consists of two vertices u and v with three vertex-disjoint paths between them.

15. Characterisation of Graphs with X l (G)=2 The proof for one way for K 1 is clear. Consider Θ 2,2,2 m Case 1: L(A 1 )=L(A 2 )=L(A 3 )=….=L(A 2m+1 )={ x,y }, simply colour them alternating and then colour of A 1 and A 2m+1 will be same, so B and D are colourable.

16. Characterisation of Graphs with X l (G)=2 Case 2: L(A i )≠L(A i+1 ) for some i , Tentatively choose x i ∈ A i -A i+1 , Now choose x i-1 ∈ A i-1 -{x i } , keep going till choosing x 1, now if A 2m+1 = { b,d } and {L(B),L(D)} ≠{{x 1 ,b},{x 1 ,d}}, then ∃ x ∈ A 2m+1 s.t L(B)-{x,x 1 } ≠ Φ and L(D)-{x,x 1 } ≠ Φ , then choose x for A 2m+1 , now keep going by choosing x 2m ∈ A 2m -{x}, till x i+1 =A i+1 -x i+2 . We know that x i+1 ≠x i , since x i ∈ A i -A i+1

17. Characterisation of Graphs with X l (G)=2 Case 2: L(A i )≠L(A i+1 ) for some i , If {L(B),L(D)} ={{x 1 ,b},{x 1 ,d}}, then go the other way, i.e take x i+1 ∈ A i+1 -A i , and x i+2 ∈ A i+2 -{x i+1 }, .. Till x 2m+1 ∈ A 2m+1 ={ b,d }, now let B and D be colored x 1, so choose a color for A 1 from A 1 -x 1 , keep going till we complete circle.

18. Characterisation of Graphs with X l (G)=2 Other side of the proof is done by exhausting all possibilities, by showing that either G is in T or else G contains a subgraph of the following type: An odd cycle. 2 node disjoint even cycles connected by a path. Two even cycles having exactly one node in common . Θ a , b , c where a≠2 and b≠2 . Θ 2,2, 2, 2 m+1 Then we prove the above 5 categories are not 2 choosable

19. Further Readings: Josep D´ıaz , Oznur Ya¸sar Diner, Maria Serna, and Oriol Serra. On list k- coloring ¨ convex bipartite graphs, 2020Josep D´ıaz , Oznur Ya¸sar Diner, Maria Serna, and Oriol Serra. On list k- coloring ¨ convex bipartite graphs, 2020. The above paper talks about polynomial time solving of List-k Coloring (Each list at vertex is a subset of {1,2,..k}) for convex bipartite graph. Future goals expanding the above result for circular convex bipartite graphs and studying cubic bipartite graphs.

20. References Abel Romer. List colorings. 2020. Paul Erdos , Arthur L Rubin, and Herbert Taylor. Choosability in graphs. Congr . Numer , 26(4):125–157, 1979. Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica , 12:125–134, 1992. Carsten Thomassen . Every planar graph is 5-choosable. Journal of Combinatorial Theory Series B, 62(1):180–181, 1994. Josep D´ıaz , Oznur Ya¸sar Diner, Maria Serna, and Oriol Serra. On list k- coloring ¨ convex bipartite graphs, 2020