Neochromatica

Panagiotis Cheilaris; Ernst Specker; Stathis Zachos

Commentationes Mathematicae Universitatis Carolinae (2010)

  • Volume: 51, Issue: 3, page 469-480
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Cheilaris, Panagiotis, Specker, Ernst, and Zachos, Stathis. "Neochromatica." Commentationes Mathematicae Universitatis Carolinae 51.3 (2010): 469-480. <http://eudml.org/doc/38143>.

@article{Cheilaris2010,
abstract = {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.},
author = {Cheilaris, Panagiotis, Specker, Ernst, Zachos, Stathis},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph coloring; paths; conflict-free; graph coloring; path; conflict-free},
language = {eng},
number = {3},
pages = {469-480},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Neochromatica},
url = {http://eudml.org/doc/38143},
volume = {51},
year = {2010},
}

TY - JOUR
AU - Cheilaris, Panagiotis
AU - Specker, Ernst
AU - Zachos, Stathis
TI - Neochromatica
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2010
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 51
IS - 3
SP - 469
EP - 480
AB - 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.
LA - eng
KW - graph coloring; paths; conflict-free; graph coloring; path; conflict-free
UR - http://eudml.org/doc/38143
ER -

References

top
  1. Allouche J.-P., Shallit J., Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003. Zbl1086.11015MR1997038
  2. Alon N., Grytczuk J., Hałuszczak M., Riordan O., 10.1002/rsa.10057, Random Structures Algorithms 21 (2002), no. 3–4, 336–346. MR1945373DOI10.1002/rsa.10057
  3. Alon N., Smorodinsky S., 10.1142/S0218195908002775, Internat. J. Comput. Geom. Appl. 18 (2008), no. 6, 599–604. Zbl1184.05038MR2479564DOI10.1142/S0218195908002775
  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. MR2671334
  5. Bar-Noy A., Cheilaris P., Smorodinsky S., 10.1145/1383369.1383375, ACM Trans. Algorithms 4 (2008), no. 4, 18pp. MR2446963DOI10.1145/1383369.1383375
  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., 10.1137/S0097539704446682, SIAM J. Comput. 36 (2007), no. 5, 1342–1359. MR2284084DOI10.1137/S0097539704446682
  8. Currie J.D., There are ternary circular square-free words of length n for n ≥ 18 , Electron. J. Combin. 9 (2002), no. 1, N10. Zbl1057.68081MR1936865
  9. Djidjev H.N., 10.1137/0603022, SIAM J. Algebraic Discrete Methods 3 (1982), 229–240. Zbl0503.05057MR0655563DOI10.1137/0603022
  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. MR2080082
  11. Even G., Lotker Z., Ron D., Smorodinsky S., 10.1137/S0097539702431840, SIAM J. Comput. 33 (2003), 94–136. Zbl1069.68120MR2033655DOI10.1137/S0097539702431840
  12. Grytczuk J., Nonrepetitive graph coloring, Graph Theory, Trends in Mathematics, Birkhäuser, Basel, 2007, pp. 209–218. Zbl1120.05029MR2279177
  13. Har-Peled S., Smorodinsky S., 10.1007/s00454-005-1162-6, Discrete Comput. Geom. 34 (2005), 47–70. Zbl1066.05064MR2140882DOI10.1007/s00454-005-1162-6
  14. Iyer A.V., Ratliff H.R., Vijayan G., 10.1016/0020-0190(88)90194-9, Inform. Process. Lett. 28 (1988), 225–229. Zbl0661.68063MR0958825DOI10.1016/0020-0190(88)90194-9
  15. Jordan C., Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869), 185–190. 
  16. Katchalski M., McCuaig W., Seager S., 10.1016/0012-365X(93)E0216-Q, Discrete Math. 142 (1995), 141–154. Zbl0842.05032MR1341442DOI10.1016/0012-365X(93)E0216-Q
  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. Zbl0272.68054
  18. Lipton R.J., Tarjan R.E., 10.1137/0136016, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. Zbl0432.05022MR0524495DOI10.1137/0136016
  19. Nešetřil J., Ossona de Mendez P., 10.1016/j.ejc.2005.01.010, European J. Combin. 27 (2006), 1022–1041. MR2226435DOI10.1016/j.ejc.2005.01.010
  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. MR2038496
  22. Pezarski A., Zmarz M., Non-repetitive 3 -coloring of subdivided graphs, Electron. J. Combin. 16 (2009), N15. Zbl1165.05325MR2515755
  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., 10.1016/0020-0190(89)90161-0, Inform. Process. Lett. 33 (1989), no. 2, 91–96. MR1031599DOI10.1016/0020-0190(89)90161-0
  25. Thue A., Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl 7 (1906), 1–22. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.