Balanced bipartite graphs may be completely star-factored

We conclude the study of complete K_1,q-factorizations of complete bipartite graphs of the form K_n,n and show that, so long as the obvious Basic Arithmetic Conditions are satisfied, such complete factorizations must exist. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 407–415, 1997     

Crossing minimization in weighted bipartite graphs

Given a bipartite graph G=(L₀,L₁,E) and a fixed ordering of the nodes in L₀, the problem of finding an ordering of the nodes in L₁ that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Star coloring bipartite planar graphs

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009     

An extremal bandwidth problem for bipartite graphs

This paper discusses the problem of finding the maximum number of edges E(m, n, B) in a bipartite graph having partite set sizes m and n and bandwidth B. Exact values for E(m, n, B) are found for many cases. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 278–289, 2000     

Dynamic list coloring of bipartite graphs

A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of G, denoted by χ₂(G), is called the dynamic chromatic number of G. The least integer k, such that if every vertex of G is assigned a list of k colors, then G has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of G, denoted by ch(G) (resp. the dynamic choice number, denoted by ch₂(G)). It was recently conjectured (Akbari et al. (2009) [1]) that for any graph G, ch₂(G)=max(ch(G),χ₂(G)). In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph G with ch(G)=χ₂(G)=3 and ch₂(G)=4. Then, for any integer k≥5, we construct a bipartite graph G_k such that ch(G_k)=χ₂(G_k)=3 and ch₂(G)≥k.     

Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs.     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

Weakly bipartite graphs and the Max-cut problem

A new class of graphs, called weakly bipartite graphs, is introduced. A graph is called weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class of bipartite graphs and the class of planar graphs. It is shown that the max-cut problem can be solved in polynomial time for weakly bipartite graphs. The polynomical algorithm presented is based on the ellipsoid method and an algorithm that computes a shortest path of even length.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

Bipartite graphs with the maximum sum of squares of degrees

In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.     

Restricted unimodular chordal graphs

A chordal graph is called restricted unimodular if each cycle of its vertex‐clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct them by starting from block graphs and multiplying vertices subject to a certain restriction, which leads to a linear‐time recognition algorithm. We show how they are related to other classes such as distance‐hereditary chordal graphs and strongly chordal graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 121–136, 1999     

Largest planar matching in random bipartite graphs

For a distribution ?? over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ??. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ?? is the uniform distribution over the k‐regular bipartite graphs on W and M. For k = o(n^1/4), we establish that $L(n) \slash \sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n² possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γ_p in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002