| Title:
|
Neochromatica (English) |
| Author:
|
Cheilaris, Panagiotis |
| Author:
|
Specker, Ernst |
| Author:
|
Zachos, Stathis |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
51 |
| Issue:
|
3 |
| Year:
|
2010 |
| Pages:
|
469-480 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We create and discuss several modifications to traditional graph coloring. In particular, we classify various notions of coloring in a proper hierarchy. We concentrate on grid graphs whose colorings can be represented by natural number entries in arrays with various restrictions. (English) |
| Keyword:
|
graph coloring |
| Keyword:
|
paths |
| Keyword:
|
conflict-free |
| MSC:
|
05C15 |
| MSC:
|
05C65 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 1224.05164 |
| idMR:
|
MR2741880 |
| . |
| Date available:
|
2010-09-02T14:18:43Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140723 |
| . |
| Reference:
|
[1] Allouche J.-P., Shallit J.: Automatic Sequences: Theory, Applications, Generalizations.Cambridge University Press, Cambridge, 2003. Zbl 1086.11015, MR 1997038 |
| Reference:
|
[2] Alon N., Grytczuk J., Hałuszczak M., Riordan O.: Nonrepetitive colorings of graphs.Random Structures Algorithms 21 (2002), no. 3–4, 336–346. MR 1945373, 10.1002/rsa.10057 |
| Reference:
|
[3] Alon N., Smorodinsky S.: Conflict-free colorings of shallow discs.Internat. J. Comput. Geom. Appl. 18 (2008), no. 6, 599–604. Zbl 1184.05038, MR 2479564, 10.1142/S0218195908002775 |
| Reference:
|
[4] Bar-Noy A., Cheilaris P., Lampis M., Mitsou V., Zachos S.: Ordered coloring grids and related graphs.Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2009, pp. 30–43. MR 2671334 |
| Reference:
|
[5] Bar-Noy A., Cheilaris P., Smorodinsky S.: Deterministic conflict-free coloring for intervals: from offline to online.ACM Trans. Algorithms 4 (2008), no. 4, 18pp. MR 2446963, 10.1145/1383369.1383375 |
| Reference:
|
[6] Cheilaris P.: Conflict-free coloring.Ph.D. thesis, City University of New York, 2009. |
| Reference:
|
[7] Chen K., Fiat A., Kaplan H., Levy M., Matoušek J., Mossel E., Pach J., Sharir M., Smorodinsky S., Wagner U., Welzl E.: Online conflict-free coloring for intervals.SIAM J. Comput. 36 (2007), no. 5, 1342–1359. MR 2284084, 10.1137/S0097539704446682 |
| Reference:
|
[8] Currie J.D.: There are ternary circular square-free words of length $n$ for $n \geq 18$.Electron. J. Combin. 9 (2002), no. 1, N10. Zbl 1057.68081, MR 1936865 |
| Reference:
|
[9] Djidjev H.N.: On the problem of partitioning planar graphs.SIAM J. Algebraic Discrete Methods 3 (1982), 229–240. Zbl 0503.05057, MR 0655563, 10.1137/0603022 |
| Reference:
|
[10] Erlebach T., Pagourtzis A., Potika K., Stefanakos S.: Resource allocation problems in multifiber WDMtree networks.Proceedings of 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003), Lecture Notes in Comput. Sci., 2880, Berlin, 2003, pp. 218–229. MR 2080082 |
| Reference:
|
[11] Even G., Lotker Z., Ron D., Smorodinsky S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.SIAM J. Comput. 33 (2003), 94–136. Zbl 1069.68120, MR 2033655, 10.1137/S0097539702431840 |
| Reference:
|
[12] Grytczuk J.: Nonrepetitive graph coloring.Graph Theory, Trends in Mathematics, Birkhäuser, Basel, 2007, pp. 209–218. Zbl 1120.05029, MR 2279177 |
| Reference:
|
[13] Har-Peled S., Smorodinsky S.: Conflict-free coloring of points and simple regions in the plane.Discrete Comput. Geom. 34 (2005), 47–70. Zbl 1066.05064, MR 2140882, 10.1007/s00454-005-1162-6 |
| Reference:
|
[14] Iyer A.V., Ratliff H.R., Vijayan G.: Optimal node ranking of trees.Inform. Process. Lett. 28 (1988), 225–229. Zbl 0661.68063, MR 0958825, 10.1016/0020-0190(88)90194-9 |
| Reference:
|
[15] Jordan C.: Sur les assemblages de lignes.J. Reine Angew. Math. 70 (1869), 185–190. |
| Reference:
|
[16] Katchalski M., McCuaig W., Seager S.: Ordered colourings.Discrete Math. 142 (1995), 141–154. Zbl 0842.05032, MR 1341442, 10.1016/0012-365X(93)E0216-Q |
| Reference:
|
[17] Lewis P.M. II, Stearns R.E., Hartmanis J.: Memory bounds for recognition of context-free and context-sensitive languages.Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, Ann Arbor, MI, 1965, pp. 191–202. Zbl 0272.68054 |
| Reference:
|
[18] Lipton R.J., Tarjan R.E.: A separator theorem for planar graphs.SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. Zbl 0432.05022, MR 0524495, 10.1137/0136016 |
| Reference:
|
[19] Nešetřil J., Ossona de Mendez P.: Tree-depth, subgraph coloring and homomorphism bounds.European J. Combin. 27 (2006), 1022–1041. MR 2226435, 10.1016/j.ejc.2005.01.010 |
| Reference:
|
[20] Nešetřil J., Ossona de Mendez P., Wood D.R.: Characterisations and examples of graph classes with bounded expansion.CoRR abs/0902.3265 (2009). |
| Reference:
|
[21] Pach J., Tóth G.: Conflict Free Colorings.Discrete and Computational Geometry, The Goodman-Pollack Festschrift, Springer, Berlin, 2003, pp. 665–671. MR 2038496 |
| Reference:
|
[22] Pezarski A., Zmarz M.: Non-repetitive $3$-coloring of subdivided graphs.Electron. J. Combin. 16 (2009), N15. Zbl 1165.05325, MR 2515755 |
| Reference:
|
[23] Prouhet E.: Mémoire sur quelques relations entre les puissances des nombres.Comptes Rendus de l'Académie des Sciences, Paris, Série I 33 (1851), 225. |
| Reference:
|
[24] Schäffer A.A.: Optimal node ranking of trees in linear time.Inform. Process. Lett. 33 (1989), no. 2, 91–96. MR 1031599, 10.1016/0020-0190(89)90161-0 |
| Reference:
|
[25] Thue A.: Über unendliche Zeichenreihen.Norske vid. Selsk. Skr. Mat. Nat. Kl 7 (1906), 1–22. |
| . |
