View in EDS

A nonplanar critical multigraph that achieves Goldberg's bound.

Saved in:
Bibliographic Details
Title: A nonplanar critical multigraph that achieves Goldberg's bound.
Authors: Wang, Chunxiang1 (AUTHOR) wcxiang@ccnu.edu.cn, Wang, Shujing1 (AUTHOR) wang06021@126.com
Source: Discrete Applied Mathematics. Jun2026, Vol. 386, p381-387. 7p.
Subjects: Multigraph, Goldberg, Jeffrey, 1965-, Planar graphs, Graph theory, Graph coloring
Abstract: Let G be a multigraph with maximum degree Δ (G) and odd girth g o (G). Denote by χ ′ (G) the chromatic index of G. Goldberg showed that χ ′ (G) ≤ Δ (G) + 1 + Δ (G) − 2 g o (G) − 1 . For given Δ and odd number g o , let GO (Δ , g o) ≔ { G : Δ (G) = Δ , g o (G) = g o , χ ′ (G) = Δ + 1 + Δ − 2 g o − 1 }. Stiebitz, Scheide, Toft, and Favrholdt in their book conjecture that if G ∈ GO (Δ , g o) , then G contains a ring graph R ∈ GO (Δ , g o) , where ring graph is obtained from a cycle by duplicating some edges. A graph G is critical if χ ′ (H) < χ ′ (G) for any proper subgraph H of G. In this paper, we present a characterization of critical graphs by using near-perfect matchings. Furthermore, we provide some nonplanar critical graphs that achieve Goldberg's bound, which implies that there exists graph G ∈ GO (Δ , g o) , such that for any subgraph H of G with H ∈ GO (Δ , g o) , H is neither a ring graph nor a planar graph. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 192967419
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A nonplanar critical multigraph that achieves Goldberg&#39;s bound.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Wang%2C+Chunxiang%22&quot;&gt;Wang, Chunxiang&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; wcxiang@ccnu.edu.cn&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Wang%2C+Shujing%22&quot;&gt;Wang, Shujing&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; wang06021@126.com&lt;/i&gt;
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22Discrete+Applied+Mathematics%22&quot;&gt;Discrete Applied Mathematics&lt;/searchLink&gt;. Jun2026, Vol. 386, p381-387. 7p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Multigraph%22&quot;&gt;Multigraph&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Goldberg%2C+Jeffrey%2C+1965-%22&quot;&gt;Goldberg, Jeffrey, 1965-&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Planar+graphs%22&quot;&gt;Planar graphs&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Graph+theory%22&quot;&gt;Graph theory&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Graph+coloring%22&quot;&gt;Graph coloring&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Let G be a multigraph with maximum degree Δ (G) and odd girth g o (G). Denote by χ ′ (G) the chromatic index of G. Goldberg showed that χ ′ (G) ≤ Δ (G) + 1 + Δ (G) − 2 g o (G) − 1 . For given Δ and odd number g o , let GO (Δ , g o) ≔ { G : Δ (G) = Δ , g o (G) = g o , χ ′ (G) = Δ + 1 + Δ − 2 g o − 1 }. Stiebitz, Scheide, Toft, and Favrholdt in their book conjecture that if G ∈ GO (Δ , g o) , then G contains a ring graph R ∈ GO (Δ , g o) , where ring graph is obtained from a cycle by duplicating some edges. A graph G is critical if χ ′ (H) &lt; χ ′ (G) for any proper subgraph H of G. In this paper, we present a characterization of critical graphs by using near-perfect matchings. Furthermore, we provide some nonplanar critical graphs that achieve Goldberg&#39;s bound, which implies that there exists graph G ∈ GO (Δ , g o) , such that for any subgraph H of G with H ∈ GO (Δ , g o) , H is neither a ring graph nor a planar graph. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder&#39;s express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192967419
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2026.02.053
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 7
        StartPage: 381
    Subjects:
      – SubjectFull: Multigraph
        Type: general
      – SubjectFull: Goldberg, Jeffrey, 1965-
        Type: general
      – SubjectFull: Planar graphs
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Graph coloring
        Type: general
    Titles:
      – TitleFull: A nonplanar critical multigraph that achieves Goldberg's bound.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Wang, Chunxiang
      – PersonEntity:
          Name:
            NameFull: Wang, Shujing
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 06
              Text: Jun2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 386
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1