Alternating signed bipartite graphs and difference-1 colourings (Q2197215): Difference between revisions

Coloring in graphs is an important area. The authors investigated 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 theme is when does a given bipartite graph admit an ASBG-colouring; a 2-edge colouring such that the resulting graph is an ASBG. The authors introduce the concept of a difference-1 colouring, a relaxation of the concept of an ASBG-colouring, and presented 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 \(r(v)\). This article is interesting, many fruitful avenues are highlighted. The authors discussed the results intelligently and fruitfully. The article is useful to many researchers working in the area of coloring.