A coloring (partition) of the collection
(
X
h
) of all
h‐subsets of a set
X is
r‐regular if the number of times each element of
X appears in each color class (all sets of the same color) is the same ...number
r. We are interested in finding the conditions under which a given
r‐regular coloring of
(
X
h
) is extendible to an
s‐regular coloring of
(
Y
h
) for
s
⩾
r and
Y
⊋
X. The case
h
=
2
,
r
=
s
=
1 was solved by Cruse, and due to its connection to completing partial symmetric latin squares, many related problems are extensively studied in the literature, but very little is known for
h
⩾
3. The case
r
=
s
=
1 was solved by Häggkvist and Hellgren, settling a conjecture of Brouwer and Baranyai. The cases
h
=
2 and
h
=
3 were solved by Rodger and Wantland, and Bahmanian and Newman, respectively. In this paper, we completely settle the cases
h
=
4
,
|
Y
|
⩾
4
|
X
| and
h
=
5
,
|
Y
|
⩾
5
|
X
|.
The adjacent vertex-distinguishing edge-coloring of a graph $ G $ is a proper edge-coloring of $ G $ such that each pair of adjacent vetices receives a distinct set of colors. The minimum number of ...colors required in an adjacent vertex-distinguishing edge-coloring of $ G $ is called the adjacent vertex-distinguishing chromatic index. In this paper, we determine the adjacent vertex distinguishing chromatic indices of cubic Halin graphs whose characteristic trees are caterpillars.
An acyclic edge coloring of a graph
G
is a proper edge coloring such that there are no bichromatic cycles in
G
. The acyclic chromatic index
X
α
′
(
G
)
of
G
is the smallest
k
such that
G
has an ...acyclic edge coloring using
k
colors. It was conjectured that every simple graph
G
with maximum degree Δ has
X
α
′
(
G
)
≤
Δ
+
2
. A 1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we show that every 1-planar graph
G
without 4-cycles has
X
α
′
(
G
)
≤
Δ
+
22
.
The strong chromatic index of a graph G, denoted by χs′(G), is the least number of colors needed to edge-color G properly so that every path of length 3 uses three different colors. In this paper, we ...prove that if G is a graph with Δ(G)=4 and maximum average degree less than 6118 (resp.72, 185, 154, 5113), then χs′(G)≤16 (resp.17, 18, 19, 20), which improves the results of Bensmail et al. (2015).
Given an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such ...distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3.
A path in an edge-colored graph G is called monochromatic if any two edges on the path have the same color. For k≥2, an edge-colored graph G is said to be monochromatic k-edge-connected if every two ...distinct vertices of G are connected by at least k edge-disjoint monochromatic paths, and G is said to be uniformly monochromatic k-edge-connected if every two distinct vertices are connected by at least k edge-disjoint monochromatic paths such that all edges of these k paths are colored with a same color. We use mck(G) and umck(G) to denote the maximum number of colors that ensures G to be monochromatic k-edge-connected and, respectively, G to be uniformly monochromatic k-edge-connected. In this paper, we first conjecture that for any k-edge-connected graph G, mck(G)=e(G)−e(H)+⌊k2⌋, where H is a minimum k-edge-connected spanning subgraph of G. We verify the conjecture for k=2. We also prove the conjecture for G=Kk+1 and G=Kk,n with n≥k≥3. When G is a minimal k-edge-connected graph, we give an upper bound of mck(G), i.e., mck(G)≤k−1. For the uniformly monochromatic k-edge-connectivity, we prove that for all k, umck(G)=e(G)−e(H)+1, where H is a minimum k-edge-connected spanning subgraph of G.
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.
PDF
