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


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
  • 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: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "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": [
          {
            "name": "readcube_id", 
            "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02025-2"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00373-019-02025-2 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N653456ef9267479983012c771167f693
    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 N656969138bdb4669bc9055bdabbfdc26
    23 N6840d54b7b414288a5c11864e10acf79
    24 Nce5ccbf95c2f403db91af7f40a3446df
    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
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N6f4a77b036384c58b91896b88e2fa4b3
    30 schema:url https://link.springer.com/10.1007%2Fs00373-019-02025-2
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N0677b748fdc940ac8ae14a9ed381d2c0 schema:affiliation https://www.grid.ac/institutes/grid.411407.7
    35 schema:familyName Liu
    36 schema:givenName Runrun
    37 rdf:type schema:Person
    38 N07476a934aad41409057f621745e8196 schema:affiliation https://www.grid.ac/institutes/grid.411407.7
    39 schema:familyName Yin
    40 schema:givenName Yuxue
    41 rdf:type schema:Person
    42 N0cf940f3f5614a86ad5850a5918660e0 rdf:first Nee798227e43846e1afc386085a61e513
    43 rdf:rest rdf:nil
    44 N4e188de6eafa44238d098d92f5ae6cd9 rdf:first N07476a934aad41409057f621745e8196
    45 rdf:rest N0cf940f3f5614a86ad5850a5918660e0
    46 N653456ef9267479983012c771167f693 rdf:first N0677b748fdc940ac8ae14a9ed381d2c0
    47 rdf:rest N841d473fa21745f49648caa5bfa72867
    48 N656969138bdb4669bc9055bdabbfdc26 schema:name dimensions_id
    49 schema:value pub.1112609234
    50 rdf:type schema:PropertyValue
    51 N6840d54b7b414288a5c11864e10acf79 schema:name readcube_id
    52 schema:value 051968ff2d8bf670d8acb3e8dc5d50ea114f6970b8a1861157f631b57623cf76
    53 rdf:type schema:PropertyValue
    54 N6f4a77b036384c58b91896b88e2fa4b3 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 N841d473fa21745f49648caa5bfa72867 rdf:first Ncebb96727cf9458db5e6bdf3ca406888
    57 rdf:rest Nb7fbdccc26c44f34a86cf98a34a0a8a6
    58 Nb7fbdccc26c44f34a86cf98a34a0a8a6 rdf:first Nd89ff5bc77ba4c33879f9501aa030d43
    59 rdf:rest N4e188de6eafa44238d098d92f5ae6cd9
    60 Nce5ccbf95c2f403db91af7f40a3446df schema:name doi
    61 schema:value 10.1007/s00373-019-02025-2
    62 rdf:type schema:PropertyValue
    63 Ncebb96727cf9458db5e6bdf3ca406888 schema:affiliation https://www.grid.ac/institutes/grid.256771.0
    64 schema:familyName Loeb
    65 schema:givenName Sarah
    66 rdf:type schema:Person
    67 Nd89ff5bc77ba4c33879f9501aa030d43 schema:affiliation https://www.grid.ac/institutes/grid.264889.9
    68 schema:familyName Rolek
    69 schema:givenName Martin
    70 rdf:type schema:Person
    71 Nee798227e43846e1afc386085a61e513 schema:affiliation https://www.grid.ac/institutes/grid.264889.9
    72 schema:familyName Yu
    73 schema:givenName Gexin
    74 rdf:type schema:Person
    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
     




    Preview window. Press ESC to close (or click here)


    ...