Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.     

Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.     

A maximal zero-free interval for chromatic polynomials of bipartite planar graphs

It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs.     

A scale-free graph model based on bipartite graphs

Most biological networks have some common properties, on which models have to fit. The main one is that those networks are scale-free, that is that the distribution of the vertex degrees follows a power-law. Among the existing models, the ones which fit those characteristics best are based on a time evolution which makes impossible the analytic calculation of the number of motifs in the network. Focusing on applications, this calculation is very important to decompose networks in a modular manner, as proposed by Milo et al.. On the contrary, models whose construction does not depend on time, miss one or several properties of real networks or are not computationally tractable. In this paper, we propose a new random graph model that satisfies the global features of biological networks and the non-time-dependency condition. It is based on a bipartite graph structure, which has a biological interpretation in metabolic networks.     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

A characterization of cycle-forced bipartite graphs

A forced cycle$C$ of a graph $G$ is a cycle in $G$ such that $G?V\left(C\right)$ has a unique perfect matching. A graph $G$ is a cycle-forced graph if every cycle in $G$ is a forced cycle. In this paper, we give a characterization of cycle-forced hamiltonian bipartite graphs.     

Hamiltonian and long paths in bipartite graphs with connectivity

Let G be a graph, $\nu (G)$ the order of G, $\kappa (G)$ the connectivity of G and k a positive integer such that $k\le (\nu (G)?2)/2$. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets $V_1$ and $V_2$ is defined to be Hamiltonian-laceable if such that $|V_1|=|V_2|$ and for every pair of vertices $p\in V_1$ and $q\in V_2$, there exists a Hamiltonian path in G with endpoints p and q, or $|V_1|=|V_2|+1$ and for every pair of vertices $p,q\in V_1,p\ne q$, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition $(X,Y)$. Define $bn(G)$ to be a maximum integer such that $0\le bn(G)<min\{|X|,|Y|\}$ and (1) for each non-empty subset S of X, if $|S|\le |X|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|X|?bn(G)<|S|\le |X|$, then $N(S)=Y$; and (2) for each non-empty subset S of Y, if $|S|\le |Y|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|Y|?bn(G)<|S|\le |Y|$, then $N(S)=X$; and (3) $bn(G)=0$ if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|$ and $bn(G)>0$. In this paper, we show that if $\nu (G)\le 2\kappa (G)+4bn(G)?4$, then G is Hamiltonian-laceable; or if $\nu (G)>6bn(G)?2$, then for every pair of vertices $x\in X$ and $y\in Y$, there is an $(x,y)$-path P in G with $|V(P)|\ge 6bn(G)?2$. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs

In 1956, W.T. Tutte proved that a 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

A note on the minimum total coloring of planar graphs

Graph coloring is an important tool in the study of optimization,computer science,network design,e.g.,file transferring in a computer network,pattern matching,computation of Hessians matrix and so on.In this paper,we consider one important coloring,vertex coloring of a total graph,which is also called total coloring.We consider a planar graph G with maximum degree Δ(G)≥8,and proved that if G contains no adjacent i,j-cycles with two chords for some i,j∈{5,6,7},then G is total-(Δ+1)-colorable.     

Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 9

Let $k$ be a positive integer. An adjacent vertex distinguishing (for short, AVD) total-$k$-coloring of a graph $G$ is a proper total-$k$-coloring of $G$ such that any two adjacent vertices have different color sets, where the color set of a vertex $v$ contains the color of $v$ and the colors of its incident edges. It was conjectured that any graph with maximum degree $\Delta$ has an AVD total-($\Delta +3$)-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-($\Delta +2$)-coloring and the bound $\Delta +2$ is sharp.     

Relation between the H-rank of a mixed graph and the rank of its underlying graph

Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $\stackrel{?}{G}$ is obtained from $G$ by orienting some of its edges. Let $H\left(\stackrel{?}{G}\right)$ denote the Hermitian adjacency matrix of $\stackrel{?}{G}$ and $A\left(G\right)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $\stackrel{?}{G}$ (resp. $G$), written as $rk\left(\stackrel{?}{G}\right)$ (resp. $r\left(G\right)$), is the rank of $H\left(\stackrel{?}{G}\right)$ (resp. $A\left(G\right)$). Denote by $d\left(G\right)$ the dimension of cycle space of $G$, that is $d\left(G\right)=\left|E_G\right|?\left|V_G\right|+\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $\stackrel{?}{G}$ and the rank of $G$. We first show that $?2d\left(G\right)?rk\left(\stackrel{?}{G}\right)?r\left(G\right)?2d\left(G\right)$ for every mixed graph $\stackrel{?}{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently.