pith. sign in

arxiv: 2509.17069 · v2 · submitted 2025-09-21 · 🧮 math.CO

Computational results on semistrong edge coloring of graphs

Yuquan Lin , Wensong Lin This is my paper

Pith reviewed 2026-05-18 14:47 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C85
keywords semistrong edge coloringchromatic indexNP-completenesstreesgraph coloringmatchingcomputational complexity
0
0 comments X

The pith

Deciding semistrong edge colorability is polynomial-time solvable for two colors or fewer and NP-complete for three or more, with an exact polynomial algorithm for trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the decision problem of whether a graph admits a semistrong edge coloring with k colors belongs to P when k is at most 2 and is NP-complete when k is at least 3. It further supplies a separate polynomial-time procedure that computes the exact semistrong chromatic index on any tree. A reader would care because semistrong edge coloring models channel scheduling in wireless networks, so the results mark the precise threshold at which optimal schedules can be found by efficient algorithms versus when one must accept heuristic or approximate methods.

Core claim

We prove that the problem of determining whether a graph G has a semistrong edge coloring with k colors is polynomial-time solvable for k ≤ 2 and is NP-complete for k ≥ 3. For trees, we develop a polynomial-time algorithm to determine the semistrong chromatic index exactly.

What carries the argument

A semistrong matching: a matching M in which every edge of M is incident to a degree-1 vertex in the subgraph induced by the vertices covered by M.

If this is right

  • The exact semistrong chromatic index of every tree can be computed in polynomial time.
  • For any fixed k ≥ 3 there is no polynomial-time algorithm for deciding semistrong k-edge-colorability on general graphs unless P equals NP.
  • The complexity threshold lies exactly between two and three colors for the decision version on arbitrary graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The tree algorithm may extend to graphs of bounded treewidth or other recursively structured classes.
  • Approximation algorithms or fixed-parameter algorithms for the semistrong chromatic index could be developed for general graphs where exact computation is intractable.

Load-bearing premise

The reduction showing NP-completeness for k ≥ 3 correctly forces each color class to obey the semistrong incidence condition without introducing extraneous edges or vertices that would change the yes/no outcome.

What would settle it

A concrete polynomial-time algorithm that decides whether any graph admits a semistrong edge coloring with three colors, or a specific graph instance on which the claimed reduction fails to preserve the semistrong property.

Figures

Figures reproduced from arXiv: 2509.17069 by Wensong Lin, Yuquan Lin.

