12 papers
Acyclic Dichromatic Number of Tournaments: these are the Champions
Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2
The acyclic dichromatic number of an oriented graph is the minimum size of a vertex-partition such that the digraphs induced by any single part are acyclic, and the oriented bipart…
Bouchet's conjecture for cyclically 5-edge-connected, cubic signed graphs
Kathryn Nurse
A 1983 conjecture of Bouchet states that every flow-admissible signed graph has a nowhere-zero six-flow. We prove this conjecture for cyclically five-edge-connected, cubic signed g…
Nowhere-zero 8-flows in 3-edge-connected signed graphs
Matt DeVos, Kathryn Nurse, Robert Šámal
In 1983, A. Bouchet extended W.T. Tutte's notion of nowhere-zero flows to signed graphs, and conjectured that every flow-admissible signed graph has a nowhere-zero 6-flow. In this…
On the Ban-Linial Conjecture
Matt DeVos, Kathryn Nurse
Let be a graph and let be a partition of . This partition is called external or unfriendly if every has at least as many neighbours in …
Density of -critical signed graphs
Laurent Beaudou, Penny Haxell, Kathryn Nurse +2
We say that a signed graph is -critical if it is not -colorable but every one of its proper subgraphs is -colorable. Using the definition of colorability due to Naserasr,…
Nowhere-zero 8-flows in cyclically 5-edge-connected, flow-admissible signed graphs
Matt DeVos, Kathryn Nurse, Robert Sámal
In 1983, Bouchet proved that every bidirected graph with a nowhere-zero integer-flow has a nowhere-zero 216-flow, and conjectured that 216 could be replaced with 6. This paper show…
Balanced-chromatic number and Hadwiger-like conjectures
Andrea Jiménez, Jessica McDonald, Reza Naserasr +2
Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward…
A short proof of Seymour's 6-flow theorem
Matt DeVos, Kathryn Nurse
We give a compact variation of Seymour's proof that every -edge-connected graph has a nowhere-zero -flow.
Cycles through two edges in signed graphs
Matt DeVos, Kathryn Nurse
We give a characterization of when a signed graph with a pair of distinguished edges has the property that all cycles containing both and have t…
Group connectivity of 3-edge-connected signed graphs
Alejandra Brewer Castano, Jessica McDonald, Kathryn Nurse
Jaeger, Linial, Payan, and Tarsi introduced the notion of -connectivity for graphs in 1992, and proved a decomposition for cubic graphs from which -connectivity follows for a…
Another proof of Seymour's 6-flow theorem
Matt DeVos, Jessica McDonald, Kathryn Nurse
In 1981 Seymour proved his famous 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero flow in the group (in fact, he…
A Maximum Linear Arrangement Problem on Directed Graphs
Matt DeVos, Kathryn Nurse
We propose a new arrangement problem on directed graphs, Maximum Directed Linear Arrangement (MaxDLA). This is a directed variant of a similar problem for undirected graphs, in whi…