Search

ABSTRACT Applications of graph colouring often involve taking restrictions into account, and it is desirable to have multiple (disjoint) solutions. In the optimal case, where there is a partition into disjoint colourings, we speak of a packing. However, even for complete bipartite graphs, the list chromatic number can be arbitrarily large, and its exact determination is generally difficult. For the packing variant, this question becomes even harder. In this paper, we study the correspondence‐ and list‐packing numbers of (asymmetric) complete bipartite graphs. In the most asymmetric cases, Latin squares come into play. Our results show that every z ∈ Z + \{ 3 } $z\in {{\mathbb{Z}}}^{+}\backslash \{3\}$ can be equal to the correspondence packing number of a graph. We disprove a recent conjecture that relates the list packing number and the list flexibility number. Additionally, we improve the threshold functions for the correspondence packing variant. [ABSTRACT FROM AUTHOR]

For f:R2→R, let ΓR(f) be a two‐dimensional algebraically defined graph, that is, a bipartite graph where each partite set is a copy of R2 and two vertices (a,a2) and [x,x2] are adjacent if and only if a2+x2=f(a,x). It is known that ΓR(XY) has girth 6 and can be extended to the point‐line incidence graph of the classical real projective plane. However, it was unknown whether there exists f∈R[X,Y] such that ΓR(f) has girth 6 and is nonisomorphic to ΓR(XY). This paper answers this question affirmatively and thus provides a construction of a nonclassical real projective plane. This paper also studies the diameter and girth of ΓR(f) for families of bivariate functions f. [ABSTRACT FROM AUTHOR]

An edge e of a matching covered graph G is removable if G−e is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K4 and C6¯ has at least Δ−2 removable edges. A brick G is near‐bipartite if it has a pair of edges {e1,e2} such that G−{e1,e2} is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G with at least six vertices, every vertex of G, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G has at least |V(G)|−62 removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]