Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
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: Nov 30 2016

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.

Reviewer:  Jan De Beule Review #: CR144952 (1702-0146)
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.
Bookmark and Share
  Featured Reviewer  
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy