Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 45 min ago
PreprintarXiv licencearXiv

A stronger upper bound on the D-chromatic index

  • Lin Tian
  • Runze Wang
Open at sourcePDFDOICite

Abstract

For a graph G, a proper edge coloring of G is called a D-coloring if every diamond subgraph of G is rainbow. Let χ'D(G) be the D-chromatic index of G, which is the smallest integer k such that G admits a D-coloring with k colors. Let Δ be the maximum degree of G. The only known Brooks-type upper bound on χ'D(G) is 9/16Δ2 + 1/2Δ, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that χ'D(G) ≤ (1−c)9/16Δ2 for some c > 0 and sufficiently large Δ.

Related

  1. A double-logarithmic upper bound on the chromatic number of the associahedron
    Sang-il Oum, David R. Wood
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An improved upper bound on the chromatic number of the n-dimensional sphere
    A. I. Bikeev, V. A. Voronov, A. M. Raigorodskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An Improved Upper Bound for the Perturbation Index
    Ton That Quoc Tan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Stronger Spectral Bound for Clique Number
    Hareshkumar Jadav, Sudipta Mallik, Akhilesh Panchangam +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. A cubic chromatic bound for capped graphs
    Hongyang Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{tian2026stronger,
  title = {{A stronger upper bound on the D-chromatic index}},
  author = {Lin Tian and Runze Wang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01875},
  eprint = {2609.01875},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01875},
}
RIS
TY  - UNPB
TI  - A stronger upper bound on the D-chromatic index
AU  - Lin Tian
AU  - Runze Wang
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01875
UR  - https://arxiv.org/abs/2609.01875
AB  - For a graph G, a proper edge coloring of G is called a D-coloring if every diamond subgraph of G is rainbow. Let χ'_D(G) be the D-chromatic index of G, which is the smallest integer k such that G admits a D-coloring with k colors. Let Δ be the maximum degree of G. The only known Brooks-type upper bound on χ'_D(G) is 9/16Δ^2 + 1/2Δ, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that χ'_D(G) ≤ (1−c)9/16Δ^2 for some c > 0 and sufficiently large Δ.
ER  -