{
  "id": "enwiki-001367493274",
  "slug": "colour-refinement-algorithm",
  "title": "Colour refinement algorithm",
  "qid": "",
  "lead": "In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement.",
  "body": "In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement. For all vertices v , we set \\lambda_{i+1}(v) = \\left(\\lambda_i(v), \\{\\{ \\lambda_i(w) \\mid w \\text{ is a neighbor of } v\\}\\}\\right) . In other words, the new colour of the vertex v is the pair formed from the previous colour and the multiset of the colours of its neighbours. This algorithm keeps refining the current colouring. At some point it stabilises, i.e., \\lambda_{i+1}(u)=\\lambda_{i+1}(v) if and only if \\lambda_i(u)=\\lambda_i(v) . This final colouring is called the stable colouring. ==Equivalent Characterizations== For two graphs G and H with the same number of vertices, the following conditions are equivalent: G and H are indistinguishable by colour refinement. The minimum fibration bases of G and H are isomorphic. G and H are fractionally isomorphic. G and H have a common coarsest equitable partition. G and H have the same universal cover. For all trees T , there are an equal number of homomorphisms from T to G as there are from T to H . G and H cannot be distinguished by the two variable fragment of first order logic with counting. Any message passing graph neural network will map G and H to the same output, if the input node features are the initial colours \\lambda_0 . Any synchronous anonymous algorithm with broadcast/mailbox message passing in which the input depends on the color only will generate an output that depends, again, on the initial color only. ==References==",
  "categories": [
    "23221441"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1367493274",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1785749998.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001367493274",
    "type": "webpage",
    "title": "Colour refinement algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/colour-refinement-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001367493274",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1367493274",
    "note": "Immutable snapshot enwiki-001367493274"
  }
}