(Δ+1)-total choosability of planar graphs with no cycles of length from 4 to k and without close triangles

Publication year: 2011
Source: Discrete Mathematics, In Press, Corrected Proof, Available online 14 June 2011

Gerard J., Chang , Nicolas, Roussel

Let G be a planar graph with maximum degree Δ(G). In this paper, we prove that Gis (Δ(G)+1)-total choosable if G has no cycle of length from 4 to k and has minimum distance at least dΔ between triangles for (Δ(G),k,dΔ)=(6,4,1),(5,5,2),(5,6,1),(5,7,0),(4,6,3), (4,7,2),(4,10,1).

 Highlights: ► We study (D+1)-total choosability of planar graphs with maximum degree D. ► The absence of cycle of length from 4 to k and of triangles at distance less than d is sufficient. ► The cases (D,k,d)=(6,4,1),(5,5,2),(5,6,1),(5,7,0),(4,6,3),(4,7,2),(4,10,1) are proved. ► These results improve and generalize recent results from Borodin et al., Chang et al., and Hou et al. ► The proofs rely on the structural properties of an hypothetical minimal counter example.