FindVertexColoring

FindVertexColoring[g]

finds a coloring with minimal size for the vertices in the graph g.

FindVertexColoring[g,{c1,c2,…}]

finds a coloring {c1,c2,…,ck} for the vertices in the graph g.

Details and Options

Examples

open allclose all

Basic Examples  (2)

Find a vertex coloring of the Petersen graph:

Assign distinct colors to adjacent vertices of a graph:

Visualize the graph:

Scope  (7)

FindVertexColoring works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

Assign distinct colors to adjacent vertices of a graph:

FindVertexColoring works with large graphs:

Applications  (5)

Basic Applications  (2)

Visualize vertex colorings of parametrized graphs:

Find a sequence of colors of CompleteGraph[n]:

CycleGraph[n]:

Making Schedule  (1)

A university has a number of different subjects. Each student is enrolled in some of these subjects. Build a graph where every vertex is a subject and an edge between two vertices means there is a common student:

Find a exam schedule such that no two exams with a common student are scheduled at same time:

Minimum time slots are needed to schedule all exams:

Mobile Radio Frequency Assignment  (1)

When frequencies are assigned to towers, frequencies assigned to all towers at the same location must be different. Build a graph where each vertex is a tower and an edge between two towers represents that they are in range of each other:

Find the minimum number of frequencies needed:

Map Coloring  (1)

Build a map where each vertex is an African country and there is an edge between two countries if they are adjacent:

Color the map with a minimum number of colors, where any adjacent countries must be assigned different colors:

Properties & Relations  (6)

Bipartite graphs are two-colorable graphs:

The one-colorable graphs are empty graphs:

Use FindVertexColoring to compute VertexChromaticNumber:

An edge coloring of a graph is just a vertex coloring of its line graph:

A graph with vertices, its chromatic number and independence number satisfies ≤ :

A face coloring of a planar graph is a vertex coloring of its dual:

Wolfram Research (2021), FindVertexColoring, Wolfram Language function, https://reference.wolfram.com/language/ref/FindVertexColoring.html.

Text

Wolfram Research (2021), FindVertexColoring, Wolfram Language function, https://reference.wolfram.com/language/ref/FindVertexColoring.html.

CMS

Wolfram Language. 2021. "FindVertexColoring." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindVertexColoring.html.

APA

Wolfram Language. (2021). FindVertexColoring. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindVertexColoring.html

BibTeX

@misc{reference.wolfram_2024_findvertexcoloring, author="Wolfram Research", title="{FindVertexColoring}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindVertexColoring.html}", note=[Accessed: 21-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findvertexcoloring, organization={Wolfram Research}, title={FindVertexColoring}, year={2021}, url={https://reference.wolfram.com/language/ref/FindVertexColoring.html}, note=[Accessed: 21-December-2024 ]}