Planar Graphs Without 4-cycles Are(4,4)-colorable

A graph is k-colorable if its vertex set can be partitioned into k color classes so that each color class is an independent set.This is proper coloring.In this paper,we focus the improper coloring.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 maximum degree at most di for i = 1,2,...,k.The length of a shorted cycle is girth.The famous Four Color Theorem states that every planar graph is 4-colorable.Since there are planar graphs that are not 3-colorable,finding sufficient conditions for a planar graph.to ba 3-colorable has been an active area of research.The most well-known result is that:Planar graphs without 3-cycles are 3-colorable.At present,there are some other conclusion about 3-coloring:Planar graphs without(4,5,6,9)-cycles are 3-colorable;Planar graphs without(4,5,7)-cycles are 3-colorable;Planar graphs without(4,5,8,9)-cycles are 3-colorable;Planar graphs without(4,6,7,9)-cycles are 3-colorable;Planar graphs without(4,6,8)-cycles are 3-colorable;Planar graphs without(4,7,8,9)-cycles are 3-colorable.And Planar graphs are(2,2,2)-colorable.For each pair(d1,d2),there exist a planar graph with girth 4 that is not(d1,d2)-colorable,then we consider the problem of improper 2-coloring.in the base of without 4-cycles.At present,there are some conclusion about 2-coloring:Planar graph with.girth at least 5 are(1,10)-,(2,6)-,(3,4)-colorable.For given a nonnegative integer df a planar graph with girth 6 is not(0,d)-colorable.Recently,Choi,Liu and Oum proved that every planar graph without 4-cycles is(5,5)-colorable.By further study the structure of planar graphs without 4-cycles,we prove that every planax graph without 4-cycles is(4,4)-colorable.