For a graph G=(V,E), a total ordering L on V, and a vertex v∈V, let Wcol2G,L,v be the set of vertices w∈V for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is ...w. The weak 2-coloring number wcol2(G) of G is the least k such that there is a total ordering L on V with |Wcol2G,L,v|≤k for all vertices v∈V. We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved.
The Star Dichromatic Number Hochstättler, Winfried; Steiner, Raphael
Discussiones Mathematicae. Graph Theory,
02/2022, Letnik:
42, Številka:
1
Journal Article
Recenzirano
Odprti dostop
We introduce a new notion of circular colourings for digraphs. The idea of this quantity, called
(
) of a digraph
, is to allow a finer subdivision of digraphs with the same dichromatic number into ...such which are “easier” or “harder” to colour by allowing fractional values. This is related to a coherent notion for the vertex arboricity of graphs introduced in G. Wang, S. Zhou, G. Liu and J. Wu,
, J. Discrete Appl. Math. 159 (2011) 1231–1238 and resembles the concept of the
of graphs introduced by Vince in 15 in the framework of digraph colouring. After presenting basic properties of the new quantity, including range, simple classes of digraphs, general inequalities and its relation to integer counterparts as well as other concepts of fractional colouring, we compare our notion with the notion of circular colourings for digraphs introduced in D. Bokal, G. Fijavz, M. Juvan, P.M. Kayll and B. Mohar,
, J. Graph Theory 46 (2004) 227–224 and point out similarities as well as differences in certain situations. As it turns out, the star dichromatic number shares all positive characteristics with the circular dichromatic number of Bokal
, but has the advantage that it depends on the strong components of the digraph only, while the addition of a dominating source raises the circular dichromatic number to the ceiling. We conclude with a discussion of the case of planar digraphs and point out some open problems.
Star coloring of cubic graphs Xie, Dezheng; Xiao, Huanhuan; Zhao, Zhihong
Information processing letters,
12/2014, Letnik:
114, Številka:
12
Journal Article
Recenzirano
A star coloring of a graph G is a proper vertex coloring of G such that any path of length 3 in G is not bicolored. The star chromatic number of a graph G, denoted by χs(G), is the smallest integer k ...for which G admits a star coloring with k colors. In this paper, we show that if G is a cubic graph, then χs(G)≥4 and the lower bound is optimal.
•We study star coloring of cubic graphs.•We prove that the star chromatic of a cubic graph is at least 4.•We show that the lower bound is optimal.
In this paper, we investigate the b -chromatic number of central graph, middle graph and total graph of star graph, denoted by C ( K 1 ,n ) , M ( K 1 ,n ) and T ( K 1 ,n ) respectively. We discuss ...the relationship between b -chromatic number with some other types of chromatic numbers such as chromatic number, star chromatic number and equitable chromatic number.
Let k and d be positive integers with k ≥ 2d. Let Zk = {0, 1, 2, ..., k - 1} be the set of integers modulo k. Let D
k
(x, y) = min{|x - y|, k - | x - y |} for x, y ∈ Z
k
. A pseudo complete ...d-coloring of G using k colors is a mapping ϕ : V(G) → Z
k
such that for any two elements i, j ∈ Z
k
with D
k
(i, j) ≥ d, there exist adjacent vertices u, v such that ϕ (u) = i and ϕ (v) = j. The maximum value of k for which G is k-pseudo complete d-colorable is called the pseudo d-achromatic number of G and is denoted by
. A graph G is called k-edge d-critical if
and
for all e ∈ E(G). In this paper we present several basic results on the degrees and degree sequence of k-edge d-critical graphs.
Let H be a fixed graph. We show that any H-minor free graph G of high enough girth has circular chromatic number arbitrarily close to two. Equivalently, each such graph G admits a homomorphism to a ...large odd circuit. In particular, graphs of high girth and of bounded genus, or of bounded tree width, are “nearly bipartite” in this sense. For example, any planar graph of girth at least 16 admits a homomorphism to a pentagon. We also obtain tight bounds on the girth of G in a few specific cases of small forbidden minors H.
Suppose
m,
k,
s are positive integers with
m>
sk. Let
D
m,
k,
s
denote the set {1,2,…,
m}⧹{
k,2
k,…,
sk}. The distance graph
G(
Z,
D
m,
k,
s
) has as vertex set all integers
Z and edges connecting
i ...and
j whenever |
i−
j|∈
D
m,
k,
s
. This paper determines the circular chromatic number of all the distance graphs
G(
Z,
D
m,
k,
s
).
PDF
