Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graph coloring; paths; conflict-free
graph coloring; paths; conflict-free
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.
References:
[1] Allouche J.-P., Shallit J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003. MR 1997038 | Zbl 1086.11015
[2] Alon N., Grytczuk J., Hałuszczak M., Riordan O.: Nonrepetitive colorings of graphs. Random Structures Algorithms 21 (2002), no. 3–4, 336–346. DOI 10.1002/rsa.10057 | MR 1945373
[3] Alon N., Smorodinsky S.: Conflict-free colorings of shallow discs. Internat. J. Comput. Geom. Appl. 18 (2008), no. 6, 599–604. DOI 10.1142/S0218195908002775 | MR 2479564 | Zbl 1184.05038
[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
[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. DOI 10.1145/1383369.1383375 | MR 2446963
[6] Cheilaris P.: Conflict-free coloring. Ph.D. thesis, City University of New York, 2009.
[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. DOI 10.1137/S0097539704446682 | MR 2284084
[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. MR 1936865 | Zbl 1057.68081
[9] Djidjev H.N.: On the problem of partitioning planar graphs. SIAM J. Algebraic Discrete Methods 3 (1982), 229–240. DOI 10.1137/0603022 | MR 0655563 | Zbl 0503.05057
[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
[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. DOI 10.1137/S0097539702431840 | MR 2033655 | Zbl 1069.68120
[12] Grytczuk J.: Nonrepetitive graph coloring. Graph Theory, Trends in Mathematics, Birkhäuser, Basel, 2007, pp. 209–218. MR 2279177 | Zbl 1120.05029
[13] Har-Peled S., Smorodinsky S.: Conflict-free coloring of points and simple regions in the plane. Discrete Comput. Geom. 34 (2005), 47–70. DOI 10.1007/s00454-005-1162-6 | MR 2140882 | Zbl 1066.05064
[14] Iyer A.V., Ratliff H.R., Vijayan G.: Optimal node ranking of trees. Inform. Process. Lett. 28 (1988), 225–229. DOI 10.1016/0020-0190(88)90194-9 | MR 0958825 | Zbl 0661.68063
[15] Jordan C.: Sur les assemblages de lignes. J. Reine Angew. Math. 70 (1869), 185–190.
[16] Katchalski M., McCuaig W., Seager S.: Ordered colourings. Discrete Math. 142 (1995), 141–154. DOI 10.1016/0012-365X(93)E0216-Q | MR 1341442 | Zbl 0842.05032
[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
[18] Lipton R.J., Tarjan R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. DOI 10.1137/0136016 | MR 0524495 | Zbl 0432.05022
[19] Nešetřil J., Ossona de Mendez P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin. 27 (2006), 1022–1041. DOI 10.1016/j.ejc.2005.01.010 | MR 2226435
[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).
[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
[22] Pezarski A., Zmarz M.: Non-repetitive $3$-coloring of subdivided graphs. Electron. J. Combin. 16 (2009), N15. MR 2515755 | Zbl 1165.05325
[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.
[24] Schäffer A.A.: Optimal node ranking of trees in linear time. Inform. Process. Lett. 33 (1989), no. 2, 91–96. DOI 10.1016/0020-0190(89)90161-0 | MR 1031599
[25] Thue A.: Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl 7 (1906), 1–22.
Search
Partner of
