Title of article
Contractible edges in a k-connected graph (K1 + P4)-free graph
Author/Authors
Ando، نويسنده , , Kiyoshi، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2000
Pages
4
From page
7
To page
10
Abstract
We define a notion of simple k-coloring of an oriented graph G→ as an assignement c of colors from the set {1, 2,…, k} to the vertices of G→ in such a way that at least two colors are used and the following property is satisfied: if (x,y), (xʹ, yʹ) are two edges of G→ and c(x) = c(yʹ), then c(y) ≠ c(xʹ) or c(x) = c(y). For the graph with only one vertex, we define its simple 1-coloring as the assignement of the color 1 to this vertex. We define the simple chromatic number of G→ as the minimum k such that there is a simple k-coloring of G→ʹ, for any subgraph G→ʹ of G→. We show that this number is close to the oriented chromatic number of a graph for some families of graphs (bipartite graphs, graphs with bounded treewidth, graphs with bounded acyclic chromatic number, planar graphs).
Keywords
connectivity , contractible edge , graph , forbidden subgraph
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2000
Journal title
Electronic Notes in Discrete Mathematics
Record number
1452812
Link To Document