Alternating signed bipartite graphs and difference-1 colourings

O'Brien, Cian, Jennings, Kevin and Quinlan, Rachel 2020. Alternating signed bipartite graphs and difference-1 colourings. Linear Algebra and its Applications 604 , pp. 370-398. 10.1016/j.laa.2020.06.030

PDF - Published Version Available under License Creative Commons Attribution. Download (1MB)

Abstract

We investigate a class of 2-edge coloured bipartite graphs known as alternating signed bipartite graphs (ASBGs) that encode the information in alternating sign matrices. The central question is when a given bipartite graph admits an ASBG-colouring; a 2-edge colouring such that the resulting graph is an ASBG. We introduce the concept of a difference-1 colouring, a relaxation of the concept of an ASBG-colouring, and present a set of necessary and sufficient conditions for when a graph admits a difference-1 colouring. The relationship between distinct difference-1 colourings of a particular graph is characterised, and some classes of graphs for which all difference-1 colourings are ASBG-colourings are identified. One key step is Theorem 3.4.6, which generalises Hall's Matching Theorem by describing a necessary and sufficient condition for the existence of a subgraph H of a bipartite graph in which each vertex v of H has some prescribed degree .

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	0024-3795
Date of First Compliant Deposit:	16 September 2021
Date of Acceptance:	29 June 2020
Last Modified:	06 May 2023 10:51
URI:	https://orca.cardiff.ac.uk/id/eprint/143852

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item