By h(G,x) and P(G,λ) we denote the adjoint polynomial and the chromatic polynomial of graph G, respectively. A new invariant of graph G, which is the fourth character R₄(G), is given in this paper. Using the properties of the adjoint polynomials, the adjoint equivalence class of graph $B_{n-6,1,2}$ is determined, which can be regarded as the continuance of the paper written by Wang et al. [J. Wang, R. Liu, C. Ye and Q. Huang, A complete solution to the chromatic equivalence class of graph $\overline{B_{n-7,1,3}}$, Discrete Math....

We prove a converse of the well-known Kelly’s Lemma. This motivates the introduction of the general notions of $𝒦$-table, $𝒦$-congruence and control-class.

A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each...

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

Suppose that G is a simple, vertex-labeled graph and that S is a multiset. Then if there exists a one-to-one mapping between the elements of S and the vertices of G, such that edges in G exist if and only if the absolute difference of the corresponding vertex labels exist in S, then G is an autograph, and S is a signature for G. While it is known that many common families of graphs are autographs, and that infinitely many graphs are not autographs, a non-autograph has never been exhibited. In this...

We investigate the connections between Ramsey properties of Fraïssé classes and the universal minimal flow $M(G_{)}$ of the automorphism group $G$ of their Fraïssé limits. As an extension of a result of Kechris, Pestov and Todorcevic (2005) we show that if the class has finite Ramsey degree for embeddings, then this degree equals the size of $M(G_{)}$. We give a partial answer to a question of Angel, Kechris and Lyons (2014) showing that if is a relational Ramsey class and $G$ is amenable, then $M(G_{)}$ admits a unique invariant...