On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

The 2-surviving rate of planar graphs without 5-cycles

Let \(G\) be a connected graph with \(n\ge 2\) vertices. Let \(k\ge 1\) be an integer. Suppose that a fire breaks out at a vertex \(v\) of \(G\). A firefighter starts to protect vertices. At each step, the firefighter protects \(k\)-vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let \(\hbox {sn}_k(v)\) denote the maximum number of vertices in \(G\) that the firefighter can save when a fire breaks out at vertex \(v\). The \(k\)-surviving rate \(\rho _k(G)\) of \(G\) is defined to be \(\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)\), which is the average proportion of saved vertices. In this paper, we prove that if \(G\) is a planar graph with \(n\ge 2\) vertices and without 5-cycles, then \(\rho _2(G)>\frac{1}{363}\).     

Cacti with the smallest,second smallest,and third smallest Gutman index

The Gutman index (also known as Schultz index of the second kind) of a graph \(G\) is defined as \(Gut(G)=\sum \nolimits _{u,v\in V(G)}d(u)d(v)d(u, v)\). A graph \(G\) is called a cactus if each block of \(G\) is either an edge or a cycle. Denote by \(\mathcal {C}(n, k)\) the set of connected cacti possessing \(n\) vertices and \(k\) cycles. In this paper, we give the first three smallest Gutman indices among graphs in \(\mathcal {C}(n, k)\), the corresponding extremal graphs are characterized as well.     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

Further results on the reciprocal degree distance of graphs

The reciprocal degree distance of a simple connected graph \(G=(V_G, E_G)\) is defined as \(\bar{R}(G)=\sum _{u,v \in V_G}(\delta _G(u)+\delta _G(v))\frac{1}{d_G(u,v)}\), where \(\delta _G(u)\) is the vertex degree of \(u\), and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\). The reciprocal degree distance is an additive weight version of the Harary index, which is defined as \(H(G)=\sum _{u,v \in V_G}\frac{1}{d_G(u,v)}\). In this paper, the extremal \(\bar{R}\)-values on several types of important graphs are considered. The graph with the maximum \(\bar{R}\)-value among all the simple connected graphs of diameter \(d\) is determined. Among the connected bipartite graphs of order \(n\), the graph with a given matching number (resp. vertex connectivity) having the maximum \(\bar{R}\)-value is characterized. Finally, sharp upper bounds on \(\bar{R}\)-value among all simple connected outerplanar (resp. planar) graphs are determined.     

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.     

An approximation algorithm for maximum weight budgeted connected set cover

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set \(X\), a collection of sets \({\mathcal {S}}\subseteq 2^X\), a weight function \(w\) on \(X\), a cost function \(c\) on \({\mathcal {S}}\), a connected graph \(G_{\mathcal {S}}\) (called communication graph) on vertex set \({\mathcal {S}}\), and a budget \(L\), the MWBCSC problem is to select a subcollection \({\mathcal {S'}}\subseteq {\mathcal {S}}\) such that the cost \(c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L\), the subgraph of \(G_{\mathcal {S}}\) induced by \({\mathcal {S'}}\) is connected, and the total weight of elements covered by \({\mathcal {S'}}\) (that is \(\sum _{x\in \bigcup _{S\in {\mathcal {S'}}}S}w(x)\)) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio \(O((\delta +1)\log n)\), where \(\delta \) is the maximum degree of graph \(G_{\mathcal {S}}\) and \(n\) is the number of sets in \({\mathcal {S}}\). In particular, if every set has cost at most \(L/2\), the performance ratio can be improved to \(O(\log n)\).     

2-Edge connected dominating sets and 2-Connected dominating sets of a graph

