Displaying similar documents to “Vertex-disjoint copies of K¯₄”

Detour chromatic numbers

Marietjie Frick, Frank Bullock (2001)

Discussiones Mathematicae Graph Theory

Similarity:

The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.

An Oriented Version of the 1-2-3 Conjecture

Olivier Baudon, Julien Bensmail, Éric Sopena (2015)

Discussiones Mathematicae Graph Theory

Similarity:

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct...

Effect of edge-subdivision on vertex-domination in a graph

Amitava Bhattacharya, Gurusamy Rengasamy Vijayakumar (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any...

The bondage number of graphs: good and bad vertices

Vladimir Samodivkin (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph...

Highly connected counterexamples to a conjecture on α-domination

Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.