{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R120",
  "content_hash": null,
  "slug": "cdg-artifact-finite-windows-60",
  "type": "artifact",
  "title": "Exact cube-distance colorings on small windows",
  "summary": "The induced graphs on widths 20, 30, 40, and 60 each have chromatic number 3.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "An exact backtracking search computes chromatic number 3 on the induced graphs with vertex sets \\(\\{0,\\ldots,w-1\\}\\) for \\(w=20,30,40,60\\). The lower bound already appears on nine vertices: \\(0,1,2,\\ldots,8,0\\) is an odd cycle whose edge lengths are 1 and 8. A checked 3-coloring at width 60 is encoded by the string 010101012010101012012121201202020101201010101201010120121212.\n\nThese finite values are compatible with an infinite chromatic number. Polynomial recurrence forces larger finite subgraphs to require arbitrarily many colors.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "induced cube-distance graphs on integer intervals of width at most 60",
    "bounds": {
      "width": {
        "max": 60
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "python_computation",
    "source": "research/candidate-screening/multi.py",
    "citation": {
      "url": "https://github.com/philipfweiss/theoremdb/blob/main/research/candidate-screening/multi.py",
      "locator": "research/candidate-screening/multi.py, exact finite-window coloring search"
    },
    "missing": [
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://github.com/philipfweiss/theoremdb/blob/main/research/candidate-screening/multi.py",
    "locator": "research/candidate-screening/multi.py, exact finite-window coloring search"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R122",
      "title": "The cube-distance graph has countably infinite chromatic number",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "R121",
      "title": "Search for a periodic finite coloring",
      "object_type": "attempt",
      "relation": "constrains",
      "direction": "incoming"
    },
    {
      "slug": "chromatic-number-cube-distance-graph",
      "title": "chromatic number cube distance graph",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}