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 N932bdad9f1a74bcf84887be13a712622
    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
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N6dd4b6174d3a439e9b8483a94445bcfa
    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 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
    39 rdf:rest Naed9fcc3d2cd4960bc7edb6ad6ebf463
    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
    60 N932bdad9f1a74bcf84887be13a712622 rdf:first N768ec278a5284ffd88be5eeb3c7d59e8
    61 rdf:rest N76570373ac284694826983d211985f65
    62 Naed9fcc3d2cd4960bc7edb6ad6ebf463 rdf:first Ncb57ac4035154e3f87f7d1eb80b5d600
    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
    72 Nf32aa657102b4cb383a4a98141781a8d schema:name readcube_id
    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
     




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


    ...