×

On the adaptable chromatic number of graphs. (English) Zbl 1147.05031

Summary: The adaptable chromatic number of a graph \(G\) is the smallest integer \(k\) such that for any edge \(k\)-colouring of \(G\) there exists a vertex \(k\)-colouring of \(G\) in which the same colour never appears on an edge and both its endpoints. (Neither the edge nor the vertex colourings are necessarily proper in the usual sense.)We give an efficient characterization of graphs with adaptable chromatic number at most two, and prove that it is NP-hard to decide if a given graph has adaptable chromatic number at most \(k\), for any \(k\geq 3\). The adaptable chromatic number cannot exceed the chromatic number; for complete graphs, the adaptable chromatic number seems to be near the square root of the chromatic number. On the other hand, there are graphs of arbitrarily high girth and chromatic number, in which the adaptable chromatic number coincides with the classical chromatic number. In analogy with well-known properties of chromatic numbers, we also discuss the adaptable chromatic numbers of planar graphs, and of graphs with bounded degree, proving a Brooks-like result.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Spencer, J. H.; Erdős, Paul, The Probabilistic Method (1991), John Wiley and Sons
[2] Bondy, J. A.; Hell, P., A note on the star chromatic number, J. Graph Theory, 14, 479-482 (1990) · Zbl 0706.05022
[3] Borodin, O. V., On acyclic coloring of planar graphs, Discrete Math., 25, 211-236 (1979) · Zbl 0406.05031
[4] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115
[5] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of list partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[6] T. Feder, P. Hell, D. Král, J. Sgall, Two algorithms for list matrix partition, in: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, pp. 870-876; T. Feder, P. Hell, D. Král, J. Sgall, Two algorithms for list matrix partition, in: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, pp. 870-876 · Zbl 1297.68091
[7] Gerards, A. H.M., Homomorphisms of graphs into odd cycles, J. Graph Theory, 12, 73-83 (1988) · Zbl 0691.05013
[8] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[9] Karger, D.; Motwani, R.; Sudan, M., Approximate graph coloring by semidefinite programming, J. ACM, 45, 246-265 (1998) · Zbl 0904.68116
[10] Kostochka, A.; Sopena, E.; Zhu, X., Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 24, 331-340 (1997) · Zbl 0873.05044
[11] Nešetřil, J.; Zhu, X., Construction of sparse graphs with prescribed circular colourings, Discrete Math., 233, 277-291 (2001) · Zbl 0982.05048
[12] Pan, Z.; Zhu, X., The circular chromatic number of series-parallel graphs of large odd girth, Discrete Math., 245, 235-246 (2002) · Zbl 0993.05076
[13] Raspaud, A.; Sopena, E., Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett., 51, 171-174 (1994) · Zbl 0806.05031
[14] Simonyi, G.; Tardos, G., Local chromatic number, Ky Fan’s theorem, and circular colouring, Combinatorica, 26, 587-626 (2006) · Zbl 1121.05050
[15] Vince, A., Star chromatic number, J. Graph Theory, 12, 551-559 (1988) · Zbl 0658.05028
[16] Zhu, X., Circular chromatic number, a survey, Discrete Math., 229, 371-410 (2001) · Zbl 0973.05030
[17] 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
[18] A. Kostochka, X. Zhu, Adapted list coloring of graphs and hypergraphs, SIAM J. Disc. Math. (in press); A. Kostochka, X. Zhu, Adapted list coloring of graphs and hypergraphs, SIAM J. Disc. Math. (in press) · Zbl 1170.05309
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.