The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-160863 |
| Date | January 2019 |
| Creators | Johansson, Per |
| Publisher | Linköpings universitet, Matematik och tillämpad matematik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds