Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a ...connected graph G, denoted rc(G), is the least k for which G admits a (not necessarily proper) k-edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define rc(G)=∞. A graph G is rainbow critical if the deletion of any edge of G increases rc(G). In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs.
The
k
-
weak-dynamic number
of a graph
G
is the smallest number of colors we need to color the vertices of
G
in such a way that each vertex
v
of degree
d
(
v
) sees at least min
{
k
,
d
(
v
)
}
...colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
This is the first book to comprehensively cover chromatic polynomials of graphs. It includes most of the known results and unsolved problems in the area of chromatic polynomials. Dividing the book ...into three main parts, the authors take readers from the rudiments of chromatic polynomials to more complex topics: the chromatic equivalence classes of graphs and the zeros and inequalities of chromatic polynomials. The early material is well suited to a graduate level course while the latter parts will be an invaluable resource for postgraduate students and researchers in combinatorics and graph theory.
Graph coloring is an assignment of labels called colors to elements of a graph. The packing coloring was introduced by Goddard et al. 1 in 2008 which is a kind of coloring of a graph. This problem is ...NP-complete for general graphs. In this paper, we consider some transformation graphs and generalized their packing chromatic numbers.
nema
Graphs with coloring redundant edges Demoen, Bart; Nguyen, Phuong-Lan
Electronic journal of graph theory and applications,
01/2016, Letnik:
1, Številka:
2
Journal Article
Recenzirano
Odprti dostop
A graph edge is $d$-coloring redundant if the removal of the edge does
not change the set of $d$-colorings of the graph. Graphs that are too
sparse or too dense do not have coloring redundant edges. ...Tight upper
and lower bounds on the number of edges in a graph in order for the
graph to have a coloring redundant edge are proven. Two constructions
link the class of graphs with a coloring redundant edge to the
$K_4$-free graphs and to the uniquely colorable graphs. The structure
of graphs with a coloring redundant edge is explored.
Abstract A vertex v of a given graph G is said to be in a rainbow neighbourhood of G, with respect to a proper coloring C of G, if the closed neighbourhood Nv of the vertex v consists of at least one ...vertex from every color class of G with respect to C. A maximal proper coloring of a graph G is a J-coloring of G such that every vertex of G belongs to a rainbow neighbourhood of G. In this paper, we study certain parameters related to J-coloring of certain Mycielski-type graphs.
We prove new upper bounds on the Thue chromatic number of an arbitrary graph and on the facial Thue chromatic number of a plane graph in terms of its maximum degree.
PDF
