Name
Abstract | ||
|---|---|---|
A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying (|L(x)cap L(y)|le d) for each edge xy. An L-coloring is a vertex coloring (pi ) such that (pi (v) in L(v)) for each vertex v and (pi (x) ne pi (y)) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4- and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5- and 6-cycles are (3, 1)-choosable. |
Year | DOI | Venue |
|---|---|---|
2017 | https://doi.org/10.1007/s10878-017-0124-2 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Planar graphs,Choosability with separation,List coloring,Cycles | Discharging method,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),List coloring,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
34 | 4 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chen | 1 | 10 | 2.44 |
| Yingying Fan | 2 | 8 | 2.17 |
| Yiqiao Wang | 3 | 494 | 42.81 |
| Weifan Wang | 4 | 868 | 89.92 |