Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-05-19

AUTHORS

Kenta Ozeki

ABSTRACT

A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable. More... »

PAGES

1-30

References to SciGraph publications

  • 1985-12. List-colourings of graphs in GRAPHS AND COMBINATORICS
  • 1992-06-01. Colorings and orientations of graphs in COMBINATORICA
  • 1996-09. List edge colourings of some 1-factorable multigraphs in COMBINATORICA
  • 2008-01. Pfaffian labelings and signs of edge colorings in COMBINATORICA
  • 2017-01-04. Spanning quadrangulations of triangulated surfaces in ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSIT√ĄT HAMBURG
  • 2007-01-01. Kempe Equivalence of Colorings in GRAPH THEORY IN PARIS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4330-2

    DOI

    http://dx.doi.org/10.1007/s00493-021-4330-2

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Faculty of Environment and Information Sciences, Yokohama National University, Yokohama, Japan", 
              "id": "http://www.grid.ac/institutes/grid.268446.a", 
              "name": [
                "Faculty of Environment and Information Sciences, Yokohama National University, Yokohama, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ozeki", 
            "givenName": "Kenta", 
            "id": "sg:person.014752016273.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014752016273.40"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s12188-016-0172-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018798184", 
              "https://doi.org/10.1007/s12188-016-0172-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02582936", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042921797", 
              "https://doi.org/10.1007/bf02582936"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-008-2231-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015937137", 
              "https://doi.org/10.1007/s00493-008-2231-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01261320", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023147320", 
              "https://doi.org/10.1007/bf01261320"
            ], 
            "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/978-3-7643-7400-6_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019998480", 
              "https://doi.org/10.1007/978-3-7643-7400-6_22"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-05-19", 
        "datePublishedReg": "2022-05-19", 
        "description": "A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4330-2", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7530221", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.9453656", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "graph G", 
          "projective plane", 
          "cubic graph G", 
          "bipartite planar graphs", 
          "chromatic number", 
          "Graphs Embedded", 
          "planar graphs", 
          "equivalence classes", 
          "triangulation G", 
          "cycle C", 
          "theorem", 
          "plane", 
          "conjecture", 
          "graph", 
          "Fisk", 
          "embedding", 
          "class", 
          "Kempe", 
          "Embedded", 
          "number", 
          "switch", 
          "results", 
          "sequence", 
          "analogues", 
          "products", 
          "color", 
          "paper"
        ], 
        "name": "Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane", 
        "pagination": "1-30", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1147999039"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4330-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4330-2", 
          "https://app.dimensions.ai/details/publication/pub.1147999039"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:49", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_925.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4330-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/s00493-021-4330-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/s00493-021-4330-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4330-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4330-2'


     

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

    106 TRIPLES      21 PREDICATES      55 URIs      41 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4330-2 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N4230a1893e944502b70ccc5b3b99e63f
    4 schema:citation sg:pub.10.1007/978-3-7643-7400-6_22
    5 sg:pub.10.1007/bf01204715
    6 sg:pub.10.1007/bf01261320
    7 sg:pub.10.1007/bf02582936
    8 sg:pub.10.1007/s00493-008-2231-2
    9 sg:pub.10.1007/s12188-016-0172-z
    10 schema:datePublished 2022-05-19
    11 schema:datePublishedReg 2022-05-19
    12 schema:description A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable.
    13 schema:genre article
    14 schema:isAccessibleForFree false
    15 schema:isPartOf sg:journal.1136493
    16 schema:keywords Embedded
    17 Fisk
    18 Graphs Embedded
    19 Kempe
    20 analogues
    21 bipartite planar graphs
    22 chromatic number
    23 class
    24 color
    25 conjecture
    26 cubic graph G
    27 cycle C
    28 embedding
    29 equivalence classes
    30 graph
    31 graph G
    32 number
    33 paper
    34 planar graphs
    35 plane
    36 products
    37 projective plane
    38 results
    39 sequence
    40 switch
    41 theorem
    42 triangulation G
    43 schema:name Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
    44 schema:pagination 1-30
    45 schema:productId N5dab4d0175de42f89912a2320648b880
    46 Ne06885f99ae045dd862e8dc9a0ada494
    47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1147999039
    48 https://doi.org/10.1007/s00493-021-4330-2
    49 schema:sdDatePublished 2022-10-01T06:49
    50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    51 schema:sdPublisher N7545519eaa894e2eb561368f9040ea86
    52 schema:url https://doi.org/10.1007/s00493-021-4330-2
    53 sgo:license sg:explorer/license/
    54 sgo:sdDataset articles
    55 rdf:type schema:ScholarlyArticle
    56 N4230a1893e944502b70ccc5b3b99e63f rdf:first sg:person.014752016273.40
    57 rdf:rest rdf:nil
    58 N5dab4d0175de42f89912a2320648b880 schema:name doi
    59 schema:value 10.1007/s00493-021-4330-2
    60 rdf:type schema:PropertyValue
    61 N7545519eaa894e2eb561368f9040ea86 schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Ne06885f99ae045dd862e8dc9a0ada494 schema:name dimensions_id
    64 schema:value pub.1147999039
    65 rdf:type schema:PropertyValue
    66 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Mathematical Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Pure Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:grant.7530221 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4330-2
    73 rdf:type schema:MonetaryGrant
    74 sg:grant.9453656 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4330-2
    75 rdf:type schema:MonetaryGrant
    76 sg:journal.1136493 schema:issn 0209-9683
    77 1439-6912
    78 schema:name Combinatorica
    79 schema:publisher Springer Nature
    80 rdf:type schema:Periodical
    81 sg:person.014752016273.40 schema:affiliation grid-institutes:grid.268446.a
    82 schema:familyName Ozeki
    83 schema:givenName Kenta
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014752016273.40
    85 rdf:type schema:Person
    86 sg:pub.10.1007/978-3-7643-7400-6_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019998480
    87 https://doi.org/10.1007/978-3-7643-7400-6_22
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/bf01204715 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013095644
    90 https://doi.org/10.1007/bf01204715
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/bf01261320 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023147320
    93 https://doi.org/10.1007/bf01261320
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/bf02582936 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042921797
    96 https://doi.org/10.1007/bf02582936
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/s00493-008-2231-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015937137
    99 https://doi.org/10.1007/s00493-008-2231-2
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/s12188-016-0172-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1018798184
    102 https://doi.org/10.1007/s12188-016-0172-z
    103 rdf:type schema:CreativeWork
    104 grid-institutes:grid.268446.a schema:alternateName Faculty of Environment and Information Sciences, Yokohama National University, Yokohama, Japan
    105 schema:name Faculty of Environment and Information Sciences, Yokohama National University, Yokohama, Japan
    106 rdf:type schema:Organization
     




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


    ...