A \(k\)-connected (resp. \(k\)-edge connected) dominating set \(D\) of a connected graph \(G\) is a subset of \(V(G)\) such that \(G[D]\) is \(k\)-connected (resp. \(k\)-edge connected) and each \(v\in V(G)\backslash D\) has at least one neighbor in \(D\). The \(k\) -connected domination number (resp. \(k\) -edge connected domination number) of a graph \(G\) is the minimum size of a \(k\)-connected (resp. \(k\)-edge connected) dominating set of \(G\), and denoted by \(\gamma _k(G)\) (resp. \(\gamma '_k(G)\)). In this paper, we investigate the relation of independence number and 2-connected (resp. 2-edge-connected) domination number, and prove that for a graph \(G\), if it is \(2\)-edge connected, then \(\gamma '_2(G)\le 4\alpha (G)-1\), and it is \(2\)-connected, then \(\gamma _2(G)\le 6\alpha (G)-3\), where \(\alpha (G)\) is the independent number of \(G\).     

Sparse multipartite graphs as partition universal for graphs with bounded degree

For graphs G and H, let \(G\rightarrow (H,H)\) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote \(\mathcal {H}(\Delta ,n)=\{H:|V(H)|=n,\Delta (H)\le \Delta \}\). For any \(\Delta \) and n, we say that G is partition universal for \(\mathcal {H}(\Delta ,n)\) if \(G\rightarrow (H,H)\) for every \(H\in \mathcal {H}(\Delta ,n)\). Let \(G_r(N,p)\) be the random spanning subgraph of the complete r-partite graph \(K_r(N)\) with N vertices in each part, in which each edge of \(K_r(N)\) appears with probability p independently and randomly. We prove that for fixed \(\Delta \ge 2\) there exist constants r, B and C depending only on \(\Delta \) such that if \(N\ge Bn\) and \(p=C(\log N/N)^{1/\Delta }\), then asymptotically almost surely \(G_r(N,p)\) is partition universal for \(\mathcal {H}(\Delta ,n)\).     

On zero-sum $$\mathbb {Z}_{2j}^k$$-magic graphs

Let \(G = (V,E)\) be a finite graph and let \((\mathbb {A},+)\) be an abelian group with identity 0. Then G is \(\mathbb {A}\)-magic if and only if there exists a function \(\phi \) from E into \(\mathbb {A} - \{0\}\) such that for some \(c \in \mathbb {A}, \sum _{e \in E(v)} \phi (e) = c\) for every \(v \in V\), where E(v) is the set of edges incident to v. Additionally, G is zero-sum \(\mathbb {A}\)-magic if and only if \(\phi \) exists such that \(c = 0\). We consider zero-sum \(\mathbb {A}\)-magic labelings of graphs, with particular attention given to \(\mathbb {A} = \mathbb {Z}_{2j}^k\). For \(j \ge 1\), let \(\zeta _{2j}(G)\) be the smallest positive integer c such that G is zero-sum \(\mathbb {Z}_{2j}^c\)-magic if c exists; infinity otherwise. We establish upper bounds on \(\zeta _{2j}(G)\) when \(\zeta _{2j}(G)\) is finite, and show that \(\zeta _{2j}(G)\) is finite for all r-regular \(G, r \ge 2\). Appealing to classical results on the factors of cubic graphs, we prove that \(\zeta _4(G) \le 2\) for a cubic graph G, with equality if and only if G has no 1-factor. We discuss the problem of classifying cubic graphs according to the collection of finite abelian groups for which they are zero-sum group-magic.     

On the algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into \(V(G)=V_1\cup V_2\cup \cdots \cup V_k\) is called a k-strong subcoloring if \(d(x,y)\ne 2\) in G for every \(x,y\in V_i\), \(1\le i \le k\) where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as \(\chi _{sc}(G)=\text {min}\{ k:G \text { admits a }k\)-\(\text {strong subcoloring}\}\). In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of \(K_{1,r}\)-free split graphs, StrongSubcoloring is in P when \(r\le 3\) and NP-complete when \(r>3\) and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of \(P_4\); otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every \(x,y\in S\), \(d(x,y)= 2\) in G and the cardinality of a maximum strong set in G is denoted by \(\alpha _{s}(G)\). Clearly, \(\alpha _{s}(G)\le \chi _{sc}(G)\). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) \(K_{1,4}\)-free split graphs, and it is polynomial time solvable for (i) trees and (ii) \(P_4\)-free graphs.     

An improved parameterized algorithm for the <Emphasis Type="Italic">p</Emphasis>-cluster vertex deletion problem

