k-partite graph

A $k$ -partite graph is a graph with a chromatic number of $k$ .

An alternate definition of a $k$ -partite graph is a graph where the vertices are partitioned into $k$ subsets with the following conditions:

1.
No two vertices in the same subset are adjacent.
2.
There is no partition of the vertices with fewer than $k$ subsets where condition 1 holds.

These two definitions are equivalent. Informally, we see that a colour can be assigned to all the vertices in each subset, since they are not adjacent to one another. Furthermore, this is also an optimal colouring, since the second condition holds.

An example of a 4-partite graph:

单词	KpartiteGraph
释义	k-partite graph A $k$ -partite graph is a graph with a chromatic number of $k$ . An alternate definition of a $k$ -partite graph is a graph where the vertices are partitioned into $k$ subsets with the following conditions: 1. No two vertices in the same subset are adjacent. 2. There is no partition of the vertices with fewer than $k$ subsets where condition 1 holds. These two definitions are equivalent. Informally, we see that a colour can be assigned to all the vertices in each subset, since they are not adjacent to one another. Furthermore, this is also an optimal colouring, since the second condition holds. An example of a 4-partite graph:
随便看	EuclidsLemma EuclidsLemmaProof EuclidsProofOfTheInfinitudeOfPrimes Euclid’s algorithm Euclid’s coefficients Euclid’s lemma Euclid’s lemma proof Euclid’s proof of the infinitude of primes EulerCharacteristic Euler characteristic EulerCircuit Euler circuit EulerFermatTheorem Euler-Fermat theorem EulerFoursquareIdentity Euler four-square identity EulerGompertzConstant Euler-Gompertz constant EulerianPoset Eulerian poset EulerLagrangeDifferentialEquationadvanced Euler-Lagrange differential equation (advanced) EulerLagrangeDifferentialEquationelementary Euler-Lagrange differential equation (elementary) EulerLeonhard