2 papers
math.CO2019
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
math.CO2016
The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs
Frédéric Maffray, Lucas Pastor
We present a polynomial-time algorithm that finds a maximum weight stable set in a graph that does not contain as an induced subgraph an induced path on six vertices or a bull (the…