BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

A coloring algorithm for $4K_1$-free line graphs Maffray, Frederic


When $F$ is a set of four-vertex graphs the complexity of the vertex coloring problem in the class of $F$-free graphs is known, with three exceptions: $F = \{\text{claw}, 4K_1\}$, $F = \{\text{claw}, 4K_1, \text{co-diamond}\}$, and $F = \{C_4, 4K_1\}$. We study the coloring problem for $\{\text{claw},4K_1\}$-free graphs. We solve the vertex coloring problem for a subclass of this class which contains the class of $4K_1$-free line graphs. Our result implies that the chromatic index of a graph with no matching of size four can be computed in polynomial time. Joint work with Dallas J. Fraser, Angele M. Hamel, Chinh T. Hoang (Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International