7 papers · 1 filter
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…