In the p-Cluster Vertex Deletion problem, we are given a graph \(G=(V,E)\) and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let \(r=p/k\). In this paper, we design a branching algorithm with time complexity \(O(\alpha ^k+|V||E|)\), where \(\alpha \) depends on r and has a rough upper bound \(\min \{1.618^{1+r},2\}\). With a more precise analysis, we show that \(\alpha =1.28\cdot 3.57^{r}\) for \(r\le 0.219\); \(\alpha =(1-r)^{r-1}r^{-r}\) for \(0.219< r<1/2\); and \(\alpha =2\) for \(r\ge 1/2\), respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity \(O^*(1.84^{p+k})\) and implies that for fixed p the problem can be solved as efficiently as Vertex Cover.     

Crossing edges and faces of line arrangements in the plane

For any natural number \(n\) we define \(f(n)\) to be the minimum number with the following property. Given any arrangement \(\mathcal{A}(\mathcal{L})\) of \(n\) blue lines in the real projective plane one can find \(f(n)\) red lines different from the blue lines such that any edge in the arrangement \(\mathcal{A}(\mathcal{L})\) is crossed by a red line. We define \(h(n)\) to be the minimum number with the following property. Given any arrangement \(\mathcal{A}(\mathcal{L})\) of \(n\) blue lines in the real projective plane one can find \(h(n)\) red lines different from the blue lines such that every face in the arrangement \(\mathcal{A}(\mathcal{L})\) is crossed in its interior by a red line. In this paper we show \(f(n)=2n-o(n)\) and \(h(n)=n-o(n)\).     

Algorithmic aspects of <Emphasis Type="Italic">b</Emphasis>-disjunctive domination in graphs

For a fixed integer \(b>1\), a set \(D\subseteq V\) is called a b-disjunctive dominating set of the graph \(G=(V,E)\) if for every vertex \(v\in V{\setminus }D\), v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by \(\gamma _{b}^{d}(G)\). Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, \(\gamma _{b}^{d}(G)\) is equal to \(\gamma (G)\), the domination number of G for \(b \ge 3\) and observe that \(\gamma _{b}^{d}(G)\) need not be equal to \(\gamma (G)\) for \(b=2\). We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for \(b=2\). Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a \((\ln ({\varDelta }^{2}+(b-1){\varDelta }+b)+1)\)-approximation algorithm for MbDDP, where \({\varDelta }\) is the maximum degree of input graph \(G=(V,E)\) and prove that MbDDP cannot be approximated within \((1-\epsilon ) \ln (|V|)\) for any \(\epsilon >0\) unless NP \(\subseteq \) DTIME\((|V|^{O(\log \log |V|)})\). Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree \(\max \{b,4\}\).     

An improved bound on 2-distance coloring plane graphs with girth 5

A vertex coloring is called \(2\)-distance if any two vertices at distance at most \(2\) from each other get different colors. The minimum number of colors in 2-distance colorings of \(G\) is its 2-distance chromatic number, denoted by \(\chi _2(G)\). Let \(G\) be a plane graph with girth at least \(5\). In this paper, we prove that \(\chi _2(G)\le \Delta +8\) for arbitrary \(\Delta (G)\), which partially improves some known results.     

On (s,t)-relaxed L(2,1)-labeling of graphs

