pith. sign in

arxiv: 2606.04856 · v1 · pith:RSJWWL7Ynew · submitted 2026-06-03 · 🧮 math.CO

Spectral bounds for distance coloring and packing parameters of graphs via semidefinite programming

Aida Abiad , Yue Yang , Jiang Zhou This is my paper

Pith reviewed 2026-06-28 05:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral graph theorysemidefinite programminginjective chromatic numberopen packing numberhypercubesdistance coloringstrong chromatic indexcode covering number
0
0 comments X

The pith

Semidefinite programming and spectral graph theory produce sharp bounds on the injective chromatic number and related distance coloring and packing parameters.

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

The paper develops eigenvalue bounds derived from semidefinite programming relaxations of graph matrices to bound the injective chromatic number, the open packing number, the injective chromatic index, and the strong chromatic index. These spectral bounds improve several existing combinatorial bounds. The authors apply the bounds on the first two parameters to the hypercube graphs, obtaining new exact values for the code covering number and strengthened bounds for the open packing number. The work shows how spectral methods and optimization can address problems that arise in both graph theory and coding theory.

Core claim

Using methods from spectral graph theory and semidefinite programming, sharp spectral bounds are obtained for the injective chromatic number, open packing number, injective chromatic index, and strong chromatic index. The new bounds improve existing combinatorial bounds. The eigenvalue bounds on the first two parameters are applied to estimate the code covering number and the open packing number of hypercubes, yielding new exact values and strengthened bounds.

What carries the argument

Semidefinite programming relaxations of graph matrices that produce eigenvalue bounds for distance coloring and packing parameters.

If this is right

  • The spectral bounds improve several existing combinatorial bounds for the injective chromatic number, open packing number, injective chromatic index, and strong chromatic index.
  • Application of the bounds yields new exact values for the code covering number of hypercubes.
  • Application of the bounds yields strengthened estimates for the open packing number of hypercubes.
  • The combination of spectral and semidefinite programming tools can be used to tackle coloring and packing problems that appear in graph theory and coding theory.

Where Pith is reading between the lines

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

  • The same SDP-based spectral technique could be tested on other distance-constrained parameters beyond the four treated here.
  • Exact values obtained for hypercubes suggest the method may produce closed-form results for additional highly symmetric graphs.
  • The link between the derived coloring bounds and coding parameters indicates the approach may transfer to bounding minimum distances or covering radii in other code families.

Load-bearing premise

The SDP relaxations and eigenvalue bounds derived from the graph matrices are sufficiently tight to produce sharp or improved estimates over combinatorial methods for the listed distance coloring and packing parameters.

What would settle it

A concrete graph for which one of the new spectral bounds is strictly weaker than a known combinatorial bound, or a specific hypercube dimension where the computed code covering number or open packing number contradicts the claimed exact value.

read the original abstract

Using methods from spectral graph theory and semidefinite programming, we obtain sharp spectral bounds for several graph parameters related to distance colorings and packing, including the injective chromatic number, the open packing number, the injective chromatic index, and the strong chromatic index. The new spectral bounds improve several existing combinatorial bounds. Furthermore, we apply the obtained eigenvalue bounds on the first two parameters to estimate the code covering number and the open packing number of hypercubes, obtaining new exact values and strengthened bounds regarding the existing literature. The obtained results illustrate the power of combining spectral and semidefinite programming tools for tackling coloring and packing problems in graph theory and coding theory.

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

0 major / 3 minor

Summary. The paper develops spectral bounds via semidefinite programming relaxations applied to graph matrices (adjacency and distance matrices) for the injective chromatic number, open packing number, injective chromatic index, and strong chromatic index. These bounds are shown to be sharp in some cases and to improve upon prior combinatorial bounds; the eigenvalue bounds on the first two parameters are then used to obtain new exact values and strengthened estimates for the code covering number and open packing number of hypercubes.

Significance. If the SDP relaxations and resulting eigenvalue bounds are tight as claimed, the work provides a systematic spectral-SDP framework that strengthens existing bounds for distance coloring and packing parameters and yields concrete new results on hypercubes. The recovery of exact values on tested families and the explicit improvement over combinatorial methods are notable strengths.

