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
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