A proper edge-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v, the set of colors used on the edges incident with u and the set of colors used on the ...edges incident with v are not included in each other. The strict neighbor-distinguishing index χsnd′(G) of G is the minimum number of colors in a strict neighbor-distinguishing edge-coloring of G. A graph is formal if its minimum degree is at least 2. Let Hn denote the graph obtained from the complete bipartite graph K2,n by inserting a 2-vertex into one edge.
In this paper, we prove that if G is a formal K4-minor-free graph, then χsnd′(G)≤2Δ+1, and moreover χsnd′(G)=2Δ+1 if and only if G is HΔ. This shows partially a conjecture, which says that every formal graph G, different from HΔ, has χsnd′(G)≤2Δ.
The edge DP-chromatic number of G, denoted by χDP′(G), is the minimum k such that G is edge DP-k-colorable. In 1999, Juvan, Mohar, and Thomas proved that the edge list chromatic number of K4-minor ...free graph G with Δ≥3 is Δ. In this paper, we prove that if G is a K4-minor free graph, then χDP′(G)∈{Δ,Δ+1}, and equality χDP′(G)=Δ+1 holds for some K4-minor free graph G with Δ=3. Moreover, if G is a planar graph with Δ≥9 and with no intersecting triangles, then χDP′(G)=Δ.
It is well known that a graph is outerplanar if and only if it is K4-minor free and K2,3-minor free. Campos and Wakabayashi (2013) recently proved that γ(G)≤⌊n+k4⌋ for any maximal outerplanar graph G ...of order n≥3 with k vertices of degree 2, where γ(G) denotes the domination number of G. Tokunaga (2013) provided a short proof for the above theorem. Based on some structural properties of K2,3-minor free graphs and K4-minor free graphs, applying the idea of Tokunaga we extend the theorem of Campos and Wakabayashi to all maximal K4-minor free graphs and all maximal K2,3-minor free graphs. We also disprove two conjectures of Tokunaga on planar graphs.
A graph G is said to be 1-perfectly orientable if it has an orientation D such that for every vertex v∈V(G), the out-neighborhood of v in D is a clique in G. We characterize the class of 1-perfectly ...orientable K4-minor-free graphs. As a consequence we obtain a characterization of 1-perfectly orientable outerplanar graphs.
The surviving rate of an infected network Wang, Weifan; Finbow, Stephen; Wang, Ping
Theoretical computer science,
09/2010, Letnik:
411, Številka:
40
Journal Article
Recenzirano
Odprti dostop
Let
G
be a connected network. Let
k
≥
1
be an integer. Suppose that a vertex
v
of
G
becomes infected. A program is then installed on
k
-nodes not yet infected. Afterwards, the virus spreads to all ...its unprotected neighbors in each time interval. The virus and the network administrator take turns until the virus can no longer spread further. Let
s
n
k
(
v
)
denote the maximum number of vertices in
G
the network administrator can save when a virus infects
v
. The
k
-surviving rate
ρ
k
(
G
)
of
G
is defined to be the average value
∑
v
∈
V
(
G
)
s
n
k
(
v
)
/
n
2
. In particular, we write
ρ
(
G
)
=
ρ
1
(
G
)
.
In this paper, we first use a probabilistic method to show that almost all networks have
k
-surviving rate arbitrarily close to 0. Then, we prove the following results: (1)
ρ
(
G
)
≥
2
35
for a planar network
G
of girth at least 9; (2)
ρ
2
(
G
)
≥
1
16
for a series–parallel network
G
; and (3)
ρ
2
d
−
1
(
G
)
≥
2
5
d
for a
d
-degenerate network
G
.
A
k
-coloring of a graph
G
=(
V
,
E
) is a mapping
c
:
V
→{1,2,…,
k
}. The coloring
c
is injective if, for every vertex
v
∈
V
, all the neighbors of
v
are assigned with distinct colors. The injective ...chromatic number
χ
i
(
G
) of
G
is the smallest
k
such that
G
has an injective
k
-coloring. In this paper, we prove that every
K
4
-minor free graph
G
with maximum degree Δ≥1 has
. Moreover, some related results and open problems are given.
Let
G be a
K
4-minor free graph with maximum degree
Δ. We prove that the chromatic number of the square of
G is at most (i)
Δ+3 if 2⩽
Δ⩽3; or (ii) ⌊3
Δ/2⌋+1 if
Δ⩾4. Examples are given to show the ...bounds can be attained.
We prove that the incidence coloring number of every
k-degenerated graph
G is at most
Δ(
G)+2
k−1. For
K
4-minor free graphs (
k=2), we decrease this bound to
Δ(
G)+2, which is tight. For planar ...graphs (
k=5), we decrease this bound to
Δ(
G)+7.
Let G be a simple graph of order n whose adjacency eigenvalues are λ1≥⋯≥λn. The HL-index of G is defined to be R(G)=max{|λh|,|λl|} with h=n+12 and l=n+12. Mohar conjectured that R(G)≤1 for every ...planar subcubic graph G. In this note, we prove that Mohar’s Conjecture holds for every K4-minor-free subcubic graph. In addition, R(G)≤1 for every subcubic graph G which contains a subgraph K2,3.
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $\sigma= v_1,\dots,v_n$, the ..."First-Fit" greedy colouring algorithm colours the vertices in the order of $\sigma$ by assigning to each vertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, we obtain {\em connected greedy colourings}. For some graphs, all connected greedy colourings use exactly $\chi(G)$ colours; they are called {\em good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only $\chi(G)$ colours; they are called {\em ugly graphs}. We show that no perfect graph is ugly. We also give simple proofs of this fact for subclasses of perfect graphs (block graphs, comparability graphs), and show that no $K_4$-minor free graph is ugly. Moreover, our proofs are constructive, and imply the existence of polynomial-time algorithms to compute good connected orderings for these graph classes.
PDF
