Mathematics – Combinatorics
Scientific paper
2005-12-22
Discussiones Mathematicae Graph Theory. Vol. 29 (1), 2009, pp. 163-178
Mathematics
Combinatorics
10 pages, 1 figure. This is a new version, with significantly more results. To make the paper shorter, we have omitted the two
Scientific paper
Let $G$ be a planar graph with no two 3-cycles sharing an edge. We show that if $\Delta(G)\geq 9$, then $\chi'_l(G) = \Delta(G)$ and $\chi''_l(G)=\Delta(G)+1.$ We also show that if $\Delta(G)\geq 6$, then $\chi'_l(G)\leq\Delta(G)+1$ and if $\Delta(G)\geq 7$, then $\chi''_l(G)\leq\Delta(G)+2$. All of these results extend to graphs in the projective plane and when $\Delta(G)\geq 7$ the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method to prove structural lemmas about the existence of subgraphs with small degree-sum. For example, we prove that if $G$ is a planar graph with no two 3-cycles sharing an edge and with $\Delta(G)\geq 7$, then $G$ has an edge $uv$ with $d(u)\leq 4$ and $d(u)+d(v)\leq \Delta(G)+2$. All of our proofs yield linear-time algorithms that produce the desired colorings.
No associations
LandOfFree
Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-726328