Math 2.0

Combinatorics Definition

K-colourable graph

Builds on Graph colouring

Definition

Let kk be a natural number. A graph GG is kk-colourable if it has a colouring with the set of colours {1,2,…,k}\{1, 2, \dots, k\}.

Remarks

A kk-colourable graph is also (k+1)(k+1)-colourable. A graph is 22-colourable if and only if it is bipartite. The complete graph KnK_n is kk-colourable if and only if k≥nk \ge n.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Graph colouring, definition, no evidence levelGraph colouringdefinitionK-colourable graph, definition, no evidence levelK-colourable graphdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph colouring definition
  2. K-colourable graph definition

Where this leads

10 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Graph_coloring, Vertex coloring
About this page
Tag0Y7VDAX8Q3
URIm2://0Y7VDAX8Q3
Kinddefinition
WritingW0 stub
MSC05C15
DefinesK-colourable graph
UsesGraph colouring

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by

Results about this