Font Size: a A A

Defective DP-coloring Of Planar Graphs

Posted on:2021-03-09Degree:MasterType:Thesis
Country:ChinaCandidate:T T ShanFull Text:PDF
GTID:2370330611990633Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
This paper proves that every planar graph G contains a subgraph H with ?(H)?6 such that G-E(H)is 2-degenerate.As a consequence of this result,every planar graph G is 6-defective DP 3-colorable.On the other hand,we show that there is a planar graph which is not 3-defective DP 3-colourable.It remains an open problem whether every planar graph is d-defective DP 3-colourable,for d=4,5.
Keywords/Search Tags:planar graphs, 2-degenerate planar graphs, defective colouring, acyclic orientation, DP-coloring
PDF Full Text Request
Related items