Figure 1
Figure 1. Figure 1: Different types of matching (heavy edges), from weaker to stronger. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Different types of edge coloring (proper, uniquely restricted, semistrong, strong). [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The graph Bk[u, v]. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 6
Figure 6. Figure 6: A semstrong 4-edge-coloring of [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The illustration of various subtrees of Tr. For any two vertices x, y ∈ V (Tv), let dTv (x, y) denote the distance between x and y in Tv. For an edge xy ∈ E(Tv), define dTv (xy, v) = max{dTv (x, v), dTv (y, v)}. If dTv (xy, v) = i, then we call xy an ith-generation edge descended from v (we usually abbreviate it as ith-generation edge in the absence of confusion). Assume that Tv is semistrongly ∆-edge-colo… view at source ↗
Figure 8
Figure 8. Figure 8: The illustration of the first case in Observation [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The illustration of the second case in Observation [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The illustration of the third case in Observation [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
read the original abstract

The semistrong edge coloring, as a relaxation of the well-known strong edge coloring, can be used to model efficient communication scheduling in wireless networks. An edge coloring of a graph $G$ is called \emph{semistrong} if every color class $M$ is a matching such that every edge of $M$ is incident with a vertex of degree 1 in the subgraph of $G$ induced by the endvertices of edges in $M$. The \emph{semistrong chromatic index} $\chi_{ss}'(G)$ of $G$ is the minimum number of colors required for a semistrong edge coloring. In this paper, we prove that the problem of determining whether a graph $G$ has a semistrong edge coloring with $k$ colors is polynomial-time solvable for $k\le2$ and is NP-complete for $k\ge3$. For trees, we develop a polynomial-time algorithm to determine the semistrong chromatic index exactly.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper studies semistrong edge coloring, a relaxation of strong edge coloring in which each color class M is a matching such that every edge of M is incident to a degree-1 vertex in the subgraph induced by the 2|M| endpoints of M. It claims to prove that deciding whether a graph admits a semistrong edge coloring with k colors is polynomial-time solvable for k ≤ 2 and NP-complete for each fixed k ≥ 3, and to give a polynomial-time algorithm that computes the exact semistrong chromatic index on trees.

Significance. If the NP-completeness reductions are shown to be correct and the tree algorithm is accompanied by a full correctness proof, the results would provide a clean complexity dichotomy for the decision problem together with an efficient exact method on trees; both would be useful for the study of constrained edge colorings with applications to scheduling.

major comments (1)
  1. [NP-completeness reduction section] The NP-completeness proof for k ≥ 3 (the section presenting the reduction from a known NP-complete problem) must explicitly verify both directions of the equivalence: that every semistrong k-coloring of the constructed graph G' projects to a valid solution of the source instance, and conversely, while ensuring that no gadget edge creates an unintended degree-1 vertex or an extra valid color class that would violate the semistrong condition (every edge in M incident to a deg-1 vertex in G[V(M)]).
minor comments (1)
  1. The abstract would benefit from a one-sentence indication of the source problem used in the reduction and the high-level structure of the tree algorithm.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address the major comment below and will revise the paper to incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [NP-completeness reduction section] The NP-completeness proof for k ≥ 3 (the section presenting the reduction from a known NP-complete problem) must explicitly verify both directions of the equivalence: that every semistrong k-coloring of the constructed graph G' projects to a valid solution of the source instance, and conversely, while ensuring that no gadget edge creates an unintended degree-1 vertex or an extra valid color class that would violate the semistrong condition (every edge in M incident to a deg-1 vertex in G[V(M)]).

    Authors: We agree that a fully rigorous NP-completeness proof requires explicit verification of both directions together with a careful analysis of the gadgets. In the revised manuscript we will expand the relevant section to include: (i) a detailed argument showing that a yes-instance of the source problem yields a semistrong k-coloring of G', (ii) the converse direction proving that any semistrong k-coloring of G' recovers a valid solution of the source instance, and (iii) an explicit check that the chosen gadgets introduce no unintended degree-1 vertices and do not create extra admissible color classes that would violate the semistrong matching condition. These additions will be placed immediately after the construction of G' and before the complexity conclusion. revision: yes

Circularity Check

0 steps flagged

No circularity: direct proofs and algorithms with no self-referential reductions

full rationale

The paper states direct results: polynomial-time solvability for k≤2, NP-completeness for k≥3 via reduction, and an exact polynomial algorithm for trees on the semistrong chromatic index. No equations, fitted parameters, or self-citations appear as load-bearing steps in the abstract or claimed derivation. The NP-completeness claim rests on a standard reduction that must enforce the semistrong matching condition (each color class M has every edge incident to a degree-1 vertex in the induced subgraph), but the paper presents this as an independent proof rather than a renaming or self-definition of inputs. The derivation chain is self-contained against external graph-theoretic benchmarks and does not reduce to its own outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definitions of matchings, induced subgraphs, polynomial-time solvability, and NP-completeness from classical complexity theory. No free parameters, ad-hoc axioms, or new postulated entities are visible in the abstract.

axioms (2)
  • standard math Standard definitions of matchings and induced subgraphs in undirected graphs
    Invoked directly in the definition of semistrong edge coloring given in the abstract.
  • standard math NP-completeness is preserved under polynomial-time reductions
    Implicit in the claim that the decision problem is NP-complete for k≥3.

pith-pipeline@v0.9.0 · 5695 in / 1349 out tokens · 65777 ms · 2026-05-18T14:47:04.980622+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    N. Alon, B. Sudakov, and A. Zaks,Acyclic edge colorings of graphs, Journal of Graph Theory 37(2001), no. 3, 157–167

    work page 2001

  2. [2]

    Alon and A

    N. Alon and A. Zaks,Algorithmic aspects of acyclic edge colorings, Algorithmica32(2002), no. 4, 611–614

    work page 2002

  3. [3]

    Baste, D

    J. Baste, D. Rautenbach, and I. Sau,Uniquely restricted matchings and edge colorings, Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers 43, Springer, 2017, pp. 100–112

    work page 2017

  4. [4]

    Cameron,Induced matchings, Discrete Applied Mathematics24(1989), no

    K. Cameron,Induced matchings, Discrete Applied Mathematics24(1989), no. 1-3, 97–102

    work page 1989

  5. [5]

    Cameron, R

    K. Cameron, R. Sritharan, and Y. Tang,Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics266(2003), no. 1, 133–142

    work page 2003

  6. [6]

    Dabrowski, M

    K.k. Dabrowski, M. Demange, and V.V. Lozin,New results on maximum induced matchings in bipartite graphs and beyond, Theoretical Computer Science478(2013), 33–40

    work page 2013

  7. [7]

    Erd˝ os and J

    P. Erd˝ os and J. Neˇ setˇ ril,Problems, Irregularities of Partitions (G. Hal´ asz and V. T. S´ os, eds.), Springer, Berlin, 1989, pp. 162–163

    work page 1989

  8. [8]

    Fiamˇ cik,Atsiklicheskij khromaticheskij klass grafa, Math

    J. Fiamˇ cik,Atsiklicheskij khromaticheskij klass grafa, Math. Slovaca28(1978), 139–145

    work page 1978

  9. [9]

    Fouquet and J.L

    J.L. Fouquet and J.L. Jolivet,Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combinatoria A16(1983), 141–150. 16

    work page 1983

  10. [10]

    Goddard, S.M

    W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, and R. Laskar,Generalized subgraph- restricted matchings in graphs, Discrete Mathematics293(2005), no. 1-3, 129–138

    work page 2005

  11. [11]

    Golumbic, T

    M.C. Golumbic, T. Hirst, and M. Lewenstein,Uniquely restricted matchings, Algorithmica 31(2001), 139–154

    work page 2001

  12. [12]

    Golumbic and M

    M.C. Golumbic and M. Lewenstein,New results on induced matchings, Discrete Applied Mathematics101(2000), no. 1-3, 157–165

    work page 2000

  13. [13]

    Gupta,Studies in the theory of graphs, Ph.D

    R.G. Gupta,Studies in the theory of graphs, Ph.D. thesis, Tata Institute of Fundamental Research, Bombay, 1967

    work page 1967

  14. [14]

    Gy´ arf´ as and A

    A. Gy´ arf´ as and A. Hubenko,Semistrong edge coloring of graphs, Journal of Graph Theory 49(2005), 39–47

    work page 2005

  15. [15]

    He and W

    D. He and W. Lin,On( s, t)-relaxed strong edge-coloring of graphs, Journal of Combinatorial Optimization33(2017), no. 2, 609–625

    work page 2017

  16. [16]

    Holyer,The NP-completeness of edge colorings, SIAM Journal on Computing10(1981), 718–720

    I. Holyer,The NP-completeness of edge colorings, SIAM Journal on Computing10(1981), 718–720

    work page 1981

  17. [17]

    Joos,Induced matchings in graphs of bounded maximum degree, SIAM Journal on Discrete Mathematics30(2016), no

    F. Joos,Induced matchings in graphs of bounded maximum degree, SIAM Journal on Discrete Mathematics30(2016), no. 3, 1876–1882

    work page 2016

  18. [18]

    Kanj, M.J

    I. Kanj, M.J. Pelsmajer, M. Schaefer, and G. Xia,On the induced matching problem, Journal of Computer and System Sciences77(2011), no. 6, 1058–1070

    work page 2011

  19. [19]

    Leven and Z

    D. Leven and Z. Galil,NP completeness of finding the chromatic index of regular graphs, Journal of Algorithms4(1983), 35–44

    work page 1983

  20. [20]

    Luˇ zar, M

    B. Luˇ zar, M. Mockovˇ ciakov´ a, and R. Sot´ ak,Revisiting semistrong edge-coloring of graphs, Journal of Graph Theory105(2024), no. 4, 612–632

    work page 2024

  21. [21]

    Mahdian,On the computational complexity of strong edge-coloring, Discrete Applied Mathematics118(2002), 239–248

    M. Mahdian,On the computational complexity of strong edge-coloring, Discrete Applied Mathematics118(2002), 239–248

    work page 2002

  22. [22]

    Vizing,On an estimate of the chromatic class of a p-graph, Diskretnyi Analiz3(1964), 25–30

    V.G. Vizing,On an estimate of the chromatic class of a p-graph, Diskretnyi Analiz3(1964), 25–30. 17

    work page 1964