The bounded chromatic number for graphs of genus \(g\) (Q1204466)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The bounded chromatic number for graphs of genus \(g\)
scientific article

    Statements

    The bounded chromatic number for graphs of genus \(g\) (English)
    0 references
    0 references
    0 references
    10 March 1993
    0 references
    Let \({\mathcal G}\) be a collection of finite graphs. The bounded chromatic number \(\chi_ B({\mathcal G})\) is the smallest number of colors \(c\) for which there is an integer \(n\) so that every \(G\in{\mathcal G}\) can be vertex \(c\)-colored without forcing more than \(n\) monochromatic edges. A path is defined here to be what is usually called a trail (a walk with no repeted edges), and a simple path here is what is usually called a path (a walk with no repeated vertices). The bounded (simple) path chromatic number \(\chi_ p({\mathcal G})\) \((\chi_{sp}({\mathcal G}))\) is the smallest number of colors \(c\) for which there is an integer \(n\) so that every \(G\in{\mathcal G}\) can be \(c\)-colored without forcing a monochromatic (simple) path of length more than \(n\). For the collection \({\mathcal G}_ g\) of all graphs having genus \(g\) \((g\geq 0)\), the authors showed previously [Proc. Am. Math. Soc. 105, No. 2, 513-522 (1989; Zbl 0672.05028)] that \(4\leq\chi_ B({\mathcal G}_ g)\leq 6\) and that \(\chi_{sp}({\mathcal G}_ g)=4\). In the present paper they show \(\chi_ B({\mathcal G}_ g)\leq 5\) and \(\chi_ p({\mathcal G}_ p)=4\). Two related numbers for \({\mathcal G}_ g\) are also studied.
    0 references
    trail
    0 references
    walk
    0 references
    path
    0 references
    chromatic number
    0 references
    genus
    0 references

    Identifiers