Computing Reviews

Planar graphs without 4-cycles adjacent to triangles are 4-choosable
Cheng P., Chen M., Wang Y. Discrete Mathematics339(12):3052-3057,2016.Type:Article
Date Reviewed: 11/30/16

Let G be a finite simple graph. A list assignment is a function on the vertices that associates a list of colors with each vertex. An L-coloring is a function that colors each vertex with one of the colors in the union of all lists of colors, such that the color of a vertex is in its list of colors and such that any two adjacent vertices have different colors. A graph is L-colorable if it admits an L-coloring. A graph is called k-choosable if it is L-colorable for every list assignment that has at least k colors for each vertex.

This short and nice paper uses combinatorial arguments to show that every planar graph without 4-cycles adjacent to triangles is 4-choosable. This is an improvement on a result by Lam et al. [1] showing that every planar graph without 4-cycles is 4-choosable.


1)

Lam, P. C. B.; Xu, B.; Liu, J. The 4-choosability of plane graphs without 4-cycles. J. Combin. Theory Ser. B 76 (1999), 117–126.

Reviewer:  Jan De Beule Review #: CR144952 (1702-0146)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy