A special \(k\)-coloring for a connected \(k\)-chromatic graph (Q1363668)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A special \(k\)-coloring for a connected \(k\)-chromatic graph |
scientific article |
Statements
A special \(k\)-coloring for a connected \(k\)-chromatic graph (English)
0 references
10 August 1997
0 references
For \(k\) a positive integer, \(f(k)\) denotes the smallest positive integer such that each connected graph of chromatic number \(k\) can be properly vertex colored with \(k\) colors so that for each pair of vertices \(x_0\) and \(x_p\) in each color class there are vertices \(x_1,x_2, \dots, x_{p-1}\) of the same class with \(d(x_i, x_{i+1}) \leq f(k)\) for each \(i\), \(0\leq i\leq p-1\). The authors show that if the order of the graph is \(n\geq k(k-2)+1\), then \(f(k)< 12k\).
0 references
connected graph
0 references
chromatic number
0 references