On the Density of C7-Critical Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-02-18

AUTHORS

Luke Postle, Evelyne Smith-Roberge

ABSTRACT

In 1959, Grötzsch [5] famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to C3). A natural generalization of this is the following conjecture: for every positive integer t, every planar graph of girth at least 4t admits a homomorphism to C2t+1. This is in fact the planar dual of a well-known conjecture of Jaeger [7] which states that every 4t-edge-connected graph admits a modulo (2t + 1)-orientation. Though Jaeger’s original conjecture was disproved in [6], Lovász et al. [10] showed that every 6t-edge connected graph admits a modolo (2t + 1)-flow. The latter result implies that every planar graph of girth at least 6t admits a homomorphism to C2t+1. We improve upon this in the t = 3 case, by showing that every planar graph of girth at least 16 admits a homomorphism to C7. We obtain this through a more general result regarding the density of C7-critical graphs: if G is a C7-critical graph with G ∉ {C3, C5}, then e(G)≥17v(G)−215\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e(G) \ge {{17v(G) - 2} \over {15}}$$\end{document}. More... »

PAGES

253-300

References to SciGraph publications

  • 1951-12. Note on the colouring of graphs in MATHEMATISCHE ZEITSCHRIFT
  • 2016-10-17. Density of 5/2-critical graphs in COMBINATORICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-020-4177-y

    DOI

    http://dx.doi.org/10.1007/s00493-020-4177-y

    DIMENSIONS

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


    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": "Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada", 
              "id": "http://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Postle", 
            "givenName": "Luke", 
            "id": "sg:person.014105416225.80", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014105416225.80"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada", 
              "id": "http://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Smith-Roberge", 
            "givenName": "Evelyne", 
            "id": "sg:person.01044204717.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01044204717.19"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00493-016-3356-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028596117", 
              "https://doi.org/10.1007/s00493-016-3356-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01238034", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048012643", 
              "https://doi.org/10.1007/bf01238034"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-02-18", 
        "datePublishedReg": "2022-02-18", 
        "description": "In 1959, Gr\u00f6tzsch [5] famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to C3). A natural generalization of this is the following conjecture: for every positive integer t, every planar graph of girth at least 4t admits a homomorphism to C2t+1. This is in fact the planar dual of a well-known conjecture of Jaeger [7] which states that every 4t-edge-connected graph admits a modulo (2t + 1)-orientation. Though Jaeger\u2019s original conjecture was disproved in [6], Lov\u00e1sz et al. [10] showed that every 6t-edge connected graph admits a modolo (2t + 1)-flow. The latter result implies that every planar graph of girth at least 6t admits a homomorphism to C2t+1. We improve upon this in the t = 3 case, by showing that every planar graph of girth at least 16 admits a homomorphism to C7. We obtain this through a more general result regarding the density of C7-critical graphs: if G is a C7-critical graph with G \u2209 {C3, C5}, then e(G)\u226517v(G)\u2212215\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$e(G) \\ge {{17v(G) - 2} \\over {15}}$$\\end{document}.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-020-4177-y", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "42"
          }
        ], 
        "keywords": [
          "planar graphs", 
          "original conjecture", 
          "positive integer t", 
          "natural generalization", 
          "general results", 
          "homomorphism", 
          "connected graph", 
          "graph", 
          "conjecture", 
          "integer t", 
          "Lov\u00e1sz et al", 
          "Gr\u00f6tzsch", 
          "et al", 
          "latter result", 
          "generalization", 
          "modulo", 
          "admits", 
          "density", 
          "girth", 
          "planar", 
          "Jaeger", 
          "flow", 
          "results", 
          "al", 
          "fact", 
          "cases", 
          "orientation", 
          "C7", 
          "C3", 
          "C5"
        ], 
        "name": "On the Density of C7-Critical Graphs", 
        "pagination": "253-300", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1145698743"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-020-4177-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-020-4177-y", 
          "https://app.dimensions.ai/details/publication/pub.1145698743"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:50", 
        "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_952.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-020-4177-y"
      }
    ]
     

    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-020-4177-y'

    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-020-4177-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4177-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4177-y'


     

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

    102 TRIPLES      21 PREDICATES      56 URIs      46 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-020-4177-y schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nc6627b92607241248b00d7fe0fcf4088
    4 schema:citation sg:pub.10.1007/bf01238034
    5 sg:pub.10.1007/s00493-016-3356-3
    6 schema:datePublished 2022-02-18
    7 schema:datePublishedReg 2022-02-18
    8 schema:description In 1959, Grötzsch [5] famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to C3). A natural generalization of this is the following conjecture: for every positive integer t, every planar graph of girth at least 4t admits a homomorphism to C2t+1. This is in fact the planar dual of a well-known conjecture of Jaeger [7] which states that every 4t-edge-connected graph admits a modulo (2t + 1)-orientation. Though Jaeger’s original conjecture was disproved in [6], Lovász et al. [10] showed that every 6t-edge connected graph admits a modolo (2t + 1)-flow. The latter result implies that every planar graph of girth at least 6t admits a homomorphism to C2t+1. We improve upon this in the t = 3 case, by showing that every planar graph of girth at least 16 admits a homomorphism to C7. We obtain this through a more general result regarding the density of C7-critical graphs: if G is a C7-critical graph with G ∉ {C3, C5}, then e(G)≥17v(G)−215\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e(G) \ge {{17v(G) - 2} \over {15}}$$\end{document}.
    9 schema:genre article
    10 schema:isAccessibleForFree false
    11 schema:isPartOf N7c2dcb02145e4c5193420b43d2416153
    12 Na2589418f21a41559fe3488f18ef6c37
    13 sg:journal.1136493
    14 schema:keywords C3
    15 C5
    16 C7
    17 Grötzsch
    18 Jaeger
    19 Lovász et al
    20 admits
    21 al
    22 cases
    23 conjecture
    24 connected graph
    25 density
    26 et al
    27 fact
    28 flow
    29 general results
    30 generalization
    31 girth
    32 graph
    33 homomorphism
    34 integer t
    35 latter result
    36 modulo
    37 natural generalization
    38 orientation
    39 original conjecture
    40 planar
    41 planar graphs
    42 positive integer t
    43 results
    44 schema:name On the Density of C7-Critical Graphs
    45 schema:pagination 253-300
    46 schema:productId N28aa28c03b074358aee9f846a8cb1216
    47 N6e46435964814841997943d641f4dafb
    48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1145698743
    49 https://doi.org/10.1007/s00493-020-4177-y
    50 schema:sdDatePublished 2022-10-01T06:50
    51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    52 schema:sdPublisher Na6d6ed6c0f5a4e1e8f1931818c75feea
    53 schema:url https://doi.org/10.1007/s00493-020-4177-y
    54 sgo:license sg:explorer/license/
    55 sgo:sdDataset articles
    56 rdf:type schema:ScholarlyArticle
    57 N28aa28c03b074358aee9f846a8cb1216 schema:name dimensions_id
    58 schema:value pub.1145698743
    59 rdf:type schema:PropertyValue
    60 N6b7fbc9ddb6c4dd0b5f27fd7472e30b5 rdf:first sg:person.01044204717.19
    61 rdf:rest rdf:nil
    62 N6e46435964814841997943d641f4dafb schema:name doi
    63 schema:value 10.1007/s00493-020-4177-y
    64 rdf:type schema:PropertyValue
    65 N7c2dcb02145e4c5193420b43d2416153 schema:issueNumber 2
    66 rdf:type schema:PublicationIssue
    67 Na2589418f21a41559fe3488f18ef6c37 schema:volumeNumber 42
    68 rdf:type schema:PublicationVolume
    69 Na6d6ed6c0f5a4e1e8f1931818c75feea schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 Nc6627b92607241248b00d7fe0fcf4088 rdf:first sg:person.014105416225.80
    72 rdf:rest N6b7fbc9ddb6c4dd0b5f27fd7472e30b5
    73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Mathematical Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Pure Mathematics
    78 rdf:type schema:DefinedTerm
    79 sg:journal.1136493 schema:issn 0209-9683
    80 1439-6912
    81 schema:name Combinatorica
    82 schema:publisher Springer Nature
    83 rdf:type schema:Periodical
    84 sg:person.01044204717.19 schema:affiliation grid-institutes:grid.46078.3d
    85 schema:familyName Smith-Roberge
    86 schema:givenName Evelyne
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01044204717.19
    88 rdf:type schema:Person
    89 sg:person.014105416225.80 schema:affiliation grid-institutes:grid.46078.3d
    90 schema:familyName Postle
    91 schema:givenName Luke
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014105416225.80
    93 rdf:type schema:Person
    94 sg:pub.10.1007/bf01238034 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048012643
    95 https://doi.org/10.1007/bf01238034
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/s00493-016-3356-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028596117
    98 https://doi.org/10.1007/s00493-016-3356-3
    99 rdf:type schema:CreativeWork
    100 grid-institutes:grid.46078.3d schema:alternateName Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
    101 schema:name Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
    102 rdf:type schema:Organization
     




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


    ...