Showing math.COShow all
3 papers · 1 filter
math.CO2026
Decomposing tournaments into comparability graphs
Pierre Aboulker, Logan Crew, Julien Duron +7
In this note, we introduce the \emph{partial order decomposition number} of a digraph , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
math.CO2024
Graphs without a 3-connected subgraph are 4-colorable
Édouard Bonnet, Carl Feghali, Tung Nguyen +4
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…
math.CO2024
Dichromatic Number and Cycle Inversions
Pierre Charbit, Stéphan Thomassé
The results of this note were stated in the first author PhD manuscript in 2006 but never published. The writing of a proof given there was slightly careless and the proof itself s…