Font Size: a A A

Planar Graphs Without 3,8,9-cycles Are DP-3-colorable

Posted on:2021-03-10Degree:MasterType:Thesis
Country:ChinaCandidate:Q HeFull Text:PDF
GTID:2370330605961402Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
A graph G is k-colorable if its vertex set can be partitioned into k color classes so that each color class is an independent set,that is,two adjacent points in graph G have different colors.Graph G=(V,E)is L-coloring,if assign each vertex v of G a color list L(v),for each vertex v of graph G,has a normal coloring c makes c(v)E L(v).If every vertex v of graph G has a set of color list |L(v)|≥k,for each vertex of graph G,graph G has a normal color makes c(v)∈L(v),then the graph G is k-colorable.This article mainly research DP-coloring.as an extension of the list coloring,DP-coloring is by Devorak and Postle in 2018.For list coloring,same color of the adjacent point matching,but for DP-coloring,the adjacent points matching is arbitrary.The planar graph of a few conclusions on the list coloring can be extended to DP-coloring,but most of the list coloring of conclusion can not be extended to DP-coloring.As Bernshteyn and Kostochka notes:list coloring and DP-coloring is different.So it’s natural to shift scholars and hobbyists focus from list coloring to DP-coloring.Since it has been proved that every planar graph is DP-5-colorable,can the bounds of the number of color be reduced?Therefore,the search for sufficient condi-tions for DP-4-colorable and DP-3-colorable has attracted the attention and consider-ation of most researchers.Results of research on DP-4-colorable and DP-3-colorable:Planar graphs without 4-cycle adjacent two 3-cycles are DP-4-colorable;Planar graphs without(4,5)-cycles and close 3-cycle are DP-3-colorable;Planar graphs with-out(4,6,7,9)-cycles are DP-3-colorable;Planar graphs without(4,6,8,9)-cycles are DP-3-colorable;Planar graphs without.(4,7,8,9)-cycles are DP-3-colorable.In this paper,we will further study the related DP-coloring problems.Moreover,we will extended planar graphs without(3,8,9)-cycles are 3-list coloring to planar graphs without(3,8,9)-cycles are DP-3-colorable.
Keywords/Search Tags:DP-3-colorable, Minimum counterexample, Reducible configurations, Discharging rules
PDF Full Text Request
Related items