"chromatic number" meaning in English

{
  "forms": [
    {
      "form": "chromatic numbers",
      "tags": [
        "plural"
      ]
    }
  ],
  "head_templates": [
    {
      "args": {},
      "expansion": "chromatic number (plural chromatic numbers)",
      "name": "en-noun"
    }
  ],
  "lang": "English",
  "lang_code": "en",
  "pos": "noun",
  "senses": [
    {
      "categories": [
        {
          "kind": "other",
          "name": "English entries with incorrect language header",
          "parents": [
            "Entries with incorrect language header",
            "Entry maintenance"
          ],
          "source": "w"
        },
        {
          "kind": "topical",
          "langcode": "en",
          "name": "Graph theory",
          "orig": "en:Graph theory",
          "parents": [
            "Mathematics",
            "Visualization",
            "Formal sciences",
            "Computing",
            "Interdisciplinary fields",
            "Sciences",
            "Technology",
            "All topics",
            "Fundamental"
          ],
          "source": "w"
        }
      ],
      "derived": [
        {
          "word": "chromatic number problem"
        },
        {
          "word": "edge chromatic number"
        },
        {
          "word": "harmonious chromatic number"
        },
        {
          "word": "total chromatic number"
        }
      ],
      "examples": [
        {
          "text": "The chromatic number of a complete graph K#x5F;n is n; the chromatic number of a bipartite graph K#x5F;#x7B;n,m#x7D; is 2.",
          "type": "example"
        },
        {
          "ref": "1995, J. A. Bondy, “1: Basic Graph Theory: Paths and Circuits”, in Ronald L. Graham, Martin Grötschel, László Lovász, editors, Handbook of Combinatorics, Volume 1, Elsevier (North-Holland), page 48",
          "text": "The chromatic number of a graph G is the minimum value of k for which G is k-colourable, and is denoted by #x5C;chi(G).[…]A more essential use of the chromatic number was made by Gallai (1968a) and Roy (1967), who discovered a simple relationship between the chromatic number of a digraph and the length of a longest directed path in the digraph, where the chromatic number #x5C;chi(D) of a digraph D is defined to be the chromatic number of its underlying graph G(D).",
          "type": "quotation"
        },
        {
          "text": "2004, Monia Discepoli, Ivan Gerace, Riccardo Mariani, Andrea Remigi, A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs, Antonio Laganà, et al. (editors), Computational Science and Its Applications, ICCSA 2004: International Conference, Proceedings, Part 3, Springer, LNCS 3045, page 745,\nThe CHROMATIC NUMBER is the minimum number of colors by means of which it is possible to color a graph in such a way that each vertex has a different color with respect to the adjacent vertices. Such a problem is an NP-hard problem [14] and [it] is even hard to obtain a good approximation of the solution in a polynomial time [17]. Although in a lot of computational problems the cost decreases when these problems are restricted to circulant graphs [6, 9], the CHROMATIC NUMBER problem is NP-hard even restrecting to circulant graphs [9]. Moreover the problem of finding a good approximation of the CHROMATIC NUMBER problem on circulant graphs is also NP-hard."
        },
        {
          "text": "2009, Gary Chartrand, Ping Zhang, Chromatic Graph Theory, Taylor & Francis Group (CRC Press / Chapman & Hall), page 149,\nThere is no general formula for the chromatic number of a graph. Consequently, we will often be concerned and must be content with (1) determining the chromatic number of some classes of interest and (2) determining upper and/or lower bounds for the chromatic number of a graph."
        }
      ],
      "glosses": [
        "The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
      ],
      "id": "en-chromatic_number-en-noun-bT27JdHm",
      "links": [
        [
          "graph theory",
          "graph theory"
        ],
        [
          "colour",
          "colour"
        ],
        [
          "graph",
          "graph"
        ],
        [
          "vertex",
          "vertex"
        ],
        [
          "edge",
          "edge"
        ]
      ],
      "raw_glosses": [
        "(graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
      ],
      "related": [
        {
          "word": "achromatic number"
        },
        {
          "word": "chromatic index"
        },
        {
          "word": "chromatic polynomial"
        },
        {
          "word": "k-colouring"
        },
        {
          "word": "k-chromatic"
        }
      ],
      "synonyms": [
        {
          "english": "used to differentiate from edge chromatic number",
          "sense": "smallest number of colours needed to colour the vertices of a graph",
          "tags": [
            "usually"
          ],
          "word": "vertex chromatic number"
        }
      ],
      "topics": [
        "graph-theory",
        "mathematics",
        "sciences"
      ],
      "translations": [
        {
          "code": "hu",
          "lang": "Hungarian",
          "sense": "smallest number of colours needed to colour a graph",
          "word": "kromatikus szám"
        },
        {
          "code": "is",
          "lang": "Icelandic",
          "sense": "smallest number of colours needed to colour a graph",
          "tags": [
            "feminine"
          ],
          "word": "litatala"
        },
        {
          "code": "it",
          "lang": "Italian",
          "sense": "smallest number of colours needed to colour a graph",
          "tags": [
            "masculine"
          ],
          "word": "numero cromatico"
        },
        {
          "code": "es",
          "lang": "Spanish",
          "sense": "smallest number of colours needed to colour a graph",
          "tags": [
            "masculine"
          ],
          "word": "número cromático"
        }
      ]
    }
  ],
  "word": "chromatic number"
}

