Font Size: a A A

Planar Graphs Without Adjacent Cycles Of Length At Most Five Are(2,0,0)-colorable

Posted on:2019-10-03Degree:MasterType:Thesis
Country:ChinaCandidate:Q ShenFull Text:PDF
GTID:2370330548971604Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Let d1,d2,...,dk be k non-negative integers.A graph G is(d1,d2,...,dk)-colorable if the vertex set of G can be partitioned into subsets Vi,V2,...,Vk such that the subgraph G[Vi]induced by Vi has maxinum degree at most di for i=1,2,...,k.Nsk's Conjecture(2006)says that every planar graph with neither triangular 3-cycles nor triangular 5-cycles is 3-colorable.Borodin,Glebov,Raspaud and Salavatipour(2005)asked whether every planar graph without adjacent cycles of length at most 5 is 3-colorable.Cohen-Addad(2017)shown that both Nsk's conjecture and the prob-lem of Borodin are false.Zhang,Wang and Chen(2016)asked whether every planar graph without adjacent cycles of length at most 5 is(1,0,0)-colorable.Zhang,Wang and Chen showed that every planar graph without adjacent cycles of length at most five is(1,1,0)-colorable.In this paper,we show that every planar graph without adjacent cycles of length at most five is(2,0,0)-colorable.
Keywords/Search Tags:Separating cycle, Minimum counterexample, Reducible configurations, Discharging rules
PDF Full Text Request
Related items