A Structure of 1-Planar Graph and Its Applications to Coloring Problems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-07

AUTHORS

Xin Zhang, Bei Niu, Jiguo Yu

ABSTRACT

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. In this paper, we first give a useful structural theorem for 1-planar graphs, and then apply it to the list edge and list total coloring, the (p, 1)-total labelling, and the equitable edge coloring of 1-planar graphs. More precisely, we verify the well-known List Edge Coloring Conjecture and List Total Coloring Conjecture for 1-planar graph with maximum degree at least 18, prove that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G)+2p-2 provided that Δ(G)≥8p+2 and p≥2, and show that every 1-planar graph has an equitable edge coloring with k colors for any integer k≥18. These three results respectively generalize the main theorems of three different previously published papers. More... »

PAGES

1-12

References to SciGraph publications

  • 2011-12. On (p, 1)-total labelling of 1-planar graphs in CENTRAL EUROPEAN JOURNAL OF MATHEMATICS
  • 1976. Graph Theory with Applications in NONE
  • 2015-07. On total colorings of 1-planar graphs in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2007. The Equitable Edge-Coloring of Series-Parallel Graphs in COMPUTATIONAL SCIENCE – ICCS 2007
  • 2017-01. On (p, 1)-total labelling of planar graphs in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2012-10. List edge and list total coloring of 1-planar graphs in FRONTIERS OF MATHEMATICS IN CHINA
  • 2017-07. On the Equitable Edge-Coloring of 1-Planar Graphs and Planar Graphs in GRAPHS AND COMBINATORICS
  • 1965-12. Ein Sechsfarbenproblem auf der Kugel in ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITÄT HAMBURG
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00373-019-02027-0

    DOI

    http://dx.doi.org/10.1007/s00373-019-02027-0

    DIMENSIONS

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


    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": "Xidian University", 
              "id": "https://www.grid.ac/institutes/grid.440736.2", 
              "name": [
                "School of Mathematics and Statistics, Xidian University, 710071, Xi\u2019an, Shaanxi, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Xin", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Xidian University", 
              "id": "https://www.grid.ac/institutes/grid.440736.2", 
              "name": [
                "School of Mathematics and Statistics, Xidian University, 710071, Xi\u2019an, Shaanxi, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Niu", 
            "givenName": "Bei", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Qufu Normal University", 
              "id": "https://www.grid.ac/institutes/grid.412638.a", 
              "name": [
                "School of Information Science and Engineering, Qufu Normal University, 276826, Rizhao, Shandong, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yu", 
            "givenName": "Jiguo", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-72588-6_75", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001351925", 
              "https://doi.org/10.1007/978-3-540-72588-6_75"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.3190190406", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003802898"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2007.11.044", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003901349"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2011.10.021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004495806"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11464-012-0184-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005722285", 
              "https://doi.org/10.1007/s11464-012-0184-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2005.12.059", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012125789"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2010.11.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013094854"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02996313", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020129667", 
              "https://doi.org/10.1007/bf02996313"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-013-9641-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029492054", 
              "https://doi.org/10.1007/s10878-013-9641-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jctb.1997.1780", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035064397"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-015-9958-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035459083", 
              "https://doi.org/10.1007/s10878-015-9958-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2007.03.034", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036635300"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.2478/s11533-011-0092-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036972189", 
              "https://doi.org/10.2478/s11533-011-0092-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.2478/s11533-011-0092-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036972189", 
              "https://doi.org/10.2478/s11533-011-0092-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2005.11.056", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037735353"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00373-017-1786-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085577186", 
              "https://doi.org/10.1007/s00373-017-1786-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00373-017-1786-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085577186", 
              "https://doi.org/10.1007/s00373-017-1786-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cosrev.2017.06.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090553413"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1109703686", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-349-03521-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109703686", 
              "https://doi.org/10.1007/978-1-349-03521-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-349-03521-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109703686", 
              "https://doi.org/10.1007/978-1-349-03521-2"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-07", 
        "datePublishedReg": "2019-03-07", 
        "description": "A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. In this paper, we first give a useful structural theorem for 1-planar graphs, and then apply it to the list edge and list total coloring, the (p, 1)-total labelling, and the equitable edge coloring of 1-planar graphs. More precisely, we verify the well-known List Edge Coloring Conjecture and List Total Coloring Conjecture for 1-planar graph with maximum degree at least 18, prove that the (p, 1)-total labelling number of every 1-planar graph G is at most \u0394(G)+2p-2 provided that \u0394(G)\u22658p+2 and p\u22652, and show that every 1-planar graph has an equitable edge coloring with k colors for any integer k\u226518. These three results respectively generalize the main theorems of three different previously published papers.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00373-019-02027-0", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7196402", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136071", 
            "issn": [
              "0911-0119", 
              "1435-5914"
            ], 
            "name": "Graphs and Combinatorics", 
            "type": "Periodical"
          }
        ], 
        "name": "A Structure of 1-Planar Graph and Its Applications to Coloring Problems", 
        "pagination": "1-12", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a0ccfdfa8d9f7e670c49a020f5b8ac329f7f3c06c6db27c967e10c744615c3b5"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00373-019-02027-0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112587432"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00373-019-02027-0", 
          "https://app.dimensions.ai/details/publication/pub.1112587432"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:19", 
        "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_11707_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02027-0"
      }
    ]
     

    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-02027-0'

    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-02027-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02027-0'

    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-02027-0'


     

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

    132 TRIPLES      21 PREDICATES      42 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00373-019-02027-0 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nf49a9c2e8a8b4363a7995f51b3d14f5d
    4 schema:citation sg:pub.10.1007/978-1-349-03521-2
    5 sg:pub.10.1007/978-3-540-72588-6_75
    6 sg:pub.10.1007/bf02996313
    7 sg:pub.10.1007/s00373-017-1786-3
    8 sg:pub.10.1007/s10878-013-9641-9
    9 sg:pub.10.1007/s10878-015-9958-7
    10 sg:pub.10.1007/s11464-012-0184-7
    11 sg:pub.10.2478/s11533-011-0092-1
    12 https://app.dimensions.ai/details/publication/pub.1109703686
    13 https://doi.org/10.1002/jgt.3190190406
    14 https://doi.org/10.1006/jctb.1997.1780
    15 https://doi.org/10.1016/j.cosrev.2017.06.002
    16 https://doi.org/10.1016/j.disc.2005.11.056
    17 https://doi.org/10.1016/j.disc.2005.12.059
    18 https://doi.org/10.1016/j.disc.2007.03.034
    19 https://doi.org/10.1016/j.disc.2007.11.044
    20 https://doi.org/10.1016/j.ipl.2010.11.001
    21 https://doi.org/10.1016/j.ipl.2011.10.021
    22 schema:datePublished 2019-03-07
    23 schema:datePublishedReg 2019-03-07
    24 schema:description A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. In this paper, we first give a useful structural theorem for 1-planar graphs, and then apply it to the list edge and list total coloring, the (p, 1)-total labelling, and the equitable edge coloring of 1-planar graphs. More precisely, we verify the well-known List Edge Coloring Conjecture and List Total Coloring Conjecture for 1-planar graph with maximum degree at least 18, prove that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G)+2p-2 provided that Δ(G)≥8p+2 and p≥2, and show that every 1-planar graph has an equitable edge coloring with k colors for any integer k≥18. These three results respectively generalize the main theorems of three different previously published papers.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf sg:journal.1136071
    29 schema:name A Structure of 1-Planar Graph and Its Applications to Coloring Problems
    30 schema:pagination 1-12
    31 schema:productId N23e66797c51a49c59b46b4ae13f92ae0
    32 N32a900485dbd42a3a303932e41f0e9b8
    33 N8d504fdb37414e0ba767d804a58e8ed4
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112587432
    35 https://doi.org/10.1007/s00373-019-02027-0
    36 schema:sdDatePublished 2019-04-11T11:19
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher N0a4fa6e2fdd1411fbd66785b4b109a11
    39 schema:url https://link.springer.com/10.1007%2Fs00373-019-02027-0
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset articles
    42 rdf:type schema:ScholarlyArticle
    43 N0a4fa6e2fdd1411fbd66785b4b109a11 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N119e245663364697b0417f2760d41cce schema:affiliation https://www.grid.ac/institutes/grid.412638.a
    46 schema:familyName Yu
    47 schema:givenName Jiguo
    48 rdf:type schema:Person
    49 N23e66797c51a49c59b46b4ae13f92ae0 schema:name dimensions_id
    50 schema:value pub.1112587432
    51 rdf:type schema:PropertyValue
    52 N324d3e6c474d4c07a44ff50697f7371b schema:affiliation https://www.grid.ac/institutes/grid.440736.2
    53 schema:familyName Niu
    54 schema:givenName Bei
    55 rdf:type schema:Person
    56 N32a900485dbd42a3a303932e41f0e9b8 schema:name doi
    57 schema:value 10.1007/s00373-019-02027-0
    58 rdf:type schema:PropertyValue
    59 N8d504fdb37414e0ba767d804a58e8ed4 schema:name readcube_id
    60 schema:value a0ccfdfa8d9f7e670c49a020f5b8ac329f7f3c06c6db27c967e10c744615c3b5
    61 rdf:type schema:PropertyValue
    62 Nad83b81395b74b068e22b4deda942362 rdf:first N119e245663364697b0417f2760d41cce
    63 rdf:rest rdf:nil
    64 Nc08773cd0bb9497d8fa948b9affde539 rdf:first N324d3e6c474d4c07a44ff50697f7371b
    65 rdf:rest Nad83b81395b74b068e22b4deda942362
    66 Ncf6c90cdd5ce4aa7917e021c949408eb schema:affiliation https://www.grid.ac/institutes/grid.440736.2
    67 schema:familyName Zhang
    68 schema:givenName Xin
    69 rdf:type schema:Person
    70 Nf49a9c2e8a8b4363a7995f51b3d14f5d rdf:first Ncf6c90cdd5ce4aa7917e021c949408eb
    71 rdf:rest Nc08773cd0bb9497d8fa948b9affde539
    72 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Mathematical Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Pure Mathematics
    77 rdf:type schema:DefinedTerm
    78 sg:grant.7196402 http://pending.schema.org/fundedItem sg:pub.10.1007/s00373-019-02027-0
    79 rdf:type schema:MonetaryGrant
    80 sg:journal.1136071 schema:issn 0911-0119
    81 1435-5914
    82 schema:name Graphs and Combinatorics
    83 rdf:type schema:Periodical
    84 sg:pub.10.1007/978-1-349-03521-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109703686
    85 https://doi.org/10.1007/978-1-349-03521-2
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/978-3-540-72588-6_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001351925
    88 https://doi.org/10.1007/978-3-540-72588-6_75
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/bf02996313 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020129667
    91 https://doi.org/10.1007/bf02996313
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/s00373-017-1786-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085577186
    94 https://doi.org/10.1007/s00373-017-1786-3
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/s10878-013-9641-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029492054
    97 https://doi.org/10.1007/s10878-013-9641-9
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/s10878-015-9958-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035459083
    100 https://doi.org/10.1007/s10878-015-9958-7
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/s11464-012-0184-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005722285
    103 https://doi.org/10.1007/s11464-012-0184-7
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.2478/s11533-011-0092-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036972189
    106 https://doi.org/10.2478/s11533-011-0092-1
    107 rdf:type schema:CreativeWork
    108 https://app.dimensions.ai/details/publication/pub.1109703686 schema:CreativeWork
    109 https://doi.org/10.1002/jgt.3190190406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003802898
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1006/jctb.1997.1780 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035064397
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/j.cosrev.2017.06.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090553413
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/j.disc.2005.11.056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037735353
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/j.disc.2005.12.059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012125789
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/j.disc.2007.03.034 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036635300
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/j.disc.2007.11.044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003901349
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1016/j.ipl.2010.11.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013094854
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1016/j.ipl.2011.10.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004495806
    126 rdf:type schema:CreativeWork
    127 https://www.grid.ac/institutes/grid.412638.a schema:alternateName Qufu Normal University
    128 schema:name School of Information Science and Engineering, Qufu Normal University, 276826, Rizhao, Shandong, China
    129 rdf:type schema:Organization
    130 https://www.grid.ac/institutes/grid.440736.2 schema:alternateName Xidian University
    131 schema:name School of Mathematics and Statistics, Xidian University, 710071, Xi’an, Shaanxi, China
    132 rdf:type schema:Organization
     




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


    ...