{
  "derived": [
    {
      "word": "chromatic number problem"
    },
    {
      "word": "edge chromatic number"
    },
    {
      "word": "harmonious chromatic number"
    },
    {
      "word": "total chromatic number"
    }
  ],
  "forms": [
    {
      "form": "chromatic numbers",
      "tags": [
        "plural"
      ]
    }
  ],
  "head_templates": [
    {
      "args": {},
      "expansion": "chromatic number (plural chromatic numbers)",
      "name": "en-noun"
    }
  ],
  "lang": "English",
  "lang_code": "en",
  "pos": "noun",
  "related": [
    {
      "word": "achromatic number"
    },
    {
      "word": "chromatic index"
    },
    {
      "word": "chromatic polynomial"
    },
    {
      "word": "k-colouring"
    },
    {
      "word": "k-chromatic"
    }
  ],
  "senses": [
    {
      "categories": [
        "English countable nouns",
        "English entries with incorrect language header",
        "English lemmas",
        "English multiword terms",
        "English nouns",
        "English terms with quotations",
        "English terms with usage examples",
        "en:Graph theory"
      ],
      "examples": [
        {
          "text": "The chromatic number of a complete graph K#x5F;n is n; the chromatic number of a bipartite graph K#x5F;#x7B;n,m#x7D; is 2.",
          "type": "example"
        },
        {
          "ref": "1995, J. A. Bondy, “1: Basic Graph Theory: Paths and Circuits”, in Ronald L. Graham, Martin Grötschel, László Lovász, editors, Handbook of Combinatorics, Volume 1, Elsevier (North-Holland), page 48",
          "text": "The chromatic number of a graph G is the minimum value of k for which G is k-colourable, and is denoted by #x5C;chi(G).[…]A more essential use of the chromatic number was made by Gallai (1968a) and Roy (1967), who discovered a simple relationship between the chromatic number of a digraph and the length of a longest directed path in the digraph, where the chromatic number #x5C;chi(D) of a digraph D is defined to be the chromatic number of its underlying graph G(D).",
          "type": "quotation"
        },
        {
          "text": "2004, Monia Discepoli, Ivan Gerace, Riccardo Mariani, Andrea Remigi, A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs, Antonio Laganà, et al. (editors), Computational Science and Its Applications, ICCSA 2004: International Conference, Proceedings, Part 3, Springer, LNCS 3045, page 745,\nThe CHROMATIC NUMBER is the minimum number of colors by means of which it is possible to color a graph in such a way that each vertex has a different color with respect to the adjacent vertices. Such a problem is an NP-hard problem [14] and [it] is even hard to obtain a good approximation of the solution in a polynomial time [17]. Although in a lot of computational problems the cost decreases when these problems are restricted to circulant graphs [6, 9], the CHROMATIC NUMBER problem is NP-hard even restrecting to circulant graphs [9]. Moreover the problem of finding a good approximation of the CHROMATIC NUMBER problem on circulant graphs is also NP-hard."
        },
        {
          "text": "2009, Gary Chartrand, Ping Zhang, Chromatic Graph Theory, Taylor & Francis Group (CRC Press / Chapman & Hall), page 149,\nThere is no general formula for the chromatic number of a graph. Consequently, we will often be concerned and must be content with (1) determining the chromatic number of some classes of interest and (2) determining upper and/or lower bounds for the chromatic number of a graph."
        }
      ],
      "glosses": [
        "The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
      ],
      "links": [
        [
          "graph theory",
          "graph theory"
        ],
        [
          "colour",
          "colour"
        ],
        [
          "graph",
          "graph"
        ],
        [
          "vertex",
          "vertex"
        ],
        [
          "edge",
          "edge"
        ]
      ],
      "raw_glosses": [
        "(graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour)."
      ],
      "topics": [
        "graph-theory",
        "mathematics",
        "sciences"
      ]
    }
  ],
  "synonyms": [
    {
      "english": "used to differentiate from edge chromatic number",
      "sense": "smallest number of colours needed to colour the vertices of a graph",
      "tags": [
        "usually"
      ],
      "word": "vertex chromatic number"
    }
  ],
  "translations": [
    {
      "code": "hu",
      "lang": "Hungarian",
      "sense": "smallest number of colours needed to colour a graph",
      "word": "kromatikus szám"
    },
    {
      "code": "is",
      "lang": "Icelandic",
      "sense": "smallest number of colours needed to colour a graph",
      "tags": [
        "feminine"
      ],
      "word": "litatala"
    },
    {
      "code": "it",
      "lang": "Italian",
      "sense": "smallest number of colours needed to colour a graph",
      "tags": [
        "masculine"
      ],
      "word": "numero cromatico"
    },
    {
      "code": "es",
      "lang": "Spanish",
      "sense": "smallest number of colours needed to colour a graph",
      "tags": [
        "masculine"
      ],
      "word": "número cromático"
    }
  ],
  "word": "chromatic number"
}