Packing Trees Into n-Chromatic Graphs
We show that if a sequence of trees T1, T2, ..., Tn−1 can be packed into Kn then they can be also packed into any n-chromatic graph.
Paired- and induced paired-domination in {E,net}-free graphs
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching...
Pan-factorial property in regular graphs.
Partition problems and kernels of graphs
Partitioning 3-colored complete graphs into three monochromatic cycles.
Partitioning 3-edge-colored complete equi-bipartite graphs by monochromatic trees under a color degree condition.
Partitions and edge colourings of multigraphs.
Partitions of a graph into cycles containing a specified linear forest
In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.
Partitions of networks that are robust to vertex permutation dynamics
Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex...
Partitions of some planar graphs into two linear forests
A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...
Path and cycle factors of cubic bipartite graphs
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...
Path systems in acyclic directed graphs
Perfect codes in Cartesian products of 2-paths and infinite paths.
Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles.
Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction...
Perfect matching preservers.
Perfect matchings and -decomposability of increasing trees.
Perfect matchings for the three-term Gale-Robinson sequences.
Perfect Matchings in a Class of Bipartite Graphs