Graf je rozložitelný, pokud pro každou $k$-tici kladných celých čísel $m_1,...,m_k$ takovou, že $m_1+...+m_k=m=|E|$ existuje rozklad hran na množiny $E_1,...,E_k$ a podgraf indukovaný hranami $E_i$ je souvislý pro $i=1,...,k$. Je známo, ža každý hranově $4$-souvislý graf je rozložitelný a na druhou stranu existuje příklad $2$-souvislého grafu, který rozložitelný není. Úkolem studenta je prozkoumat vliv různých grafových parametrů na rozložitelnost grafu, zejména se zaměřit na $3$-souvislé grafy.
Seznam odborné literatury
Matoušek, Nešetřil: Kapitoly z diskrétní matematiky. Karolinum 2007
Diestel: Graph Theory. Springer 2010
Barát, Thomassen: Dividing the edges of a graph into connected subgraphs of prescribed size. Eurocomb 2003
Předběžná náplň práce
Graf je rozložitelný, pokud pro každou $k$-tici kladných celých čísel $m_1,...,m_k$ takovou, že $m_1+...+m_k=m=|E|$ existuje rozklad hran na množiny $E_1,...,E_k$ a podgraf indukovaný hranami $E_i$ je souvislý pro $i=1,...,k$. Je známo, ža každý hranově $4$-souvislý graf je rozložitelný a na druhou stranu existuje příklad $2$-souvislého grafu, který rozložitelný není.
- zadáno a potvrzeno stud. odd.