A polynomial time algorithm for the fractional $ f $-density
- Series
- Graph Theory Seminar
- Time
- Tuesday, February 21, 2023 - 15:45 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Guoning Yu – Georgia State University – gyu6@gsu.edu
The edge-coloring problem (ECP) for a multigraph $G=(V, E)$ is to color its edges with minimum number of colors such that no two adjacent vertices receive the same color. ECP can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) of $G$, denoted by $\chi^{\prime}(G)$ (resp. $\chi^*(G)$). Let $\Delta(G)$ be the maximum degree of $G$ and let $ \mathcal{W}^*(G) $ be the fractional density of $G$, defined by $$ \mathcal{W}^*(G) = \max _{U \subseteq V,|U| \geq 2}\frac{|E(U)|}{\lfloor|U|/2\rfloor}. $$ Seymour showed that $\chi^*(G)=\max \{\Delta(G), \mathcal{W}^*(G)\}$. Moreover, the Goldberg-Seymour Conjecture is confirmed Chen, Jing, and Zang states that $\chi^{\prime}(G) \leq \max \{\Delta(G)+1,\lceil\mathcal{W}^*(G)\rceil\}$. Chen, Zang and Zhao developed an algorithm that calculates $ \mathcal{W}^*(G) $ in strongly polynomial time. Inspired by their results, we consider the fractional $ f $-edge-coloring problem ($ f $-FECP) for a given function $ f:V\to \mathbb N_+ $, which is a generalization of FECP: each spanning subgraph induced by a color class has degree at most $ f(v) $ at each vertex $ v\in V $. We give a strongly polynomial-time algorithm for calculating the corresponding fractional $ f $-density $$ \mathcal{W}^*_{f}(G)=\max _{U \subseteq V,|U| \geq 2}\frac{|E(U)|}{\lfloor f(U) / 2\rfloor}. $$