Font Size: a A A

A Relaxation Of The Bordeaux Conjecture

Posted on:2016-04-03Degree:MasterType:Thesis
Country:ChinaCandidate:R R LiuFull Text:PDF
GTID:2180330464472113Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
LetG={V(G), E(G)). A κ-coloring of G is a mapping φ:V(G)(?){1,2,...,k} satisfies that for every i,1≤i≤k, G[Vi] is edgeless, where G[Vi] denotes the subgraph induced by the vertices colored i. A graph G is k-colorable if it exists a k-coloring; A (c1, c2,...,Ck)-coloring of G is a mapping φ:V(G) (?){1,2,..., k} satisfies that for every i,1≤i≤k, G[Vi] has maximum degree at most ci. A graph G is (c1, C2,..., ck)-colorable if it exists a (c1, C2,..., Cf)-coloring.In recent years,the classic four-color problem has been researched by many schol-ars. In 1977, Appel and Haken proved it with the help of computer. In order to find a proof purely by elegant math-analysis to solve this problem, many experts and schol-ars start to do some profound research on the three-color problem of planar graph. In 2003, Borodin and Raspaud conjectured that every planar graph with neither 5-cycles nor intersecting triangles is 3-colorable. We prove in this paper that every planar graph with neither intersecting triangles nor 5-cycles is (2,0,0)-colorable.
Keywords/Search Tags:Separating cycle, Minimum counterexample, Reducible configurations, Discharging rules
PDF Full Text Request
Related items