词条 | Circular coloring |
释义 |
In graph theory, circular coloring may be viewed as a refinement of usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the following definitions, all of which are equivalent (for finite graphs).
It is relatively easy to see that (especially using 1. or 2.), but in fact . It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number. Circular coloring was originally defined by {{harvtxt|Vince|1988}}, who called it "star coloring". Coloring is dual to the subject of nowhere-zero flows and indeed, circular coloring has a natural dual notion: circular flows. Circular complete graphs{{infobox graph| name = Circular complete graph | vertices = n | edges = n(n-2k+1) / 2 | chromatic_number = ⌈n/k⌉ | girth = | notation = | properties = {{math|(n − 2k + 1)}}-regular Vertex-transitive Circulant Hamiltonian }} For integers such that , the circular complete graph {{math|Kn/k}} (also known as a circular clique) is the graph with vertex set and edges between elements at distance apart. That is, the vertices are numbers {0, 1, ..., n-1} and vertex i is adjacent to: i+k, i+k+1, ..., i+n-k mod n. For example, {{math|Kn/1}} is just the complete graph {{math|Kn}}, while {{math|K2n+1 / n}} is isomorphic to the cycle graph {{math|C2n+1}}. A circular coloring is then, according to the second definition above, a homomorphism into a circular complete graph. The crucial fact about these graphs is that {{math|Ka/b}} admits a homomorphism into {{math|Kc/d}} if and only if a/b ≤ c/d. This justifies the notation, since if the rational numbers a/b and c/d are equal, then {{math|Ka/b}} and {{math|Kc/d}} are homomorphically equivalent. Moreover, the homomorphism order among them refines the order given by complete graphs into a dense order, corresponding to rational numbers . For example {{math|K2/1}} → {{math|K5/2}} → {{math|K7/3}} → ... → {{math|K3/1}} → {{math|K4/1}} → ... or equivalently {{math|K2}} → {{math|C5}} → {{math|C7}} → ... → {{math|K3}} → {{math|K4}} → ... The example on the figure can be interpreted as a homomorphism from the flower snark {{math|J5}} into {{math|K5/2 ≈ C5}}, which comes earlier than {{math|K3}}, corresponding to the fact that . See also
References
| last = Nadolski | first = Adam | contribution = Circular coloring of graphs | doi = 10.1090/conm/352/09 | location = Providence, RI | mr = 2076994 | pages = 123–137 | publisher = Amer. Math. Soc. | series = Contemp. Math. | title = Graph colorings | volume = 352 | year = 2004}}.
| last = Vince | first = A. | doi = 10.1002/jgt.3190120411 | issue = 4 | journal = Journal of Graph Theory | mr = 968751 | pages = 551–559 | title = Star chromatic number | volume = 12 | year = 1988}}.
| last = Zhu | first = X. | doi = 10.1016/S0012-365X(00)00217-X | issue = 1-3 | journal = Discrete Mathematics | mr = 1815614 | pages = 371–410 | title = Circular chromatic number, a survey | volume = 229 | year = 2001}}.{{combin-stub}} 3 : Graph coloring|Parametric families of graphs|Regular graphs |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。