All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 27 Next

Displaying 521 – 540 of 719

Showing per page

Optimal Backbone Coloring of Split Graphs with Matching Backbones

Krzysztof Turowski (2015)

Discussiones Mathematicae Graph Theory

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.

Optimal edge ranking of complete bipartite graphs in polynomial time

Ruo-Wei Hung (2006)

Discussiones Mathematicae Graph Theory

An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees...

Orientations and 3 -colourings of graphs

Vincent Chouinard-Prévost, Alexandre Côté, Claude Tardif (2004)

Commentationes Mathematicae Universitatis Carolinae

We provide the list of all paths with at most 16 arcs with the property that if a graph G admits an orientation G → such that one of the paths in our list admits no homomorphism to G → , then G is 3 -colourable.

Oriented colouring of some graph products

N.R. Aravind, N. Narayanan, C.R. Subramanian (2011)

Discussiones Mathematicae Graph Theory

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.

Orthogonal vector coloring.

Haynes, Gerald, Park, Catherine, Schaeffer, Amanda, Webster, Jordan, Mitchell, Lon H. (2010)

The Electronic Journal of Combinatorics [electronic only]

Packing Trees Into n-Chromatic Graphs

András Gyárfás (2014)

Discussiones Mathematicae Graph Theory

We show that if a sequence of trees T1, T2, ..., Tn−1 can be packed into Kn then they can be also packed into any n-chromatic graph.

Parity vertex colorings of binomial trees

Petr Gregor, Riste Škrekovski (2012)

Discussiones Mathematicae Graph Theory

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

Parity vertex colouring of graphs

Piotr Borowiecki, Kristína Budajová, Stanislav Jendrol', Stanislav Krajci (2011)

Discussiones Mathematicae Graph Theory

A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...

Partial covers of graphs

Jirí Fiala, Jan Kratochvíl (2002)

Discussiones Mathematicae Graph Theory

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...

Partitioning a planar graph without chordal 5-cycles into two forests

Yang Wang, Weifan Wang, Jiangxu Kong, Yiqiao Wang (2024)

Czechoslovak Mathematical Journal

It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without chordal 5-cycles can be partitioned into two forests. This extends a result obtained by Raspaud and Wang in 2008.

Partitions of k -branching trees and the reaping number of Boolean algebras

Claude Laflamme (1993)

Commentationes Mathematicae Universitatis Carolinae

The reaping number 𝔯 m , n ( 𝔹 ) of a Boolean algebra 𝔹 is defined as the minimum size of a subset 𝒜 ⊆ 𝔹 ∖ { 𝐎 } such that for each m -partition 𝒫 of unity, some member of 𝒜 meets less than n elements of 𝒫 . We show that for each 𝔹 , 𝔯 m , n ( 𝔹 ) = 𝔯 ⌈ m n - 1 ⌉ , 2 ( 𝔹 ) as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every k -branching tree whose maximal nodes are coloured with ℓ colours contains an m -branching subtree using at most n colours if and only if ⌈ ℓ n ⌉ < ⌈ k m - 1 ⌉ .

Currently displaying 521 – 540 of 719