A Note on Strong Edge Coloring of Sparse Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-04

AUTHORS

Wei Dong, Rui Li, Bao Gang Xu

ABSTRACT

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ′s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2k. Yang and Zhu [J. Graph Theory, 83, 334–339 (2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4kΔ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ 4kΔ − 2k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most (4k − 1)Δ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ (4k − 1)Δ − 2k + 1. More... »

PAGES

577-582

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10114-018-7186-7

DOI

http://dx.doi.org/10.1007/s10114-018-7186-7

DIMENSIONS

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


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": "Nanjing Xiaozhuang University", 
          "id": "https://www.grid.ac/institutes/grid.440845.9", 
          "name": [
            "School of Information and Engineering, Nanjing Xiaozhuang University, 211171, Nanjing, P. R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dong", 
        "givenName": "Wei", 
        "id": "sg:person.014055474150.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055474150.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Hohai University", 
          "id": "https://www.grid.ac/institutes/grid.257065.3", 
          "name": [
            "Department of Mathematics, College of Science Hohai University, 211100, Nanjing, P. R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Rui", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Nanjing Normal University", 
          "id": "https://www.grid.ac/institutes/grid.260474.3", 
          "name": [
            "School of Mathematical Sciences, Nanjing Normal University, 210023, Nanjing, P. R. China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Bao Gang", 
        "id": "sg:person.07746444521.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07746444521.34"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/jgt.21999", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006385024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jctb.1997.1724", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008944068"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(92)90678-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012603891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2006.03.053", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027702801"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0016-0032(65)90340-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039405520"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.3190170204", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041029219"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.21646", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042289883"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00373-014-1478-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043330812", 
          "https://doi.org/10.1007/s00373-014-1478-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(88)90196-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046057006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(88)90196-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046057006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2014.10.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048286574"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2014.04.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053233731"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109706182", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-84628-970-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109706182", 
          "https://doi.org/10.1007/978-1-84628-970-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-84628-970-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109706182", 
          "https://doi.org/10.1007/978-1-84628-970-5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index \u03c7\u2032s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree \u0394 and maximum average degree at most 2k. Yang and Zhu [J. Graph Theory, 83, 334\u2013339 (2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4k\u0394 \u2212 2k in the square of the line graph of G, implying that \u03c7\u2032s(G) \u2264 4k\u0394 \u2212 2k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most (4k \u2212 1)\u0394 \u2212 2k in the square of the line graph of G, implying that \u03c7\u2032s(G) \u2264 (4k \u2212 1)\u0394 \u2212 2k + 1.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10114-018-7186-7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1040372", 
        "issn": [
          "1439-8516", 
          "1439-7617"
        ], 
        "name": "Acta Mathematica Sinica, English Series", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "35"
      }
    ], 
    "name": "A Note on Strong Edge Coloring of Sparse Graphs", 
    "pagination": "577-582", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b8484b634741d2406c38e833da471d50017307a8eec0e276a6bdb6f5c00ec5cc"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10114-018-7186-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110535640"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10114-018-7186-7", 
      "https://app.dimensions.ai/details/publication/pub.1110535640"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:04", 
    "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/0000000366_0000000366/records_112051_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10114-018-7186-7"
  }
]
 

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/s10114-018-7186-7'

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/s10114-018-7186-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10114-018-7186-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10114-018-7186-7'


 

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

120 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10114-018-7186-7 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N957969aead9646b38db45cf8e0fffeed
4 schema:citation sg:pub.10.1007/978-1-84628-970-5
5 sg:pub.10.1007/s00373-014-1478-1
6 https://app.dimensions.ai/details/publication/pub.1109706182
7 https://doi.org/10.1002/jgt.21646
8 https://doi.org/10.1002/jgt.21999
9 https://doi.org/10.1002/jgt.3190170204
10 https://doi.org/10.1006/jctb.1997.1724
11 https://doi.org/10.1016/0012-365x(88)90196-3
12 https://doi.org/10.1016/0012-365x(92)90678-9
13 https://doi.org/10.1016/0016-0032(65)90340-6
14 https://doi.org/10.1016/j.disc.2006.03.053
15 https://doi.org/10.1016/j.disc.2014.04.016
16 https://doi.org/10.1016/j.ipl.2014.10.006
17 schema:datePublished 2019-04
18 schema:datePublishedReg 2019-04-01
19 schema:description A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ′s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2k. Yang and Zhu [J. Graph Theory, 83, 334–339 (2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4kΔ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ 4kΔ − 2k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most (4k − 1)Δ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ (4k − 1)Δ − 2k + 1.
20 schema:genre research_article
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N24d77e0660d34a639df824b5710eb02a
24 N273d2a8efd9f4c929e640566f5b6c5f2
25 sg:journal.1040372
26 schema:name A Note on Strong Edge Coloring of Sparse Graphs
27 schema:pagination 577-582
28 schema:productId N231344332d0f4f058539d6f932bdfc81
29 N35205b46c5ef4c82a664ff21b502787a
30 N722fa08320e345e7a9ece3e82cf445c5
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110535640
32 https://doi.org/10.1007/s10114-018-7186-7
33 schema:sdDatePublished 2019-04-11T13:04
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nfe5004dd808947fbaf3f2fa65b35941b
36 schema:url https://link.springer.com/10.1007%2Fs10114-018-7186-7
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N0b8fc162b27e4ccda7ed41203aedeb08 schema:affiliation https://www.grid.ac/institutes/grid.257065.3
41 schema:familyName Li
42 schema:givenName Rui
43 rdf:type schema:Person
44 N231344332d0f4f058539d6f932bdfc81 schema:name doi
45 schema:value 10.1007/s10114-018-7186-7
46 rdf:type schema:PropertyValue
47 N24d77e0660d34a639df824b5710eb02a schema:issueNumber 4
48 rdf:type schema:PublicationIssue
49 N273d2a8efd9f4c929e640566f5b6c5f2 schema:volumeNumber 35
50 rdf:type schema:PublicationVolume
51 N35205b46c5ef4c82a664ff21b502787a schema:name readcube_id
52 schema:value b8484b634741d2406c38e833da471d50017307a8eec0e276a6bdb6f5c00ec5cc
53 rdf:type schema:PropertyValue
54 N3682df28c908487fb5df27371b42f21f rdf:first N0b8fc162b27e4ccda7ed41203aedeb08
55 rdf:rest N6157e22919e44e42ad5a40cc7ff34d2a
56 N6157e22919e44e42ad5a40cc7ff34d2a rdf:first sg:person.07746444521.34
57 rdf:rest rdf:nil
58 N722fa08320e345e7a9ece3e82cf445c5 schema:name dimensions_id
59 schema:value pub.1110535640
60 rdf:type schema:PropertyValue
61 N957969aead9646b38db45cf8e0fffeed rdf:first sg:person.014055474150.78
62 rdf:rest N3682df28c908487fb5df27371b42f21f
63 Nfe5004dd808947fbaf3f2fa65b35941b schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
66 schema:name Mathematical Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
69 schema:name Pure Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1040372 schema:issn 1439-7617
72 1439-8516
73 schema:name Acta Mathematica Sinica, English Series
74 rdf:type schema:Periodical
75 sg:person.014055474150.78 schema:affiliation https://www.grid.ac/institutes/grid.440845.9
76 schema:familyName Dong
77 schema:givenName Wei
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055474150.78
79 rdf:type schema:Person
80 sg:person.07746444521.34 schema:affiliation https://www.grid.ac/institutes/grid.260474.3
81 schema:familyName Xu
82 schema:givenName Bao Gang
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07746444521.34
84 rdf:type schema:Person
85 sg:pub.10.1007/978-1-84628-970-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109706182
86 https://doi.org/10.1007/978-1-84628-970-5
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/s00373-014-1478-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043330812
89 https://doi.org/10.1007/s00373-014-1478-1
90 rdf:type schema:CreativeWork
91 https://app.dimensions.ai/details/publication/pub.1109706182 schema:CreativeWork
92 https://doi.org/10.1002/jgt.21646 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042289883
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1002/jgt.21999 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006385024
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1002/jgt.3190170204 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041029219
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1006/jctb.1997.1724 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008944068
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0012-365x(88)90196-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046057006
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0012-365x(92)90678-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012603891
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0016-0032(65)90340-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039405520
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/j.disc.2006.03.053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027702801
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/j.disc.2014.04.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053233731
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/j.ipl.2014.10.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048286574
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.257065.3 schema:alternateName Hohai University
113 schema:name Department of Mathematics, College of Science Hohai University, 211100, Nanjing, P. R. China
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.260474.3 schema:alternateName Nanjing Normal University
116 schema:name School of Mathematical Sciences, Nanjing Normal University, 210023, Nanjing, P. R. China
117 rdf:type schema:Organization
118 https://www.grid.ac/institutes/grid.440845.9 schema:alternateName Nanjing Xiaozhuang University
119 schema:name School of Information and Engineering, Nanjing Xiaozhuang University, 211171, Nanjing, P. R. China
120 rdf:type schema:Organization
 




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


...