Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 49 min ago
PreprintarXiv licencearXiv

Exact majority C-colourings of balanced Hamming graphs and grids

  • ZeHua Lu
Open at sourcePDFDOICite

Abstract

A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write M(G) for the maximum number of classes. We determine M(Kq□(2k+1))=⌊(qk+1)/(⌊ q/2⌋+1)⌋ (q≥3, k≥0). The lower bound follows from explicit rectangular partitions and a uniform three-dimensional bridge. A punctured-rectangle construction supplies both the bridge and a partition in the intermediate dimension. The upper bound is a classical consequence of Hamming edge isoperimetry; an elementary proof is included. We also prove M(Cm□ Pn)=n/2⌊ m/2⌋ for m≥4 and even n≥2, contradicting the cylinder assertion of Conjecture 4 in arXiv:2608.27669v1 for odd m≥7 and even n≥6. Further layer bounds determine additional cylinder and torus families.

Related

  1. On-line majority edge-colourings of graphs
    Paweł Pękała
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Triangle-Free Sets in Exact-Distance Hamming Graphs
    Bence Csajbók, Padmini Mukkamala, Zoltán Lóránt Nagy
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Stability and exact extremal colourings for the Alon--Frankl--Lovász bound
    Tianhong Kan, Hongliang Lu, Feihong Yuan
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  4. Strong edge-colourings of truncations of cubic graphs
    Domenico Labbate, Federico Romaniello
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. On Hamming Eigenvalues and Hamming Energy of Graphs
    Harishchandra S. Ramane, Mallappa P. Mellikeri, Daneshwari D. Patil +1
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeometry & topologyDOAJ

Cite

BibTeXRIS
BibTeX
@misc{lu2026exact,
  title = {{Exact majority C-colourings of balanced Hamming graphs and grids}},
  author = {ZeHua Lu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.31674},
  eprint = {2609.31674},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.31674},
}
RIS
TY  - UNPB
TI  - Exact majority C-colourings of balanced Hamming graphs and grids
AU  - ZeHua Lu
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.31674
UR  - https://arxiv.org/abs/2609.31674
AB  - A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write M(G) for the maximum number of classes. We determine M(K_q^□(2k+1))=⌊(q^k+1)/(⌊ q/2⌋+1)⌋ (q≥3, k≥0). The lower bound follows from explicit rectangular partitions and a uniform three-dimensional bridge. A punctured-rectangle construction supplies both the bridge and a partition in the intermediate dimension. The upper bound is a classical consequence of Hamming edge isoperimetry; an elementary proof is included. We also prove M(C_m□ P_n)=n/2⌊ m/2⌋ for m≥4 and even n≥2, contradicting the cylinder assertion of Conjecture 4 in arXiv:2608.27669v1 for odd m≥7 and even n≥6. Further layer bounds determine additional cylinder and torus families.
ER  -