The color space of a graph

T.R. Jensen, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    If k is a prime power, and G is a graph with n vertices, then a k-coloring of G may be considered as a vector in GF(k)(n). We prove that the subspace of GF(3)(n) spanned by all 3-colorings of a planar triangle-free graph with n vertices has dimension n. In particular, any such graph has at least n - 1 nonequivalent 3-colorings, and the addition of any edge or any vertex of degree 3 results in a 3-colorable graph. (C) 2000 John Wiley & Sons, Inc.
    Original languageEnglish
    JournalJournal of Graph Theory
    Volume34
    Issue number3
    Pages (from-to)234-245
    ISSN0364-9024
    DOIs
    Publication statusPublished - 2000

    Keywords

    • Graph
    • Vertex coloring
    • Planar graph
    • Vector space

    Fingerprint Dive into the research topics of 'The color space of a graph'. Together they form a unique fingerprint.

    Cite this