On The Improper Coloring Of Planar Graphs

This paper investigates the improper(or defective/relaxed)coloring of planar graphs.In 1976,Steinberg conjectured that every planar graph without 4-cycle and 5-cycle is 3-colorable.In 2017,this conjecture was disproved.On the other hand,according to the four-color Theorem,every plane graph is 4-colorable,which indicates that every plane graph without 4-cycles and 5-cycles is "between:3-colorable and 4-colorable.The concept of improper coloring can be used to describe such state.The improper coloring of graphs is a relaxation of proper coloring of graphs,allowing the presence of edges in subgraphs induced by vertices with the same color.Specifically,a graph G is called {d1,...,dr}-colorable,if its vertex set can be partitioned into r subsets V1,...,Vr,where the maximum degree of the subgraph induced by Vi is at most di for each i ? {1,...,r}.The planar graphs studied in this paper include two classes.One class is the planar graphs without 4-cycles and 5-cycles,the other is the planar graphs with girth at least 5.Two colors are allowed in the coloring.For a planar graphs without 4-cycles and 5-cycles,denoted by G,Sittitrati and Nakprasit[Disctete Math.,341(2018)2142-2150]show that G is(d1,d2)-colorable,where(d1,d2)? {(2,9),(3,5),(4,4)}.We improve their results and show that G is(d1,d2)-colorable,where(d1,d2)?{(2,6),(3,3)}.For a planar graph with girth at least 5,denoted by H,Choi et,al.[J.Graph Theory,84(4)(2017)521-535]show that H is(1,10)-colorable,Borodin and Kostochka[Discrete Math.,313(22)(2013)268-2649]prove that H is(2,6)-colorable,and Choi et al.[Discrete Math.,342(12)(2019)111577]reveal that H is(3,4)-colorable.In this paper,we improve the result that H is(1,10)-colorable and show that H is(1,9)-colorable.The results of this paper are the best results so far on the improper coloring of these two kinds of planar graphs,providing a new and deeper insights for colorings of these two kinds of planar graphs.