Select any concept, construction junction, or annotated relation by pointer, touch, search, or keyboard.

Construction junctions are diamonds. They show where multiple structures must coexist on the same carrier and satisfy compatibility conditions.

Canonical static concept record

Proper vertex coloring

Open this concept in the interactive graph Read the Markdown equivalent

Summary

A labeling of a graph’s vertices by colors such that adjacent vertices receive different colors.

Record metadata

Canonical name: Proper vertex coloring
Concept ID: graph_coloring
Content version: 2.3.0
Primary field: Mathematics
Fields: Mathematics
Primary domain: Combinatorics & graph theory
Domains: Combinatorics & graph theory
Alternate terminology: No alternate terminology is currently authored for this record.

Carrier(s)

simple graph $G=(V,E)$
color set $C$

Data

map $c\colon V\to C$

Axioms / constraints

$c(u)\ne c(v)$ whenever $\{u,v\}\in E$

Canonically induces

partition of the vertex set into independent color classes

Notes

This is proper vertex coloring; edge colorings, face colorings, and improper colorings are separate notions.

Concept sources

Wikipedia — Graph coloring — Graph coloring · encyclopedic reference · source ID wp-graph-coloring
nLab — vertex coloring — vertex coloring · mathematical reference · source ID nlab-vertex-coloring
Diestel — Graph Theory — Graph Theory · textbook · source ID diestel-graph-theory

Incoming relations (arrows to this concept)

Each relation below ends at this concept.

Simple graph Proper vertex coloring

Permalink to relation

This is an authored directed relation from the source endpoint to the target endpoint.

Relation ID: simple_graph_to_graph_coloring
Relation type: Add data add-data
Direction: source → target
Endpoint roles: source: Builds toward; target: Built from
Authored annotation: choose a proper vertex coloring

Authored explanation

Choose a color set and a vertex-labeling map whose values differ across every edge.

How to interpret this relation type

Equip an existing carrier or structured object with additional chosen data, when such compatible data exists. Use a construction junction when several independently meaningful inputs must coexist on the same carrier or interact compatibly.

Relation sources

Wikipedia — Graph coloring — Graph coloring · encyclopedic reference · source ID wp-graph-coloring
nLab — vertex coloring — vertex coloring · mathematical reference · source ID nlab-vertex-coloring
Diestel — Graph Theory — Graph Theory · textbook · source ID diestel-graph-theory

Outgoing relations (arrows from this concept)

Each relation below starts at this concept.

No direct relations are authored in this direction.

Atlas of Fundamental Concepts

Select a concept

Move selected concept

Stories & Views

Compare concepts

Guide to the Atlas