Font Size: a A A

Planar Graphs Without 3-,7-,and 8-cycles Are DP-3-colorable

Posted on:2020-08-08Degree:MasterType:Thesis
Country:ChinaCandidate:X L LiFull Text:PDF
GTID:2370330578952309Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors.DP-coloring(also known as correspondence coloring)as a generalization of list coloring was introduced recently by Dvorak and Postle.(2017).The.main differe.nce betwe.en DP-coloring and list coloring is that it changes the vertex u in the graph G to Lu = {u} x L(u),where L(u)is the color set of u?and then finds any matching Muv between Lu and Lv.Dvorak and Postle used this notion proved that every planar graph without cycles of lengths from 4 to 8 is 3-choosable,solving a long-standing conjecture of Borodin.Since then much attention was drawn on this new coloring.Dvorak and Postle also noted that Thomassen's proofs for choosability can be used to show XDp(G)?5 if G is a planar graph,and XDp(G)?3 if G is a planar graph with no 3-cycles and 4-cycles.From this point of view,the research on DP-coloring is based on the study of choosability.In this paper,we prove that every planar graph G without 3-,7-,and 8-cycles is DP-3-colorable,which generalized the result of Dvorak,Lidicky,Skrekovski,who proved that every planar graph without 3-.7-and 8-cycles is 3-choosable.
Keywords/Search Tags:Separating cycle, Choosability, DP-coloring, Reducible configurations
PDF Full Text Request
Related items