An Erdős-Gallai type theorem for vertex colored graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-09

AUTHORS

Nika Salia, Casey Tompkins, Oscar Zamora

ABSTRACT

While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k+1 with end vertices of different colors has at most 2kn edges. We show that Erdős and Gallai’s original sharp upper bound of kn holds for their problem as well. We also introduce a version of this problem for trees and present a generalization of the Erdős-Sós conjecture. More... »

PAGES

1-6

References to SciGraph publications

  • 2012-03. 3-uniform hypergraphs avoiding a given odd cycle in COMBINATORICA
  • 1959-09. On maximal paths and circuits of graphs in ACTA MATHEMATICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00373-019-02026-1

    DOI

    http://dx.doi.org/10.1007/s00373-019-02026-1

    DIMENSIONS

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


    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": "MTA Alfr\u00e9d R\u00e9nyi Institute of Mathematics", 
              "id": "https://www.grid.ac/institutes/grid.423969.3", 
              "name": [
                "Central European University, Budapest, Hungary", 
                "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Salia", 
            "givenName": "Nika", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "MTA Alfr\u00e9d R\u00e9nyi Institute of Mathematics", 
              "id": "https://www.grid.ac/institutes/grid.423969.3", 
              "name": [
                "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tompkins", 
            "givenName": "Casey", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Costa Rica", 
              "id": "https://www.grid.ac/institutes/grid.412889.e", 
              "name": [
                "Central European University, Budapest, Hungary", 
                "Universidad de Costa Rica, San Jos\u00e9, Costa Rica"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zamora", 
            "givenName": "Oscar", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02024498", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003517280", 
              "https://doi.org/10.1007/bf02024498"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02024498", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003517280", 
              "https://doi.org/10.1007/bf02024498"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0963548314000601", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005852579"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-012-2584-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012406838", 
              "https://doi.org/10.1007/s00493-012-2584-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.20083", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037704523"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-09", 
        "datePublishedReg": "2019-03-09", 
        "description": "While investigating odd-cycle free hypergraphs, Gy\u0151ri and Lemons introduced a colored version of the classical theorem of Erd\u0151s and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k+1 with end vertices of different colors has at most 2kn edges. We show that Erd\u0151s and Gallai\u2019s original sharp upper bound of kn holds for their problem as well. We also introduce a version of this problem for trees and present a generalization of the Erd\u0151s-S\u00f3s conjecture.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00373-019-02026-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136071", 
            "issn": [
              "0911-0119", 
              "1435-5914"
            ], 
            "name": "Graphs and Combinatorics", 
            "type": "Periodical"
          }
        ], 
        "name": "An Erd\u0151s-Gallai type theorem for vertex colored graphs", 
        "pagination": "1-6", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "790a2ae50a5121191fdf7755d44cac65e2562c75aa293884e53df879835f8db9"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00373-019-02026-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112672861"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00373-019-02026-1", 
          "https://app.dimensions.ai/details/publication/pub.1112672861"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:21", 
        "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_11728_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02026-1"
      }
    ]
     

    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-02026-1'

    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-02026-1'

    Turtle is a human-readable linked data format.

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

    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-02026-1'


     

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

    85 TRIPLES      21 PREDICATES      28 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00373-019-02026-1 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N3f1d733ad84941a28e8b6b427cc7760a
    4 schema:citation sg:pub.10.1007/bf02024498
    5 sg:pub.10.1007/s00493-012-2584-4
    6 https://doi.org/10.1002/jgt.20083
    7 https://doi.org/10.1017/s0963548314000601
    8 schema:datePublished 2019-03-09
    9 schema:datePublishedReg 2019-03-09
    10 schema:description While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on Pk-free graphs. They proved that any graph G with a proper vertex coloring and no path of length 2k+1 with end vertices of different colors has at most 2kn edges. We show that Erdős and Gallai’s original sharp upper bound of kn holds for their problem as well. We also introduce a version of this problem for trees and present a generalization of the Erdős-Sós conjecture.
    11 schema:genre research_article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf sg:journal.1136071
    15 schema:name An Erdős-Gallai type theorem for vertex colored graphs
    16 schema:pagination 1-6
    17 schema:productId N5a22c58744074c2e8d9674d355a53f8e
    18 N97bcab4a41e94422b3ece366fc7c24a7
    19 Nd82a81d4ead147c8a1bede843ccbc0cf
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112672861
    21 https://doi.org/10.1007/s00373-019-02026-1
    22 schema:sdDatePublished 2019-04-11T11:21
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N6bb6a17132074e77ac495676cb0e54ce
    25 schema:url https://link.springer.com/10.1007%2Fs00373-019-02026-1
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset articles
    28 rdf:type schema:ScholarlyArticle
    29 N18fcf704b1f94fe2b0f709dfaf92df76 rdf:first N209c6d14dedb4b8f9f5687a0ed4cc856
    30 rdf:rest N714a670ba99d4c71893f99f1f0015df9
    31 N209c6d14dedb4b8f9f5687a0ed4cc856 schema:affiliation https://www.grid.ac/institutes/grid.423969.3
    32 schema:familyName Tompkins
    33 schema:givenName Casey
    34 rdf:type schema:Person
    35 N3f1d733ad84941a28e8b6b427cc7760a rdf:first N4e130b23385c413aa48ec6ac53e02c4c
    36 rdf:rest N18fcf704b1f94fe2b0f709dfaf92df76
    37 N4e130b23385c413aa48ec6ac53e02c4c schema:affiliation https://www.grid.ac/institutes/grid.423969.3
    38 schema:familyName Salia
    39 schema:givenName Nika
    40 rdf:type schema:Person
    41 N53c6bc68272f4d64807464059a6a0b44 schema:affiliation https://www.grid.ac/institutes/grid.412889.e
    42 schema:familyName Zamora
    43 schema:givenName Oscar
    44 rdf:type schema:Person
    45 N5a22c58744074c2e8d9674d355a53f8e schema:name readcube_id
    46 schema:value 790a2ae50a5121191fdf7755d44cac65e2562c75aa293884e53df879835f8db9
    47 rdf:type schema:PropertyValue
    48 N6bb6a17132074e77ac495676cb0e54ce schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 N714a670ba99d4c71893f99f1f0015df9 rdf:first N53c6bc68272f4d64807464059a6a0b44
    51 rdf:rest rdf:nil
    52 N97bcab4a41e94422b3ece366fc7c24a7 schema:name doi
    53 schema:value 10.1007/s00373-019-02026-1
    54 rdf:type schema:PropertyValue
    55 Nd82a81d4ead147c8a1bede843ccbc0cf schema:name dimensions_id
    56 schema:value pub.1112672861
    57 rdf:type schema:PropertyValue
    58 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Mathematical Sciences
    60 rdf:type schema:DefinedTerm
    61 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Pure Mathematics
    63 rdf:type schema:DefinedTerm
    64 sg:journal.1136071 schema:issn 0911-0119
    65 1435-5914
    66 schema:name Graphs and Combinatorics
    67 rdf:type schema:Periodical
    68 sg:pub.10.1007/bf02024498 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003517280
    69 https://doi.org/10.1007/bf02024498
    70 rdf:type schema:CreativeWork
    71 sg:pub.10.1007/s00493-012-2584-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012406838
    72 https://doi.org/10.1007/s00493-012-2584-4
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1002/jgt.20083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037704523
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1017/s0963548314000601 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005852579
    77 rdf:type schema:CreativeWork
    78 https://www.grid.ac/institutes/grid.412889.e schema:alternateName University of Costa Rica
    79 schema:name Central European University, Budapest, Hungary
    80 Universidad de Costa Rica, San José, Costa Rica
    81 rdf:type schema:Organization
    82 https://www.grid.ac/institutes/grid.423969.3 schema:alternateName MTA Alfréd Rényi Institute of Mathematics
    83 schema:name Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary
    84 Central European University, Budapest, Hungary
    85 rdf:type schema:Organization
     




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


    ...