| Constructing Colorings for Diagrams (2007) | |||||||||||||
Abstract | |||||||||||||
| Introduction and Overview An undirected graph G = (V; E) is a (Hasse--) diagram if there is a poset P = (V; !) and an orientation ~ E of E such that (x; y) 2 ~ E iff x ! y in P and there is no z with x ! z ! y. We then write G = D P . A pair (x; y) 2 ~ E is called a covering and denoted by x OE y. The chromatic number Ø ( G ) is the least number of colors needed to color the vertices of G such that no two adjacent vertices obtain the same color. The interest in the chromatic number of diagrams is motivated by a lack of small explicit examples of triangle-free graphs with chromatic number ? 3. In [NR87] N | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||