# DP-3-Coloring of Planar Graphs Without 4, 9-Cycles and Cycles of Two Lengths from {6,7,8}

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2019-03-07

AUTHORS

Runrun Liu, Sarah Loeb, Martin Rolek, Yuxue Yin, Gexin Yu

ABSTRACT

A generalization of list-coloring, now known as DP-coloring, was recently introduced by Dvořák and Postle (Comb Theory Ser B 129:38–54, 2018). Essentially, DP-coloring assigns an arbitrary matching between lists of colors at adjacent vertices, as opposed to only matching identical colors as is done for list-coloring. Several results on list-coloring of planar graphs have since been extended to the setting of DP-coloring (Liu and Li, Discrete Math 342:623–627, 2019; Liu et al., Discrete Math 342(1):178–189, 2019; Kim and Ozeki, A note on a Brooks type theorem for DP-coloring, arXiv:1709.09807, 2019; Kim and Yu, Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, arXiv:1712.08999, 2019; Sittitrai and Nakprasit, Every planar graph without i-cycles adjacent simultaneously to j-cycles and k-cycles is DP-4-colorable when {i,j,k}={3,4,5}, arXiv:1801.06760, 2019; Yin and Yu, Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, arXiv:1809.00925, 2019). We note that list-coloring results do not always extend to DP-coloring results, as shown in Bernshteyn and Kostochka (On differences between DP-coloring and list coloring, arXiv:1705.04883, 2019). Our main result in this paper is to prove that every planar graph without cycles of length {4,a,b,9} for a,b∈{6,7,8} is DP-3-colorable, extending three existing results (Shen and Wang, Inf Process Lett 104:146–151, 2007; Wang and Shen, Discrete Appl Math 159:232–239, 2011; Whang et al., Inf Process Lett 105:206–211, 2008) on 3-choosability of planar graphs. More... »

PAGES

1-11

### References to SciGraph publications

• 1992-06. Colorings and orientations of graphs in COMBINATORICA
• ### Journal

TITLE

Graphs and Combinatorics

ISSUE

N/A

VOLUME

N/A

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00373-019-02025-2

DOI

http://dx.doi.org/10.1007/s00373-019-02025-2

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1112609234

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

