请输入您要查询的字词:

 

单词 TaitColoring
释义

Tait coloring


A Tait coloringMathworldPlanetmath of a trivalent (http://planetmath.org/ValencyPlanetmathPlanetmath) (aka cubic) graph is a coloringMathworldPlanetmath of its edges with only three colors, such that at each vertex the colors of the three edges there are different. After Peter G. Tait (1831–1901), Scottish physicist, who in 1880 proved the following

TheoremMathworldPlanetmath (Tait) A bridge-free trivalent plane graphMathworldPlanetmath can beface-colored with 4 colors if and only if it can be edge-colored with 3colors.

This http://planetmath.org/node/6925introduction to face- and edge-colorings of plane graphshas a proof of the theorem.

To put this in a modern context, Vizing’s theorem says that graphs Gfall into two classes: those that can be colored with Δ(G) colors andthose that need Δ(G)+1 colors, where Δ(G) is the largest valencythat occurs in G. When applied to trivalent graphs that means 3 and 4colors, respectively. It is known that “almost all” are in the first class— this expression has a technical meaning (for increasing graph size, theproportion of them in the second class tends to zero).

Thanks to Tait’s result, it is a corollary of the four-color theoremthat all planar trivalent graphs are in the first class (can be edge-3-colored).The converseMathworldPlanetmath is not the case. Many trivalent graphs, in fact almost all ofthem, can be edge-3-colored and yet are not planar. K3,3 is one example.

The Petersen graphMathworldPlanetmathPlanetmath is an example of a trivalent graph that needs 4 colors.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:49:12