General Information
| Student: | BA BOA DOHNALOVÁ |
|---|---|
| Office: | CoE 450 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Contact: | barbora.dohnalova (at) rutgers.edu |
| Project: | KT-orientations in graphs |
| Collaborators: | Jiří Kalvoda and Gaurav Kucheryia |
| Mentor: | Sophie Spirkl |
I am part of a group of students from Charles University that includes Ondrej Chwiedziuk, Tomas Cizek, Jiri Kalvoda, Kyrylo Karlov, Volodymyr Kuznietsov, Gaurav Kucheriya, Josef Matejka, G.A. Gamboa Quintero, Jakub Petr and Ondrej Sladky.
Project Description
- Graph has a KT-orientation if for each two vertices u and v there is at most one directed path between them. We would like to know which graphs do and do not have a KT-orientation. This question is closely related to graph coloring.
esearch Log
Week 0 (01/06-02/06)
- Even though we just arrived, we managed to find some non-examples. Jirka created a program which helps us decide whether a graph has a KT-orientation.
Week 1 (05/06-09/06)
- We used Jirka's program to find non-examples not containing a four cycle. Now we are trying to understand what goes wrong with them. We would like to be able to modify these constructions for other purposes.
Week 2 (12/06 - 16/06)
- We got stuck with the research - we would like to find graphs with large girth without KT orientations but this problem seems quite difficult (and we cannot use computer anymore, since the input is just too big). We also attended the graph algorithms workshop so we didn't have so much time for the research. On Friday we have a meeting with Sophie, so hopefully she can help us to get unstuck.
Week 3 (19/06 - 23/06)
- On Monday we met with Sophie. We tried to think about one particular construction of a graph and to prove something about its structure. Since my life motto is "If you cannot solve a problem just transform it into a different problem you also cannot solve," I tried to come up with alternative definitions of a KT-orientation.
Since Monday we are suffering from a terrible problem - we ran out of orange juice! Now we are not able to focus on our research! Fortunately on Thursday we managed to finally resolve this problem.
Week 4 (26/06 - 30/06)
- On Monday we attended Martin Balko's talk about Ramsey theory. Then he managed to find a way how to use Ramsey theory for our problem, and it seems that his idea might work. On Thursday we departed on a trip to Canada to meet with Sophie in person. Together with Martin's idea, it seems that the KT-orientation question is basically settled - it's hard. Even though we cannot decide for arbitrary graph whether it has a KT-orientation, Sophie suggested some restrictions we might try to impose on our graphs and see if it makes the question easier.
Week 5 (03/07 - 07/07)
- At the meeting with Sophie we managed to solve the case with restricted degrees. We started writing down our results.
Week 6 (10/05 - 14/06)
- We continued writing down our result. On Thursday we went on a fild trip to IBM. I really liked the presentation about MolGPT.
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 Barbora Dohnalová 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.