×

Adaptable chromatic number of graph products. (English) Zbl 1179.05045

Summary: A colouring of the vertices of a graph (or hypergraph) \(G\) is adapted to a given colouring of the edges of \(G\) if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of \(G\) is the smallest integer \(k\) such that each edge-colouring of \(G\) by colours 1,2,\(\dots ,k\) admits an adapted vertex-colouring of \(G\) by the same colours 1,2,\(\dots ,k\). (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph \(G\) is smaller than or equal to the ordinary chromatic number of \(G\). While the ordinary chromatic number of all (categorical) powers \(G^k\) of \(G\) remains the same as that of \(G\), the adaptable chromatic number of \(G^k\) may increase with \(k\). We conjecture that for all sufficiently large \(k\) the adaptable chromatic number of \(G^k\) equals the chromatic number of \(G\). When \(G\) is complete, we prove this conjecture with \(k\geq 4\), and offer additional evidence suggesting it may hold with \(k\geq 2\). We also discuss other products and propose several open problems.

MSC:

05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archer, A., On the upper chromatic numbers of the reals, Discrete Math., 214, 65-75 (2000) · Zbl 0957.05039
[2] Brightwell, G. R.; Kohayakawa, Y., Ramsey properties of orientations of graphs, Random Structures Algorithms, 4, 413-428 (1993) · Zbl 0794.05083
[3] Cochand, M.; Duchet, P., A few remarks on orientations of graphs and Ramsey theory, (Halász, G.; Sós, V. T., Irregularities of Partitions. Irregularities of Partitions, Algorithms and Combinatorics, vol. 8 (1989)), 39-46 · Zbl 0698.05055
[4] Cochand, M.; Károlyi, G., On a graph coloring problem, Discrete Math., 194, 249-252 (1999) · Zbl 0934.05055
[5] Erdős, P.; Gyárfás, A., Split and balanced colorings of complete graphs, Discrete Math., 200, 79-86 (1999) · Zbl 0931.05031
[6] L. Esperet, M. Montassier, X. Zhu, Adapted list colouring of planar graphs, Manuscript, 2007; L. Esperet, M. Montassier, X. Zhu, Adapted list colouring of planar graphs, Manuscript, 2007 · Zbl 1221.05136
[7] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115
[8] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of list partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[9] Feder, T.; Hell, P.; Xie, W., Matrix partitions with finitely many obstructions, Electron. J. Combin., 14, 1, 17 pp. (2007), RP 58 · Zbl 1158.05326
[10] Gao, G.; Zhu, X., Star-extremal graphs and lexicographic product, Discrete Math., 152, 147-156 (1996) · Zbl 0852.05046
[11] Greene, J. E., Chromatic capacities of graphs and hypergraphs, Discrete Math., 281, 197-207 (2004) · Zbl 1161.05317
[12] Hajiabolhassan, H.; Zhu, X., Sparse \(H\)-colourable graphs of bounded maximum degree, Graphs Combin., 20, 65-71 (2004) · Zbl 1055.05053
[13] Hakimi, S. L., On the degree of the vertices of a directed graph, J. Franklin Inst., 279, 290-308 (1965) · Zbl 0173.26404
[14] Hell, P.; Zhu, X., Adaptable chromatic number of graphs, European J. Combin., 29, 912-921 (2008) · Zbl 1147.05031
[15] Imrich, W.; Klavžar, S., Product Graphs: Structure and Recognition (2000), John Wiley & Sons: John Wiley & Sons New York
[16] A. Kostochka, X. Zhu, Adapted list coloring of graphs and hypergraphs, SIAM J. Discrete Math. (in press); A. Kostochka, X. Zhu, Adapted list coloring of graphs and hypergraphs, SIAM J. Discrete Math. (in press) · Zbl 1170.05309
[17] Lindner, C. C.; Rodger, C. A., Design Theory (1997), CRC-Press · Zbl 0926.68090
[18] M. Montassier, A. Raspaud, X. Zhu, An upper bound on adaptable choosability of graphs, European J. Combin. doi:10.1016/j.ejc.2008.06.003; M. Montassier, A. Raspaud, X. Zhu, An upper bound on adaptable choosability of graphs, European J. Combin. doi:10.1016/j.ejc.2008.06.003 · Zbl 1209.05094
[19] Poljak, S.; Rödl, V., On the arc-chromatic number of a digraph, J. Combin. Theory B, 31, 190-198 (1981) · Zbl 0472.05024
[20] Rödl, V., A generalization of Ramsey theorem, (Graphs, Hypergraphs, and Block Systems (1976), Zielona Gora), 211-220
[21] Shrikhande, S. S., A note on mutually orthogonal Latin squares, Indian J. Statist. A, 23, 115-116 (1961) · Zbl 0099.35404
[22] Tardif, C.; Wehlau, D., Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rodl function, J. Graph Theory, 51, 33-36 (2006) · Zbl 1132.05024
[23] Zhu, X., A survey on Hedetniemi’s conjecture, Taiwanese J. Math., 2, 1-24 (1998) · Zbl 0906.05024
[24] Zhu, X., Circular chromatic number: A survey, Discrete Math., 229, 1-3, 371-410 (2001) · Zbl 0973.05030
[25] Zhu, X., On the bounds of ultimate independence ratios of graphs, Discrete Math., 156, 229-236 (1996) · Zbl 0857.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.