zbMATH — the first resource for mathematics

Almost proper line colorings and near chromatic polynomials. (English) Zbl 0793.05057
Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences,. Ann. N. Y. Acad. Sci. 576, 42-50 (1989).
As motivation for the construction of near chromatic polynomials we consider the following experimental design problem. Suppose that we wish to test the effect on rats of two sets of drugs. Let \(\overline{{\mathbf X}}= \{x_ 1,x_ 2,\dots, x_ m\}\) and \(\overline{{\mathbf Y}}= \{y_ 1,y_ 2,\dots,y_ n\}\) denote these sets. In our investigation, experiments will test the interaction of a given drug from set \(\overline{{\mathbf X}}\) with one or more drugs from set \(\overline{{\mathbf Y}}\). Also, suppose that each test of pairs last 12 hours. We can then form a bipartite graph in which vertices correspond to specific drugs and where the vertices \(x_ i\) and \(y_ j\) are joined by an edge if the corresponding drugs are to be tested together. We see that on any one day drug \(x_ i\) can be paired with at most two other drugs from set \(\overline{{\mathbf Y}}\). If \(\lambda=\) number of days required to complete the tests, we can note that the near chromatic polynomial will tell us whether completion of the investigation is possible in \(\lambda\) days and will provide the number of possible arrangements of these experiments. In addition, the “near chromatic index” will give the minimum number of days required for completion [S. Fiorini and R. J. Wilson, Edge-colourings of graphs (1977; Zbl 0421.05023)].
For the entire collection see [Zbl 0788.00046].

05C15 Coloring of graphs and hypergraphs
62K05 Optimal statistical designs