×

Alternating signed bipartite graphs and difference-1 colourings. (English) Zbl 1447.05098

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.

MSC:

05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
15B36 Matrices of integers

Software:

ROBBINS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brualdi, R.; Kiernan, K.; Meyer, S.; Schroeder, M., Patterns of alternating sign matrices, Linear Algebra Appl., 438, 10, 3967-3990 (2013) · Zbl 1281.15034
[2] Mills, W. H.; Robbins, D. P.; Rumsey, H., Proof of the Macdonald Conjecture, Invent. Math., 66, 73-87 (1982) · Zbl 0465.05006
[3] Dodgson, C. L., Condensation of determinants, being a new and brief method for computing their arithmetical values, Proc. R. Soc. Lond., 15, 150-155 (1866)
[4] Zeilberger, D., Proof of the refined alternating sign matrix conjecture, N.Y. J. Math., 2, 59-68 (1996) · Zbl 0877.05004
[5] Kuperberg, G., Another proof of the alternative-sign matrix conjecture, Int. Math. Res. Not., 1996, 3, 139-150 (1996) · Zbl 0859.05027
[6] Doran IV, W. F., A connection between alternating sign matrices and totally symmetric self-complementary plane partitions, J. Comb. Theory, Ser. A, 64, 289-310 (1993) · Zbl 0795.05008
[7] Colomo, F.; Pronko, A. G., Square ice, alternating sign matrices, and classical orthogonal polynomials, J. Stat. Mech. Theory Exp., 1, 005, 33 (2005) · Zbl 1072.82514
[8] Bressoud, David M., Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Mathematical Associations of America (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0944.05001
[9] Catral, Minerva; Lin, Minghua; Olesky, D. D.; van den Driessche, P., Inverses and eigenvalues of diamond alternating sign matrices, Spec. Matrices, 2, 1 (2014) · Zbl 1310.15008
[10] Brualdi, R.; Dahl, G., Alternating sign matrices and hypermatrices, and a generalization of latin squares, Adv. Appl. Math., 95, 116-151 (2018) · Zbl 1379.05020
[11] Ford, L. R.; Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8, 399-404 (1956) · Zbl 0073.40203
[12] Edmonds, J.; Karp, M., Theoretical improvements in algorithmic efficiency for network flow problems, J. Assoc. Comput. Mach., 19, 2, 248-264 (1972) · Zbl 0318.90024
[13] Hall, P., On representatives of subsets, J. Lond. Math. Soc., 10, 26-30 (1935) · JFM 61.0067.01
[14] Gale, D., A theorem on flows in networks, Pac. J. Math., 7, 1073-1082 (1975) · Zbl 0087.16303
[15] Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Can. J. Math., 9, 371-377 (1957) · Zbl 0079.01102
[16] Brualdi, R., Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl., 33, 159-231 (1980) · Zbl 0448.05047
[17] Lawler, E. L., Matroid intersection algorithms, Math. Program., 9, 1, 31-56 (1975) · Zbl 0315.90039
[18] Edmonds, J., Matroid intersection, Ann. Discrete Math., 4, 39-49 (1979) · Zbl 0416.05025
[19] Firla, R. T.; Spille, B.; Weismantel, R., Algorithmic characterization of bipartite b-matching and matroid intersection, Lect. Notes Comput. Sci., 2570, 48-63 (2003) · Zbl 1024.90055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.