Ewa Łazuka (1995)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we obtain the explicit formulas for chromatic polynomials of cacti. From the results relating to cacti we deduce the analogous formulas for the chromatic polynomials of n-gon-trees. Besides, we characterize unicyclic graphs by their chromatic polynomials. We also show that the so-called clique-forest-like graphs are chromatically equivalent.
Morgan, Kerri, Farr, Graham (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Ioan Tomescu (1989)
Banach Center Publications
Similarity:
Krzysztof Turowski (2015)
Discussiones Mathematicae Graph Theory
Similarity:
For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
Csilla Bujtás, Zsolt Tuza (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM...
Bergeron, Nantel, Billey, Sara (1993)
Experimental Mathematics
Similarity:
Abdulgani Sahin (2017)
Topological Algebra and its Applications
Similarity:
The Tutte polynomials for signed graphs were introduced by Kauffman. In 2012, Fath-Tabar, Gholam-Rezaeı and Ashrafı presented a formula for computing Tutte polynomial of a benzenoid chain. From this point on, we have also calculated the Tutte polynomials of signed graphs of benzenoid chains in this study.
Simon Špacapan, Aleksandra Tepeh Horvat (2008)
Discussiones Mathematicae Graph Theory
Similarity:
A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised. ...
Julian A. Allagan, David Slutzky (2014)
Discussiones Mathematicae Graph Theory
Similarity:
We color the vertices of each of the edges of a C-hypergraph (or cohypergraph) in such a way that at least two vertices receive the same color and in every proper coloring of a B-hypergraph (or bihypergraph), we forbid the cases when the vertices of any of its edges are colored with the same color (monochromatic) or when they are all colored with distinct colors (rainbow). In this paper, we determined explicit formulae for the chromatic polynomials of C-hypercycles and B-hypercycles ...
Farrell, E.J. (1981)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Ewa Kubicka, Grzegorz Kubicki, Kathleen A. McKeon (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices...
Schauz, Uwe (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Kostochka, Alexandr (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
P. Francis, S. Francis Raj (2016)
Discussiones Mathematicae Graph Theory
Similarity:
A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we obtain bounds for the b- chromatic number of induced subgraphs in terms of the b-chromatic number of the original graph. This turns out to be...
Li, Xueliang, Gutman, Ivan, Milovanović, V.Gradimir (2000)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity:
Wen-Yao Song, Lian-Ying Miao (2017)
Discussiones Mathematicae Graph Theory
Similarity:
A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by 𝜒's(G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4 Δ(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211]. In this paper, we show that...