minor comments (3)
  1. [§2] §2, notation for the distance matrix D_G: the definition of the entries d_{uv} should explicitly state whether loops or multiple edges are permitted, as this affects the SDP formulation in §3.
  2. [Table 1] Table 1, hypercube column: the reported exact values for the code covering number would benefit from a brief indication of which SDP relaxation (or which eigenvalue) produces the matching upper bound.
  3. [Introduction] The abstract claims 'sharp' bounds; the introduction or §4 should clarify the precise sense in which sharpness is established (attainment on an infinite family versus equality on specific graphs).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper constructs SDP relaxations directly from the adjacency and distance matrices of a graph to obtain upper bounds on parameters such as the injective chromatic number and open packing number. These bounds are derived from the optimal values of the SDPs and are shown to improve known combinatorial bounds on specific families including hypercubes. No step reduces a claimed result to a fitted parameter, self-referential definition, or load-bearing self-citation by construction; the spectral constructions are independent of the target parameters and externally verifiable via the matrix formulations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; all such elements would need to be extracted from the full manuscript.

pith-pipeline@v0.9.1-grok · 5634 in / 1066 out tokens · 20572 ms · 2026-06-28T05:33:11.428219+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

50 extracted references

  1. [1]

    Abiad, J

    A. Abiad, J. Zhou, Algebraic bounds for the independence and chromatic num- ber of graph powers,SIAM J. Matrix Anal. Appl.47 (2026), 467-482

    2026

  2. [2]

    Abiad, H

    A. Abiad, H. Reijnders, Eigenvalue bounds for distance-edge colorings,Discrete Appl. Math.391 (2026), 176-191

    2026

  3. [3]

    Andersen, The strong chromatic index of a cubic graph is at most 10

    L.D. Andersen, The strong chromatic index of a cubic graph is at most 10. Discrete Math.108(1-3) (1992), 231–252

    1992

  4. [4]

    Axenovich, P

    M. Axenovich, P. D¨ orr, J. Rollin, T. Ueckerdt, Induced and weak induced arboricities,Discrete Math.342 (2019), 511–519

    2019

  5. [5]

    Balla, Orthonormal representations, vector chromatic number, and extension complexity,Bull

    I. Balla, Orthonormal representations, vector chromatic number, and extension complexity,Bull. London Math. Soc.56(9) (2024), 2911–2921

    2024

  6. [6]

    Best, A.E

    M.R. Best, A.E. Brouwer, The triply shortened binary Hamming code is opti- mal,Discrete Math.17 (1977), 235–245

    1977

  7. [7]

    Bruhn, F

    H. Bruhn, F. Joos,(2018). A stronger bound for the strong chromatic index. Comb. Probab. Comput.27(1) (2018), 21–43

    2018

  8. [8]

    Blokhuis, A.E

    A. Blokhuis, A.E. Brouwer, W.H. Haemers, On 3-chromatic distance-regular graphs,Des. Codes Cryptogr.44 (2007), 293–305

    2007

  9. [9]

    Bradshaw, A

    P. Bradshaw, A. Clow, J.W. Xu, Injective edge colorings of degenerate graphs and the oriented chromatic number,Eur. J. Comb.127 (2025), 104139

    2025

  10. [10]

    Breˇ sar, B

    B. Breˇ sar, B. Samadi, I.G. Yero, Injective coloring of graphs revisited,Discrete Math.346 (2023), 113348

    2023

  11. [11]

    Breˇ sar, S

    B. Breˇ sar, S. Klavˇ zar, D.F. Rall, Packings in bipartite prisms and hypercubes, Discrete Math.347(4) (2024), 113875

    2024

  12. [12]

    Brimkov, T.R

    B. Brimkov, T.R. Cameron, O. Grubbs, On the forts and related parameters of the hypercube graph, arXiv:2507.10826 (2025)

    arXiv 2025

  13. [13]

    Brouwer, W.H

    A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer: New York, 2012

    2012

  14. [14]

    Y.H. Bu, D. Chen, A. Raspaud, W.F. Wang, Injective coloring of planar graphs, Discrete Appl. Math.157 (2009), 663–672

    2009

  15. [15]

    Cardoso, J.O

    D.M. Cardoso, J.O. Cerdeira, C. Dominic, J.P. Cruz, Injective edge coloring of graphs,Filomat33 (2019), 6411–6423. 20

    2019

  16. [16]

    M. Chen, G. Hahn, A. Raspaud, W.F. Wang, Some results on the injective chromatic number of graphs,J. Comb. Optim.24 (2012), 299–318

    2012

  17. [17]

    Cranston, S.-J

    D.W. Cranston, S.-J. Kim, G. Yu, Injective colorings of sparse graphs,Discrete Math.310 (2010), 2965–2973

    2010

  18. [18]

    Cranston, S.-J

    D.W. Cranston, S.-J. Kim, G. Yu, Injective Colorings of Graphs with Low Average Degree,Algorithmica60 (2011), 553–568

    2011

  19. [19]

    Cranston, Coloring, List Coloring, and Painting Squares of Graphs (and Other Related Problems),Electron

    D.W. Cranston, Coloring, List Coloring, and Painting Squares of Graphs (and Other Related Problems),Electron. J. Comb.Dynamic Surveys, #DS25 (2023)

    2023

  20. [20]

    W. Dong, W. Lin, Injective coloring of plane graphs with girth 5,Discrete Math.315 (2014), 120–127

    2014

  21. [21]

    Doyon, G

    A. Doyon, G. Hahn, A. Raspaud, Some bounds on the injective chromatic number of graphs,Discrete Math.310 (2010), 585–590

    2010

  22. [22]

    Dvorak, I

    T. Dvorak, I. Havel, J.M. Laborde, P. Liebl, Generalized hypercubes and graph embeddings with dilation,Rostock Math. Kolloq.39 (1990), 13–20

    1990

  23. [23]

    Faudree, R.H

    R.J. Faudree, R.H. Schelp, A. Gy´ arfas, Zs. Tuza, Induced matchings in bipartite graphs,Discrete Math.78 (1989), 83–87

    1989

  24. [24]

    Fiala, J

    J. Fiala, J. Kratochv´ ıl, Partial covers of graphs,Discuss. Math. Graph Theory 22 (2002), 89–99

    2002

  25. [25]

    Foucaud, H

    F. Foucaud, H. Hocquard, D. Lajou, Complexity and algorithms for injective edge-coloring in graphs,Inf. Process. Lett.170 (2021), 106121

    2021

  26. [26]

    Fridrich and P

    J. Fridrich and P. Lison´ ek, Grid colorings of Steganography,IEEE Trans. In- form. Theory53 (2007), 1547–1549

    2007

  27. [27]

    Frieze, M

    A. Frieze, M. Krivelevich, B. Sudakov, The strong chromatic index of random graphs.SIAM J. Discrete Math.19(3) (2005), 719-727

    2005

  28. [28]

    Haemers, Eigenvalue techniques in design and graph theory, PhD The- sis, Technical University Eindhoven, 1979, Mathematical Centre Tracts, 121, Amsterdam, 1980

    W.H. Haemers, Eigenvalue techniques in design and graph theory, PhD The- sis, Technical University Eindhoven, 1979, Mathematical Centre Tracts, 121, Amsterdam, 1980

    1979

  29. [29]

    G. Hahn, J. Kratochvı´ ıl, J.ˇSir´ aˇ n, D. Sotteau, On the injective chromatic num- ber of graphs,Discrete Math.256 (2002), 179–192

    2002

  30. [30]

    Hamid, S

    S. Hamid, S. Saravanakumar, Packing parameters in graphs,Discuss Math. Graph Theory35 (2015), 5–16. 21

    2015

  31. [31]

    P. Hell, A. Raspaud, J. Stacho, On Injective Colourings of Chordal Graphs, Lect. Notes Comput. Sci.4957 (2008), 520–530

    2008

  32. [32]

    Henning, Packing in trees,Discrete Math.186 (1998), 145–155

    M.A. Henning, Packing in trees,Discrete Math.186 (1998), 145–155

    1998

  33. [33]

    Henning, P.J

    M.A. Henning, P.J. Slater, Open packing in graphs,J. Comb. Math. Comb. Comput.28 (1999), 5–18

    1999

  34. [34]

    Hoffman, On eigenvalues and colourings of graphs, in Graph Theory and its Applications, Academic Press, New York (1970), 79–91

    A.J. Hoffman, On eigenvalues and colourings of graphs, in Graph Theory and its Applications, Academic Press, New York (1970), 79–91

    1970

  35. [35]

    Kostochka, A

    A. Kostochka, A. Raspaud, J.W. Xu, Injective edge-coloring of graphs with given maximum degree.Eur. J. Comb.96 (2021), 103355

    2021

  36. [36]

    Kratochv´ ıl, M

    J. Kratochv´ ıl, M. Siggers, Locally injectivek-colourings of planar graphs,Dis- crete Appl. Math.173 (2014), 53–61

    2014

  37. [37]

    Lov´ asz, On the Shannon capacity of a graph,IEEE Trans

    L. Lov´ asz, On the Shannon capacity of a graph,IEEE Trans. Inform. Theory 25, 1 (1979), 1–7

    1979

  38. [38]

    Mahdian, The strong chromatic index ofC 4-free graphs.Random Struct

    M. Mahdian, The strong chromatic index ofC 4-free graphs.Random Struct. Algorithms17(3-4) (2000), 357-375

    2000

  39. [39]

    McLoughlin, The complexity of computing the covering radius of a code, IEEE Trans

    A. McLoughlin, The complexity of computing the covering radius of a code, IEEE Trans. Inform. Theory30 (1984), 800–804

    1984

  40. [40]

    McEliece, An application of linear programming to a problem in coding theory (1973), unpublished

    R.J. McEliece, An application of linear programming to a problem in coding theory (1973), unpublished

    1973

  41. [41]

    Molloy, B

    M. Molloy, B. Reed, A bound on the strong chromatic index of a graph.J. Comb. Theory, B, 69(2) (1997), 103–109

    1997

  42. [42]

    Panda, Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs,Discrete Appl

    B.S. Panda, Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs,Discrete Appl. Math.291 (2021), 68–87

    2021

  43. [43]

    Panda, Priyamvada, Complexity and algorithms for injective edge coloring of graphs,Theor

    B.S. Panda, Priyamvada, Complexity and algorithms for injective edge coloring of graphs,Theor. Comput. Sci.968 (2023), 114010

    2023

  44. [44]

    Panda, R

    B.S. Panda, R. Ghosh, Injective coloring of subclasses of chordal graphs,Theor. Comput. Sci.1023 (2025), 114894

    2025

  45. [45]

    Rall, Total domination in categorical products of graphs,Discuss

    D.F. Rall, Total domination in categorical products of graphs,Discuss. Math. Graph Theory25 (2005), 35–44

    2005

  46. [46]

    Samadi, N

    B. Samadi, N. Soltankhah, I.G. Yero, Injective coloring of product graphs,Bull. Malays. Math. Sci. Soc.47(3) (2024), 86. 22

    2024

  47. [47]

    Shalu, V.K

    M.A. Shalu, V.K. Kirubakaran, Open Packing in Graphs: Bounds and Com- plexity, arXiv:2406.06982 (2024)

    arXiv 2024

  48. [48]

    J.M. Song, J. Yue, Injective coloring of some graph operations,Appl. Math. Comput.264 (2015), 279–283

    2015

  49. [49]

    Y. Yang, J. Zhou, Algebraic bounds on the chromatic number and independent sets of graphs,Discrete Appl. Math.389 (2026), 203-213

    2026

  50. [50]

    Zhou, Unified bounds for the independence number of graphs,Canad

    J. Zhou, Unified bounds for the independence number of graphs,Canad. J. Math.77 (2025), 97-117. 23 Appendix Table 1: For all connected non-isomorphic graphs of small fixed ordern, we show the percentage of graphs of fix order for which our bound from Corollary 3.3 strictly improves the known bound from Theorem 3.1 ([10, Theorem 6]). n Percentage of strict...

    2025