Pith Number

pith:RUI67RIW

pith:2026:RUI67RIWEXKJXWPFHTH3D5W2KY

not attested not anchored not stored refs resolved

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds

Samuel German

A graph with twin cover of size t has strong conflict-free vertex-connection number at most its chromatic number plus t.

arxiv:2605.13299 v1 · 2026-05-13 · cs.DM · cs.DS

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{RUI67RIWEXKJXWPFHTH3D5W2KY}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Given (G,k) together with a twin cover X of size t, we reduce in polynomial time to an equivalent annotated instance on at most max{2,t+(t+1)k 2^{t+k-1}} vertices. Every connected graph G with twin cover X of size t satisfies χ(G) ≤ svcfc(G) ≤ χ(G) + t.

C2weakest assumption

The kernelization result assumes a twin cover X is supplied as part of the input; the FPT claim for tc(G) + k therefore depends on either the cover being given or on the complexity of computing it separately.

C3one line summary

Kernelization establishes FPT for strong CFVC number by twin cover plus k, with svcfc(G) bounded between χ(G) and χ(G) plus twin cover size.

References

11 extracted · 11 resolved · 0 Pith anchors

[1] Discrete Applied Mathematics352, 88–104 (2024) 2024 · doi:10.1016/j.dam.2024.03.021

[2] Discussiones Mathematicae Graph Theory38(4), 911–920 (2018) 2018 · doi:10.7151/dmgt.2036

[3] SIAM Journal on Computing33(1), 94–136 (2003) 2003 · doi:10.1137/s0097539702431840

[4] Discrete Applied Mathematics383, 85–93 (2026) 2026 · doi:10.1016/j.dam.2025.12.025

[5] Discrete Mathematics & Theoretical Computer Science17(2), 77–100 (2015) 2015 · doi:10.46298/dmtcs.2136

Formal links

1 machine-checked theorem link

Receipt and verification

First computed	2026-05-18T02:44:49.058184Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

8d11efc51625d49bd9e53ccfb1f6da56358fb8e061b32caaaf0573a6b0622b10

Aliases

arxiv: 2605.13299 · arxiv_version: 2605.13299v1 · doi: 10.48550/arxiv.2605.13299 · pith_short_12: RUI67RIWEXKJ · pith_short_16: RUI67RIWEXKJXWPF · pith_short_8: RUI67RIW

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/RUI67RIWEXKJXWPFHTH3D5W2KY \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 8d11efc51625d49bd9e53ccfb1f6da56358fb8e061b32caaaf0573a6b0622b10

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "cf35c419ebe748131ac7a76d0f046512d08b4b1f6d53d83c04ba7ac6a5ac939a",
    "cross_cats_sorted": [
      "cs.DS"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.DM",
    "submitted_at": "2026-05-13T10:13:01Z",
    "title_canon_sha256": "e401756958e668504b3b09e20c563c1d223ae8a52eb306e247e1a512b7c22894"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13299",
    "kind": "arxiv",
    "version": 1
  }
}