Let
G
be a graph and
k
a positive integer. A strong
k
-edge-coloring of
G
is a mapping
ϕ
:
E
(
G
)
→
{
1
,
2
,
⋯
,
k
}
such that for any two edges
e
and
e
′
that are either adjacent to each other or ...adjacent to a common edge,
ϕ
(
e
)
≠
ϕ
(
e
′
)
. The strong chromatic index of
G
, denoted as
χ
s
′
(
G
)
, is the minimum integer
k
such that
G
has a strong
k
-edge-coloring. Lv, Li and Zhang Graphs and Combinatorics 38 (3) (2022) 63 proved that if
G
is a claw-free subcubic graph other than the triangular prism then
χ
s
′
(
G
)
≤
8
. In addition, they asked if the upper bound 8 can be improved to 7. In this paper, we answer this question in the affirmative. Our proof implies a polynomial-time algorithm for finding strong 7-edge-colorings of such graphs. We also construct infinitely many claw-free subcubic graphs with their strong chromatic indices attaining the bound 7.
A 3-star is a complete bipartite graph
K
1
,
3
. A 3-star packing of a graph
G
is a collection of vertex-disjoint subgraphs of
G
in which each subgraph is a 3-star. The maximum 3-star packing problem ...is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2
-independent set
of a graph
G
is a subset
S
of
V
(
G
) such that for each pair of vertices
u
,
v
∈
S
, paths between
u
and
v
are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio
8
15
(Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph
G
covering at least
3
v
(
G
)
-
8
4
vertices, where
v
(
G
) denotes the number of vertices of
G
.
Let
P
4
denote the path on four vertices. A
P
4
-packing of a graph
G
is a collection of vertex-disjoint copies of
P
4
in
G
. The maximum
P
4
-packing problem is to find a
P
4
-packing of maximum ...cardinality in a graph. In this paper, we prove that every simple cubic graph
G
on
v
(
G
) vertices has a
P
4
-packing covering at least
2
v
(
G
)
3
vertices of
G
and that this lower bound is sharp. Our proof provides a quadratic-time algorithm for finding such a
P
4
-packing of a simple cubic graph.
Let
k
be a positive integer. For any two integers
i
and
j
in
{
0
,
1
,
…
,
k
-
1
}
, let
|
i
-
j
|
k
be the circular distance between
i
and
j
, which is defined as
min
{
|
i
-
j
|
,
k
-
|
i
-
j
|
}
. ...Suppose
f
is a mapping from
V
(
G
) to
{
0
,
1
,
…
,
k
-
1
}
. If, for any two adjacent vertices
u
and
v
in
V
(
G
),
|
f
(
u
)
-
f
(
v
)
|
k
≥
2
, then
f
is called a
k
2
-coloring of
G
. In this paper, we study the relaxation of
k
2
-coloring. If adjacent vertices receive different integers, and for each vertex
u
of
G
, the number of neighbors
v
of
u
with
|
f
(
u
)
-
f
(
v
)
|
k
=
1
is at most
t
, then
f
is called a
t
-relaxed 2-distant circular
k
-coloring, or simply a
(
k
2
,
t
)
∗
-coloring of
G
. If
G
has a
(
k
2
,
t
)
∗
-coloring, then
G
is called
(
k
2
,
t
)
∗
-colorable. We prove that, for any two fixed integers
k
and
t
with
k
≥
2
and
t
≥
1
, the problem of deciding whether a graph
G
is
(
k
2
,
t
)
∗
-colorable is NP-complete except the case
k
=
2
and the case
k
=
3
and
t
≤
3
, which are polynomially solvable. For any outerplanar graph
G
, it is easy to see that
G
is
(
6
2
,
0
)
∗
-colorable. We show that all outerplanar graphs are
(
5
2
,
4
)
∗
-colorable, and there is no fixed positive integer
t
such that all outerplanar graphs are
(
4
2
,
t
)
∗
-colorable.
Fashion Game on Planar Graphs Shen, Chenli; Lin, Wensong
Graphs and combinatorics,
06/2022, Volume:
38, Issue:
3
Journal Article
Peer reviewed
This paper studies an optimization problem of the fashion game on graphs on surfaces, especially on planar graphs. There are rebel players in a graph
G
. All players choose their actions from an ...identical set of the two symmetric actions, say
{
0
,
1
}
. An action profile of
G
is a mapping
π
:
V
(
G
)
→
{
0
,
1
}
. A rebel likes people having the different action with her and dislikes people having the same action. The utility
u
(
v
,
π
)
of a player
v
under the action profile
π
is the number of neighbors she likes minus the number of neighbors she dislikes. Let
ϕ
:
V
(
G
)
→
Z
be a function. The
ϕ
-satisfiability problem is to determine whether a graph has an action profile under which each player
v
has a utility at least
ϕ
(
v
)
. Let
t
be an integer. The
t
-satisfiability problem is the specialized
ϕ
-satisfiability problem when
ϕ
(
v
)
=
t
, for each
v
∈
V
(
G
)
. The utility of
G
, denoted by
u
(
G
), is defined to be the maximum
t
such that
G
is
t
-satisfiable. Let
η
:
V
(
G
)
→
N
be a function. A mapping
c
:
V
(
G
)
→
{
0
,
1
}
is called an
η
-defective
2
-coloring
of
G
if every
v
∈
V
(
G
)
has at most
η
(
v
)
neighbors that have the same color with it. For graphs embeddable in surfaces, upper bounds of their utilities are given. The graphs embeddable in the torus or the Klein bottle whose utilities reach their upper bounds are determined. The
t
-satisfiability problem for graphs embeddable in the plane, the projective plane, the torus, or the Klein bottle is NP-complete if
t
∈
{
1
,
2
,
3
}
, and is polynomial time solvable otherwise. We design a dynamic programming algorithm that solves the
ϕ
-satisfiability problem for outerplanar graphs in
O
(
|
V
(
G
)
|
3
)
time. This algorithm can also solve the
η
-defective 2-coloring problem for outerplanar graphs.
Erdős–Faber–Lovász conjecture states that if a graph G is a union of the n edge-disjoint copies of complete graph Kn, that is, each pair of complete graphs has at most one shared vertex, then the ...chromatic number of graph G is n. In fact, we only need to consider the graphs where each pair of complete graphs has exactly one shared vertex. However, each shared vertex may be shared by more than two complete graphs. Therefore, this paper first considers the graphs where each shared vertex happens to be shared by two complete graphs, and then discusses the graphs with only one shared vertex shared by more than two complete graphs. The conjecture is correct for these two kinds of graphs in this work. Finally, the graph where each shared vertex happens to be shared by three complete graphs has been studied, and the conjecture also holds for such graphs when n=13. The graphs discussed in this paper have certain symmetric properties. The symmetry of graphs plays an important role in coloring. This work is an attempt to combine the symmetry of graphs with the coloring of graphs.
Let
P
3
denote the path on three vertices. A
P
3
-packing of a given graph
G
is a collection of vertex-disjoint subgraphs of
G
in which each subgraph is isomorphic to
P
3
. The maximum
P
3
-packing ...problem is to find a
P
3
-packing of a given graph
G
which contains the maximum number of vertices of
G
. The perfect
P
3
-packing problem is to decide whether a graph
G
has a
P
3
-packing that covers all vertices of
G
. Kelmans (Discrete Appl Math 159:112–127, 2011) proposed the following problem: Is the
P
3
-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the problem by proving that the perfect
P
3
-packing problem in claw-free cubic planar graphs is NP-complete. In addition, we show that for any connected claw-free cubic graph (resp. (2, 3)-regular graph, subcubic graph)
G
with
v
(
G
)
≥
14
(resp.
v
(
G
)
≥
8
,
v
(
G
)
≥
3
), the maximum
P
3
-packing of
G
covers at least
⌈
9
v
(
G
)
-
6
10
⌉
(resp.
⌈
6
v
(
G
)
-
6
7
⌉
,
⌈
3
v
(
G
)
-
6
4
⌉
) vertices, where
v
(
G
) denotes the order of
G
, and the bound is sharp. The proofs imply polynomial-time algorithms.
Let G be a simple graph. Suppose f is a mapping from V(G) to nonnegative integers. If, for any two adjacent vertices u and v of G, |f(u)−f(v)|≥2, then f is called a 2-distant coloring of G. In this ...paper, we introduce a relaxation of 2-distant coloring of a graph. Let t be a nonnegative integer. Suppose f is a mapping from V(G) to nonnegative integers. If adjacent vertices receive different integers and for each vertex u of G, the number of neighbors v of u with |f(v)−f(u)|=1 is at most t, then f is called a t-relaxed 2-distant coloring of G. If t=0 then f is just a 2-distant coloring of G. The span of f, denote by sp(f), is the difference between the maximum and minimum integers used by f. The minimum span of a t-relaxed 2-distant coloring of G, is called t-relaxed 2-distant coloring span of G, denoted by sp2t(G). Suppose G is a graph. Let γ:V(G)→Z+ be a function defined on V(G). A γ-relaxed 2-distant coloring of G with span k is a mapping f from V(G) to {0,1,…,k} such that f(u)≠f(v) for any two adjacent vertices u and v and each vertex u of G has at most γ(u) neighbors v with |f(v)−f(u)|=1.
In this paper, we prove that, for any two positive integers t and k with k≥2, deciding if sp2t(G)≤k for a graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. Let t be any nonnegative integer. It is easy to see that sp2t(G)≤6 for any planar graph G and sp2t(G)≤4 for any outerplanar graph G. We prove that, for any two positive integers t and k with k∈{2,3,4,5}, deciding if sp2t(G)≤k for a planar graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. We present examples to illustrate that there is no constant integer t such that every planar graph has a t-relaxed 2-distant coloring of span 5 and there is no constant integer t such that every outerplanar graph has a t-relaxed 2-distant coloring of span 3. We introduce pseudo ear decomposition and simple pseudo ear decomposition of a graph and show that a graph is outerplanar if and only if it admits a simple pseudo ear decomposition. Using this result, we show that each outerplanar graph has a γ-relaxed 2-distant coloring with span 3, where γ(v)=⌈d(v)2⌉ for each vertex v of G and the function γ is sharp in some sense, and that every triangle-free outerplanar graph has a 1-relaxed 2-distant coloring with span 3.
The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph
...G and any integer
p
⩾
0
, one can transform
G into a new graph
μ
p
(
G
)
, the
p-Mycielskian of
G. In this paper, we study the
kth chromatic numbers
χ
k
of Mycielskians and generalized Mycielskians of graphs. We show that
χ
k
(
G
)
+
1
⩽
χ
k
(
μ
(
G
)
)
⩽
χ
k
(
G
)
+
k
, where both upper and lower bounds are attainable. We then investigate the
kth chromatic number of Mycielskians of cycles and determine the
kth chromatic number of
p-Mycielskian of a complete graph
K
n
for any integers
k
⩾
1
,
p
⩾
0
and
n
⩾
2
. Finally, we prove that if a graph
G is
a
/
b
-colorable then the
p-Mycielskian of
G,
μ
p
(
G
)
, is
(
at
+
b
p
+
1
)
/
bt
-colorable, where
t
=
∑
i
=
0
p
(
a
-
b
)
i
b
p
-
i
. And thus obtain graphs
G with
m
(
G
)
grows exponentially with the order of
G, where
m
(
G
)
is the minimal denominator of a
a
/
b
-coloring of
G with
χ
f
(
G
)
=
a
/
b
.
Let
t
be a nonnegative integer and
G
= (
V
(
G
),
E
(
G
)) be a graph. For
v
∈
V
(
G
), let
N
G
(
v
) = {
u
∈
V
(
G
) \ {
v
} :
uv
∈
E
(
G
)}. And for
S
⊆
V
(
G
), we define
d
S
(
G
;
v
) = |
N
G
(v) ...∩
S
| for
v
∈
S
and
d
S
(
G
;
v
) = −1 for
v
∈
V
(
G
) \
S
. A subset
S
⊆
V
(
G
) is called a
t
-sparse set of
G
if the maximum degree of the induced subgraph
G
S
does not exceed
t
. In particular, a 0-sparse set is precisely an independent set. A vector-weighted graph $ (G,\vec{w},t)$ is a graph
G
with a vector weight function $ \vec{w}:V(G)\to {\mathbb{R}}^{t+2}$, where $ \vec{w}(v)=(w(v;-1),w(v;0),\dots,w(v;t))$ for each
v
∈
V
(
G
). The weight of a
t
-sparse set
S
in $ (G,\vec{w},t)$ is defined as $ \vec{w}(S,G)={\sum }_v w(v;{d}_S(G;v))$. And a
t
-sparse set
S
is a maximum weight
t
-sparse set of $ (G,\vec{w},t)$ if there is no
t
-sparse set of larger weight in $ (G,\vec{w},t)$. In this paper, we propose the maximum weight
t
-sparse set problem on vector-weighted graphs, which is to find a maximum weight
t
-sparse set of $ (G,\vec{w},t)$. We design a dynamic programming algorithm to find a maximum weight
t
-sparse set of an outerplane graph $ (G,\vec{w},t)$ which takes
O
((
t
+ 2)
4
n
) time, where
n
= |
V
(
G
)|. Moreover, we give a polynomial-time algorithm for this problem on graphs with bounded treewidth.
PDF
