||Peeling in graphs
If we repeatively remove a vertex with a minimal degree, then a peeling number of that
vertex is the maximal degree which we have already removed. In this project we are looking at graphs in which
all of their vertices have the same peeling number and we are trying to characterize them. The next aim is to
develope a data structure which can update a graphs and answer a peeling number for a single vertex
in good amortized time complexity.
- Week 1:
- Choosing a topic for a work. Introduction into several of themes, I have chosen Peeling in graphs and
I did first steps in this theme.
- Week 2:
- First steps in peeling. Find a construction of FP_k class. Looking at online peeling problem and finding out
that this problem is realy hard.
- Week 3:
- General construction of FP_k class, description of extremal cases of a graphs. In k-degenerate graph
there exists an independent set which we remove and get a graph which is at motst (k-1)-degenerate.
- Week 4:
- Generalization of a trees and its equality with extremal cases of FP_k. We solved
a solitaire problem from some math magazine on a bridge workshop.
- Week 5:
- I started writing the things I had already found.
- Week 6:
- Continue writing and finding some new things.
- Week 7:
- Finishing a write up and making a presentation.