We initiate the study of relaxed \(L(2,1)\)-labelings of graphs. Suppose \(G\) is a graph. Let \(u\) be a vertex of \(G\). A vertex \(v\) is called an \(i\)-neighbor of \(u\) if \(d_G(u,v)=i\). A \(1\)-neighbor of \(u\) is simply called a neighbor of \(u\). Let \(s\) and \(t\) be two nonnegative integers. Suppose \(f\) is an assignment of nonnegative integers to the vertices of \(G\). If the following three conditions are satisfied, then \(f\) is called an \((s,t)\)-relaxed \(L(2,1)\)-labeling of \(G\): (1) for any two adjacent vertices \(u\) and \(v\) of \(G, f(u)\not =f(v)\); (2) for any vertex \(u\) of \(G\), there are at most \(s\) neighbors of \(u\) receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex \(u\) of \(G\), the number of \(2\)-neighbors of \(u\) assigned the label \(f(u)\) is at most \(t\). The minimum span of \((s,t)\)-relaxed \(L(2,1)\)-labelings of \(G\) is called the \((s,t)\)-relaxed \(L(2,1)\)-labeling number of \(G\), denoted by \(\lambda ^{s,t}_{2,1}(G)\). It is clear that \(\lambda ^{0,0}_{2,1}(G)\) is the so called \(L(2,1)\)-labeling number of \(G\). \(\lambda ^{1,0}_{2,1}(G)\) is simply written as \(\widetilde{\lambda }(G)\). This paper discusses basic properties of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of graphs. For any two nonnegative integers \(s\) and \(t\), the exact values of \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of paths, cycles and complete graphs are determined. Tight upper and lower bounds for \((s,t)\)-relaxed \(L(2,1)\)-labeling numbers of complete multipartite graphs and trees are given. The upper bounds for \((s,1)\)-relaxed \(L(2,1)\)-labeling number of general graphs are also investigated. We introduce a new graph parameter called the breaking path covering number of a graph. A breaking path \(P\) is a vertex sequence \(v_1,v_2,\ldots ,v_k\) in which each \(v_i\) is adjacent to at least one vertex of \(v_{i-1}\) and \(v_{i+1}\) for \(i=2,3,\ldots ,k-1\). A breaking path covering of \(G\) is a set of disjoint such vertex sequences that cover all vertices of \(G\). The breaking path covering number of \(G\), denoted by \(bpc(G)\), is the minimum number of breaking paths in a breaking path covering of \(G\). In this paper, it is proved that \(\widetilde{\lambda }(G)= n+bpc(G^{c})-2\) if \(bpc(G^{c})\ge 2\) and \(\widetilde{\lambda }(G)\le n-1\) if and only if \(bpc(G^{c})=1\). The breaking path covering number of a graph is proved to be computable in polynomial time. Thus, if a graph \(G\) is of diameter two, then \(\widetilde{\lambda }(G)\) can be determined in polynomial time. Several conjectures and problems on relaxed \(L(2,1)\)-labelings are also proposed.     

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles

Let \(G=(V,E)\) be a graph and \(\phi \) be a total \(k\)-coloring of \(G\) using the color set \(\{1,\ldots , k\}\). Let \(\sum _\phi (u)\) denote the sum of the color of the vertex \(u\) and the colors of all incident edges of \(u\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(\sum _\phi (u)\ne \sum _\phi (v)\). By \(\chi ^{''}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). Pil?niak and Wo?niak first introduced this coloring and conjectured that \(\chi _{nsd}^{''}(G)\le \Delta (G)+3\) for any simple graph \(G\). In this paper, we prove that the conjecture holds for planar graphs without intersecting triangles with \(\Delta (G)\ge 7\). Moreover, we also show that \(\chi _{nsd}^{''}(G)\le \Delta (G)+2\) for planar graphs without intersecting triangles with \(\Delta (G) \ge 9\). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.     

On Barnette’s conjecture and the $$H^{+-}$$ property

Let \(\mathcal{B}\) denote the class of all 3-connected cubic bipartite plane graphs. A conjecture of Barnette states that every graph in \(\mathcal{B}\) has a Hamilton cycle. A cyclic sequence of big faces is a cyclic sequence of different faces, each bounded by at least six edges, such that two faces from the sequence are adjacent if and only if they are consecutive in the sequence. Suppose that \({F_1, F_2, F_3}\) is a proper 3-coloring of the faces of \(G^*\in \mathcal{B}\). We prove that if every cyclic sequence of big faces of \(G^*\) has a face belonging to \(F_1\) and a face belonging to \(F_2\), then \(G^*\) has the following properties: \(H^{+-}\): If any two edges are chosen on the same face, then there is a Hamilton cycle through one and avoiding the other, \(H^{--}\): If any two edges are chosen which are an even distance apart on the same face, then there is a Hamilton cycle that avoids both. Moreover, let \(X\) and \(Y\) partition the set of big faces of \(G^*\) such that all such faces of \(F_1\) are in \(X\) and all such faces of \(F_2\) are in \(Y\). We prove that if every cyclic sequence of big faces has a face belonging to \(X\) and a face belonging to \(Y\), then \(G^*\) has a Hamilton cycle.