Planar graphs without chordal 6-cycles are 4-choosable

A graph G is k-choosable if it can be colored whenever every vertex has a list of at least k available colors. In this paper, we prove that every planar graph without chordal 6-cycles is 4-choosable. This extends a known result that every planar graph without 6-cycles is 4-choosable.

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-07, Vol.244, p.116-123
Main Authors: Hu, Dai-Qiang, Huang, Danjun, Wang, Weifan, Wu, Jian-Liang
Format: Article
Language:English
Subjects:
Chord
Combinatorics
Cycle
Graph theory
Graphs
List coloring
Planar graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph G is k-choosable if it can be colored whenever every vertex has a list of at least k available colors. In this paper, we prove that every planar graph without chordal 6-cycles is 4-choosable. This extends a known result that every planar graph without 6-cycles is 4-choosable.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.03.014