Given two graphs H 1 and H 2 , a graph is ( H 1 , H 2 ) -free if it contains no induced subgraph isomorphic to H 1 or H 2 . A graph G is k -vertex-critical if every proper induced subgraph of G has chromatic number less than k , but G has chromatic number k . The study of k -vertex-critical graphs for specific graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there exists a polynomial-time certifying algorithm to decide the k -colorability of a graph in the class. In this paper, we show that: (1) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 1 , 4 + P 1 ) -free graphs; (2) for s ≥ 1 , there are finitely many 5-vertex-critical ( P 5 , K 1 , s + P 1 ) -free graphs; (3) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 3 + 2 P 1 ‾ ) -free graphs. Moreover, we characterize all 5-vertex-critical ( P 5 , H ) -free graphs where H ∈ { K 1 , 3 + P 1 , K 1 , 4 + P 1 , K 3 + 2 P 1 ‾ } using an exhaustive graph generation algorithm.

In biomedical networks, molecular associations are important to understand biological processes and functions. Many computational methods, such as link prediction methods based on graph neural networks (GNNs), have been successfully applied in discovering molecular relationships with biological significance. However, it remains a challenge to explore a method that relies on representation learning of links for accurately predicting molecular associations. In this paper, we present a novel GNN based on link representation (LR-GNN) to identify potential molecular associations. LR-GNN applies a graph convolutional network (GCN)-encoder to obtain node embedding. To represent associations between molecules, we design a propagation rule that captures the node embedding of each GCN-encoder layer to construct the LR. Furthermore, the LRs of all layers are fused in output by a designed layer-wise fusing rule, which enables LR-GNN to output more accurate results. Experiments on four biomedical network data, including lncRNA-disease association, miRNA-disease association, protein-protein interaction and drug-drug interaction, show that LR-GNN outperforms state-of-the-art methods and achieves robust performance. Case studies are also presented on two datasets to verify the ability to predict unknown associations. Finally, we validate the effectiveness of the LR by visualization.

MOTIVATION: With the development of single-cell RNA sequencing (scRNA-seq) techniques, increasingly more large-scale gene expression datasets become available. However, to analyze datasets produced by different experiments, batch effects among different datasets must be considered. Although several methods have been recently published to remove batch effects in scRNA-seq data, two problems remain to be challenging and not completely solved: (i) how to reduce the distribution differences of different batches more accurately; and (ii) how to align samples from different batches to recover the cell type clusters. RESULTS: We proposed a novel deep-learning approach, which is a hierarchical distribution-matching framework assisted with contrastive learning to address these two problems. Firstly, we design a hierarchical framework for distribution matching based on a deep autoencoder. This framework employs an adversarial training strategy to match the global distribution of different batches. This provides an improved foundation to further match the local distributions with a maximum mean discrepancy-based loss. For local matching, we divide cells in each batch into clusters and develop a contrastive learning mechanism to simultaneously align similar cluster pairs and keep noisy pairs apart from each other. This allows to obtain clusters with all cells of the same type (true positives), and avoid clusters with cells of different type (false positives). We demonstrate the effectiveness of our method on both simulated and real datasets. Results show that our new method significantly outperforms the state-of-the-art methods and has the ability to prevent overcorrection. AVAILABILITY AND IMPLEMENTATION: The python code to generate results and figures in this article is available at https://github.com/zhanglabNKU/HDMC, the data underlying this article is also available at this github repository. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

This work aims to document a two-sided impact of the COVID-19 pandemic on online question and answer communities. It implements empirical analyses on subsidiary communities affiliating to the Stack Exchange network. Using a difference-in-difference approach to identify the impact of the pandemic on community volume (the counts of questions and answers) and responsiveness (the likelihood of questions to be answered), this work has the following discoveries. First, the community volume grows, both in questions and answers, driven by a prolonged time of staying at home during the pandemic. Second, the community responsiveness declines, driven by an influx of new community members during the pandemic, which is also a result of the prolonged time of staying at home. Theoretical and practical implications are discussed.

For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f:V(G) -> V(H) such that for every edge uv in E(G) it holds that f(u)f(v)in E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of P_t-free graphs. We show that for every odd k >= 5 the C_k-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_9-free graphs. On the other hand, we prove that the extension version of C_k-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.

In this paper, we show that every $(2P_2,K_4)$-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [ J. Combin. Theory Ser. B, 29 (1980), pp. 345--346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for $(4P_1,C_4)$-free graphs. Lozin and Malyshev [ Discrete Appl. Math., 216 (2017), pp. 273--280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring $(4P_1,C_4)$-free graphs.

We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sanchez-Fernandez et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixed-parameter tractability results.

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs.

For a positive integer |$k$| and graph |$G=(V,E)$|⁠, a |$k$|-colouring of |$G$| is a mapping |$c: V\rightarrow \{1,2,\ldots ,k\}$| such that |$c(u)\neq c(v)$| whenever |$uv\in E$|⁠. The |$k$|-Colouring problem is to decide, for a given |$G$|⁠, whether a |$k$|-colouring of |$G$| exists. The |$k$|-Precolouring Extension problem is to decide, for a given |$G=(V,E)$|⁠, whether a colouring of a subset of |$V$| can be extended to a |$k$|-colouring of |$G$|⁠. A |$k$|-list assignment of a graph is an allocation of a list—a subset of |$\{1,\ldots ,k\}$|—to each vertex, and the List |$k$|-Colouring problem is to decide, for a given |$G$|⁠, whether |$G$| has a |$k$|-colouring in which each vertex is coloured with a colour from its list. We consider the computational complexity of these three decision problems when restricted to graphs that do not contain a cycle on |$s$| vertices or a path on |$t$| vertices as induced subgraphs (for fixed positive integers |$s$| and |$t$|⁠). We report on past work and prove a number of new NP-completeness results.

In this note, we give a counter example to show that the proof of a main result obtained by Haynes and Slater (Networks 32 (1998), 199–206, Theorem 12) is inaccurate. Here, we give a complete proof of the result. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 115–116 2011