| Meno: | Filip
|
|---|
| Priezvisko: | Zrubák
|
|---|
| Názov: | Circular chromatic index of 4-regular graphs
|
|---|
| Vedúci: | doc. RNDr. Ján Mazák, PhD
|
|---|
| Rok: | 2025
|
|---|
| Kµúčové slová: | circular chromatic index, edge coloring, 4-regular graphs, circulants
|
|---|
| Abstrakt: | This thesis investigates the circular chromatic index of 4-regular graphs, a refinement of the classical chromatic index that captures more precise edge coloring properties. We combine structural graph analysis with computational verification using SAT solvers.
We show that certain subgraphs (modified $K_5$) enforce circular chromatic index at least 5. We also prove that the circular chromatic index of the circulant graphs $C_{2n+1}(1,2)$ for all $n > 5$ equals 9/2. Further, we investigate graphs with circular chromatic index $14/3$ through decompositions at cut-vertices and formulate questions about the existence of infinite families with this circular chromatic index.
|
|---|