In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.
We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.
Motivated by the work of Chmutov, Duzhin and Lando on Vassiliev invariants, we define a polynomial on weighted graphs which contains as specialisations the weighted chromatic invariants but also contains many other classical invariants including the Tutte and matching polynomials. It also gives the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We study its complexity and prove hardness results for very restricted classes of graphs.
A mixed hypergraph is a triple 𝓗 = (X,𝓒,𝓓) where X is the vertex set and each of 𝓒, 𝓓 is a family of subsets of X, the 𝓒-edges and 𝓓-edges, respectively. A k-coloring of 𝓗 is a mapping c: X → [k] such that each 𝓒-edge has two vertices with the same color and each 𝓓-edge has two vertices with distinct colors. 𝓗 = (X,𝓒,𝓓) is called a mixed hypertree if there exists a tree T = (X,𝓔) such that every 𝓓-edge and every 𝓒-edge induces a subtree of T. A mixed hypergraph 𝓗 is called uniquely...
The achromatic number of a graph is the maximum number of colours in a proper vertex colouring of such that for any two distinct colours there is an edge of incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of and for all .
A proper vertex coloring of a graph is acyclic if there is no bicolored cycle in . In other words, each cycle of must be colored with at least three colors. Given a list assignment , if there exists an acyclic coloring of such that for all , then we say that is acyclically -colorable. If is acyclically -colorable for any list assignment with for all , then is acyclically -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without 4-cycles...
A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...
For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that and is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring. If ⊆ R,...
In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu, and J. Wang,...