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

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 N21145bc46597448c849874e646672724
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 N6f3062f173d5473f8944ed6bfc801a49
24 N8374bc05697e40828c44fbaa2953a7cf
25 sg:journal.1040372
26 schema:name A Note on Strong Edge Coloring of Sparse Graphs
27 schema:pagination 577-582
28 schema:productId N99578bff31b1440b9433536fbd47c83d
29 Nbb95bf1aeaf14097bdbc356551e8026e
30 Ncc5d6ccf38364fa9ad365b66f96bcb6b
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 N6888955ef5134cb09d6d27add1abb54e
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 N21145bc46597448c849874e646672724 rdf:first sg:person.014055474150.78
41 rdf:rest N94fca938e3784f438dfa8cf629254918
42 N6888955ef5134cb09d6d27add1abb54e schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N6f3062f173d5473f8944ed6bfc801a49 schema:volumeNumber 35
45 rdf:type schema:PublicationVolume
46 N8374bc05697e40828c44fbaa2953a7cf schema:issueNumber 4
47 rdf:type schema:PublicationIssue
48 N93169fe31d2e4e2ebf1ac6a778dbcacd rdf:first sg:person.07746444521.34
49 rdf:rest rdf:nil
50 N94fca938e3784f438dfa8cf629254918 rdf:first Nd5dda182b923468a8150401c755cbc1b
51 rdf:rest N93169fe31d2e4e2ebf1ac6a778dbcacd
52 N99578bff31b1440b9433536fbd47c83d schema:name dimensions_id
53 schema:value pub.1110535640
54 rdf:type schema:PropertyValue
55 Nbb95bf1aeaf14097bdbc356551e8026e schema:name readcube_id
56 schema:value b8484b634741d2406c38e833da471d50017307a8eec0e276a6bdb6f5c00ec5cc
57 rdf:type schema:PropertyValue
58 Ncc5d6ccf38364fa9ad365b66f96bcb6b schema:name doi
59 schema:value 10.1007/s10114-018-7186-7
60 rdf:type schema:PropertyValue
61 Nd5dda182b923468a8150401c755cbc1b schema:affiliation https://www.grid.ac/institutes/grid.257065.3
62 schema:familyName Li
63 schema:givenName Rui
64 rdf:type schema:Person
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)


...