-colorings and -bipartite graphs.
Packing independent sets and transversals
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.
Parity vertex colorings of binomial trees
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
Parity vertex colouring of graphs
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...
Partial covers of graphs
Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...
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 Graphs into Coverings and Hypergraphs into Transversals
Partitions of -branching trees and the reaping number of Boolean algebras
The reaping number of a Boolean algebra is defined as the minimum size of a subset such that for each -partition of unity, some member of meets less than elements of . We show that for each , as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every -branching tree whose maximal nodes are coloured with colours contains an -branching subtree using at most colours if and only if .
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 partitions of planar graphs.
Pattern hypergraphs.
Perfect 2-colorings of a hypercube.
Perfect colorings of the 12-cube that attain the bound on correlation immunity.
Planar graphs without 4-, 5- and 8-cycles are 3-colorable
In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.
Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable.
Point partition numbers and generalized Nordhaus-Gaddum problems
Point-distinguishing chromatic index of the union of paths
Let be a simple graph. For a general edge coloring of a graph (i.e., not necessarily a proper edge coloring) and a vertex of , denote by the set (not a multiset) of colors used to color the edges incident to . For a general edge coloring of a graph , if for any two different vertices and of , then we say that is a point-distinguishing general edge coloring of . The minimum number of colors required for a point-distinguishing general edge coloring of , denoted by , is called...