``````[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Central China Normal University",
"id": "https://www.grid.ac/institutes/grid.411407.7",
"name": [
"Department of Mathematics, Central China Normal University, Wuhan, Hubei, China"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Runrun",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Hampden\u2013Sydney College",
"id": "https://www.grid.ac/institutes/grid.256771.0",
"name": [
"Department of Mathematics, The College of William and Mary, 23185, Williamsburg, VA, USA",
"Hampden-Sydney College, 23943, Hampden-Sdyney, VA, USA"
],
"type": "Organization"
},
"familyName": "Loeb",
"givenName": "Sarah",
"type": "Person"
},
{
"affiliation": {
"alternateName": "College of William & Mary",
"id": "https://www.grid.ac/institutes/grid.264889.9",
"name": [
"Department of Mathematics, The College of William and Mary, 23185, Williamsburg, VA, USA"
],
"type": "Organization"
},
"familyName": "Rolek",
"givenName": "Martin",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Central China Normal University",
"id": "https://www.grid.ac/institutes/grid.411407.7",
"name": [
"Department of Mathematics, Central China Normal University, Wuhan, Hubei, China"
],
"type": "Organization"
},
"familyName": "Yin",
"givenName": "Yuxue",
"type": "Person"
},
{
"affiliation": {
"alternateName": "College of William & Mary",
"id": "https://www.grid.ac/institutes/grid.264889.9",
"name": [
"Department of Mathematics, Central China Normal University, Wuhan, Hubei, China",
"Department of Mathematics, The College of William and Mary, 23185, Williamsburg, VA, USA"
],
"type": "Organization"
},
"familyName": "Yu",
"givenName": "Gexin",
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1006/jctb.1994.1062",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002067900"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/jctb.1995.1027",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005627019"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.dam.2010.11.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005901640"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01204715",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013095644",
"https://doi.org/10.1007/bf01204715"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01204715",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013095644",
"https://doi.org/10.1007/bf01204715"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ipl.2007.06.005",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018758903"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ipl.2007.08.027",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044737782"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jctb.2017.09.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1091575285"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.disc.2018.09.025",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1107585191"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.disc.2018.10.025",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1110257357"
],
"type": "CreativeWork"
}
],
"datePublished": "2019-03-07",
"datePublishedReg": "2019-03-07",
"description": "A generalization of list-coloring, now known as DP-coloring, was recently introduced by Dvo\u0159\u00e1k and Postle (Comb Theory Ser B 129:38\u201354, 2018). Essentially, DP-coloring assigns an arbitrary matching between lists of colors at adjacent vertices, as opposed to only matching identical colors as is done for list-coloring. Several results on list-coloring of planar graphs have since been extended to the setting of DP-coloring (Liu and Li, Discrete Math 342:623\u2013627, 2019; Liu et al., Discrete Math 342(1):178\u2013189, 2019; Kim and Ozeki, A note on a Brooks type theorem for DP-coloring, arXiv:1709.09807, 2019; Kim and Yu, Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, arXiv:1712.08999, 2019; Sittitrai and Nakprasit, Every planar graph without i-cycles adjacent simultaneously to j-cycles and k-cycles is DP-4-colorable when {i,j,k}={3,4,5}, arXiv:1801.06760, 2019; Yin and Yu, Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, arXiv:1809.00925, 2019). We note that list-coloring results do not always extend to DP-coloring results, as shown in Bernshteyn and Kostochka (On differences between DP-coloring and list coloring, arXiv:1705.04883, 2019). Our main result in this paper is to prove that every planar graph without cycles of length {4,a,b,9} for a,b\u2208{6,7,8} is DP-3-colorable, extending three existing results (Shen and Wang, Inf Process Lett 104:146\u2013151, 2007; Wang and Shen, Discrete Appl Math 159:232\u2013239, 2011; Whang et al., Inf Process Lett 105:206\u2013211, 2008) on 3-choosability of planar graphs.",
"genre": "research_article",
"id": "sg:pub.10.1007/s00373-019-02025-2",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1136071",
"issn": [
"0911-0119",
"1435-5914"
],
"name": "Graphs and Combinatorics",
"type": "Periodical"
}
],
"name": "DP-3-Coloring of Planar Graphs Without 4, 9-Cycles and Cycles of Two Lengths from {6,7,8}",
"pagination": "1-11",
"productId": [
{
"type": "PropertyValue",
"value": [
"051968ff2d8bf670d8acb3e8dc5d50ea114f6970b8a1861157f631b57623cf76"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00373-019-02025-2"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1112609234"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00373-019-02025-2",
"https://app.dimensions.ai/details/publication/pub.1112609234"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T11:20",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000354_0000000354/records_11719_00000002.jsonl",
"type": "ScholarlyArticle",
}
]``````

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

`curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02025-2'`

N-Triples is a line-based linked data format ideal for batch operations.

`curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02025-2'`

`curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02025-2'`

RDF/XML is a standard XML format for linked data.

`curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02025-2'`

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      21 PREDICATES      33 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
4 schema:citation sg:pub.10.1007/bf01204715
5 https://doi.org/10.1006/jctb.1994.1062
6 https://doi.org/10.1006/jctb.1995.1027
7 https://doi.org/10.1016/j.dam.2010.11.002
8 https://doi.org/10.1016/j.disc.2018.09.025
9 https://doi.org/10.1016/j.disc.2018.10.025
10 https://doi.org/10.1016/j.ipl.2007.06.005
11 https://doi.org/10.1016/j.ipl.2007.08.027
12 https://doi.org/10.1016/j.jctb.2017.09.001
13 schema:datePublished 2019-03-07
14 schema:datePublishedReg 2019-03-07
15 schema:description A generalization of list-coloring, now known as DP-coloring, was recently introduced by Dvořák and Postle (Comb Theory Ser B 129:38–54, 2018). Essentially, DP-coloring assigns an arbitrary matching between lists of colors at adjacent vertices, as opposed to only matching identical colors as is done for list-coloring. Several results on list-coloring of planar graphs have since been extended to the setting of DP-coloring (Liu and Li, Discrete Math 342:623–627, 2019; Liu et al., Discrete Math 342(1):178–189, 2019; Kim and Ozeki, A note on a Brooks type theorem for DP-coloring, arXiv:1709.09807, 2019; Kim and Yu, Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, arXiv:1712.08999, 2019; Sittitrai and Nakprasit, Every planar graph without i-cycles adjacent simultaneously to j-cycles and k-cycles is DP-4-colorable when {i,j,k}={3,4,5}, arXiv:1801.06760, 2019; Yin and Yu, Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable, arXiv:1809.00925, 2019). We note that list-coloring results do not always extend to DP-coloring results, as shown in Bernshteyn and Kostochka (On differences between DP-coloring and list coloring, arXiv:1705.04883, 2019). Our main result in this paper is to prove that every planar graph without cycles of length {4,a,b,9} for a,b∈{6,7,8} is DP-3-colorable, extending three existing results (Shen and Wang, Inf Process Lett 104:146–151, 2007; Wang and Shen, Discrete Appl Math 159:232–239, 2011; Whang et al., Inf Process Lett 105:206–211, 2008) on 3-choosability of planar graphs.
16 schema:genre research_article
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf sg:journal.1136071
20 schema:name DP-3-Coloring of Planar Graphs Without 4, 9-Cycles and Cycles of Two Lengths from {6,7,8}
21 schema:pagination 1-11
22 schema:productId N4855b9643c124bfba23ee44d7ee3e1a5
23 N8c3c8bdbf4f94967a7fa72c1b4ff5df2
24 Nf32aa657102b4cb383a4a98141781a8d
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112609234
26 https://doi.org/10.1007/s00373-019-02025-2
27 schema:sdDatePublished 2019-04-11T11:20
29 schema:sdPublisher N6dd4b6174d3a439e9b8483a94445bcfa
32 sgo:sdDataset articles
33 rdf:type schema:ScholarlyArticle
34 N175bf83a76ef4b73bd2be4460506cb1f schema:affiliation https://www.grid.ac/institutes/grid.411407.7
35 schema:familyName Yin
36 schema:givenName Yuxue
37 rdf:type schema:Person
38 N26a92237b7b14df1bd85dee7abb81e24 rdf:first N175bf83a76ef4b73bd2be4460506cb1f
40 N3204df25c3634cd0abe9a6acd7f2034a rdf:first N562da1a4b3b348b5976023c1db4aec9e
41 rdf:rest N26a92237b7b14df1bd85dee7abb81e24
42 N4855b9643c124bfba23ee44d7ee3e1a5 schema:name dimensions_id
43 schema:value pub.1112609234
44 rdf:type schema:PropertyValue
45 N562da1a4b3b348b5976023c1db4aec9e schema:affiliation https://www.grid.ac/institutes/grid.264889.9
46 schema:familyName Rolek
47 schema:givenName Martin
48 rdf:type schema:Person
49 N6dd4b6174d3a439e9b8483a94445bcfa schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N76570373ac284694826983d211985f65 rdf:first Nb3291d14210c4c4c90d8ee3bbf067e90
52 rdf:rest N3204df25c3634cd0abe9a6acd7f2034a
53 N768ec278a5284ffd88be5eeb3c7d59e8 schema:affiliation https://www.grid.ac/institutes/grid.411407.7
54 schema:familyName Liu
55 schema:givenName Runrun
56 rdf:type schema:Person
57 N8c3c8bdbf4f94967a7fa72c1b4ff5df2 schema:name doi
58 schema:value 10.1007/s00373-019-02025-2
59 rdf:type schema:PropertyValue
61 rdf:rest N76570373ac284694826983d211985f65
63 rdf:rest rdf:nil
64 Nb3291d14210c4c4c90d8ee3bbf067e90 schema:affiliation https://www.grid.ac/institutes/grid.256771.0
65 schema:familyName Loeb
66 schema:givenName Sarah
67 rdf:type schema:Person
68 Ncb57ac4035154e3f87f7d1eb80b5d600 schema:affiliation https://www.grid.ac/institutes/grid.264889.9
69 schema:familyName Yu
70 schema:givenName Gexin
71 rdf:type schema:Person
73 schema:value 051968ff2d8bf670d8acb3e8dc5d50ea114f6970b8a1861157f631b57623cf76
74 rdf:type schema:PropertyValue
75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
76 schema:name Mathematical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
79 schema:name Pure Mathematics
80 rdf:type schema:DefinedTerm
81 sg:journal.1136071 schema:issn 0911-0119
82 1435-5914
83 schema:name Graphs and Combinatorics
84 rdf:type schema:Periodical
85 sg:pub.10.1007/bf01204715 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013095644
86 https://doi.org/10.1007/bf01204715
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1006/jctb.1994.1062 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002067900
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1006/jctb.1995.1027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005627019
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/j.dam.2010.11.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005901640
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/j.disc.2018.09.025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107585191
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/j.disc.2018.10.025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110257357
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/j.ipl.2007.06.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018758903
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/j.ipl.2007.08.027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044737782
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/j.jctb.2017.09.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091575285
103 rdf:type schema:CreativeWork
104 https://www.grid.ac/institutes/grid.256771.0 schema:alternateName Hampden–Sydney College
105 schema:name Department of Mathematics, The College of William and Mary, 23185, Williamsburg, VA, USA
106 Hampden-Sydney College, 23943, Hampden-Sdyney, VA, USA
107 rdf:type schema:Organization
108 https://www.grid.ac/institutes/grid.264889.9 schema:alternateName College of William & Mary
109 schema:name Department of Mathematics, Central China Normal University, Wuhan, Hubei, China
110 Department of Mathematics, The College of William and Mary, 23185, Williamsburg, VA, USA
111 rdf:type schema:Organization
112 https://www.grid.ac/institutes/grid.411407.7 schema:alternateName Central China Normal University
113 schema:name Department of Mathematics, Central China Normal University, Wuhan, Hubei, China
114 rdf:type schema:Organization