General Information
| Student: | Gaurav Kucheriya |
|---|---|
| Office: | CoRE 409 |
| School: | Charles University |
| Contact: | gaurav.kucheriya-at-rutgers.edu |
| Project: | Graph coloring and orientation |
| Mentor: | Sophie Spirkl |
| Team members: | Barbora Dohnalova and Jiri Kalvoda |
| Other webpages: | Main webpage and REU 2022 |
I am part of a group of students from Charles University that includes Ondrej Chwiedziuk, Tomas Cizek, Barbora Dohnalova, Guillermo Gamboa, Jiri Kalvoda, Kyrylo Karlov, Volodymyr Kuznietsov, Josef Matejka, Jakub Petr and Ondrej Sladky.
Project Description
Our focus is on categorizing the graph families that accept a particular type of orientation known as KT orientation (named after Kierstead and Trotter).Consider a graph with proper coloring. Let i and j be any two colors in this coloring. To obtain the KT orienation, all edges connecting vertices of color i to those of color j are oriented from color i to color j, whenever they exist. For more details, see the slides.
Research project log
Week 0
- Finally, after quite a long and time-consuming bureaucratic process, the Czech REU 2023 group arrived in Prague, albeit two days after the program officially started.
- We just had a couple of days to prepare the slides for the first presentation introducing our problem.
- Had a short meeting with Sophie to discuss about this presentation on Friday after a couple of orientations.
Week 1
- Introduced the problem at the seminar.
- Attended a seminar by Dimitris Metaxas on "Scalable and Explainable AI Analytics for Computer Vision and Medical Applications".
- We found a couple of non-examples and examples.
Week 2 (plan)
- Attending the DIMACS graph algorithms workshop.
- Meeting with Sophie on Friday.
- Biking along the D&R Canal to Princeton.
References
-
- [1] H. A. Kierstead, W. T. Trotter, Colorful induced subgraphs . Discrete Math. 101 (1992) 165-169.
- [2] A. Scott, P. Seymour. A survey of χ-boundedness. Journal of Graph Theory 95 (2020) 473–504.
- [3] É. Bonnet, R. Borneuf, J. Duron, C. Geniet, S.Thomassé and N. Trotignon. A tamed family of triangle-free graphs with unbounded chromatic number. manuscript, arXiv:2304.04296.
Acknowledgements
- This work was carried out while the author was a participant in the 2023 DIMACS REU program, supported by CoSP,
a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748. The author is grateful to the organizers at Rutgers and Charles for providing this opportunity.