Strong Chromatic Index Of Planar Graphs With Large Girth
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6....
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1763 |
| _version_ | 1797757743691464704 |
|---|---|
| author | Jennhwa Chang Gerard Montassier Mickael Pêche Arnaud Raspaud André |
| author_facet | Jennhwa Chang Gerard Montassier Mickael Pêche Arnaud Raspaud André |
| author_sort | Jennhwa Chang Gerard |
| collection | DOAJ |
| description | Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6. |
| first_indexed | 2024-03-12T18:19:03Z |
| format | Article |
| id | doaj.art-3e41abf6277a4a8db9fd025be8caea2b |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:03Z |
| publishDate | 2014-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-3e41abf6277a4a8db9fd025be8caea2b2023-08-02T08:59:11ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-11-0134472373310.7151/dmgt.1763dmgt.1763Strong Chromatic Index Of Planar Graphs With Large GirthJennhwa Chang Gerard0Montassier Mickael1Pêche Arnaud2Raspaud André3Department of Mathematics/Taida Institute for Mathematical Sciences National Taiwan University, Taipei 10617, Taiwan/National Center for Theoretical Sciences, Taipei Office, TaiwanUniversit Montpellier 2, CNRS-LIRMM, UMR5506 161 rue Ada, 34095 Montpellier Cedex 5, FranceLaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, FranceLaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, FranceLet Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.https://doi.org/10.7151/dmgt.1763planar graphsedge coloring2-distance coloringstrong edgecoloring. |
| spellingShingle | Jennhwa Chang Gerard Montassier Mickael Pêche Arnaud Raspaud André Strong Chromatic Index Of Planar Graphs With Large Girth Discussiones Mathematicae Graph Theory planar graphs edge coloring 2-distance coloring strong edgecoloring. |
| title | Strong Chromatic Index Of Planar Graphs With Large Girth |
| title_full | Strong Chromatic Index Of Planar Graphs With Large Girth |
| title_fullStr | Strong Chromatic Index Of Planar Graphs With Large Girth |
| title_full_unstemmed | Strong Chromatic Index Of Planar Graphs With Large Girth |
| title_short | Strong Chromatic Index Of Planar Graphs With Large Girth |
| title_sort | strong chromatic index of planar graphs with large girth |
| topic | planar graphs edge coloring 2-distance coloring strong edgecoloring. |
| url | https://doi.org/10.7151/dmgt.1763 |
| work_keys_str_mv | AT jennhwachanggerard strongchromaticindexofplanargraphswithlargegirth AT montassiermickael strongchromaticindexofplanargraphswithlargegirth AT pechearnaud strongchromaticindexofplanargraphswithlargegirth AT raspaudandre strongchromaticindexofplanargraphswithlargegirth |