Open AccessArticle

Strong Chromatic Index of Outerplanar Graphs

School of Mathematics and Information Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, China

School of Management, Beijing University of Chinese Medicine, Beijing 100029, China

Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China

Author to whom correspondence should be addressed.

^†

Research Supported Partially by NSFC (No. 12001156).

^‡

Research Supported Partially by NSFC (No. 12071048) and Science and Technology Commission of Shanghai Municipality (No. 18dz2271000).

^§

Research Supported Partially by NSFC (No. 12031018).

Axioms 2022, 11(4), 168; https://doi.org/10.3390/axioms11040168

Submission received: 4 February 2022 / Revised: 7 March 2022 / Accepted: 3 April 2022 / Published: 8 April 2022

(This article belongs to the Special Issue Graph Theory with Applications)

Download

Browse Figures

Review Reports Versions Notes

Abstract

The strong chromatic index

χ_{s}^{'} (G)

of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every outerplanar graph G with

Δ \geq 3

has

χ_{s}^{'} (G) \leq 3 Δ - 3

. In this paper, we give a characterization for an outerplanar graph G to have

χ_{s}^{'} (G) = 3 Δ - 3

. We also show that if G is a bipartite outerplanar graph, then

χ_{s}^{'} (G) \leq 2 Δ

; and

χ_{s}^{'} (G) = 2 Δ

if and only if G contains a particular subgraph.

Keywords:

strong edge-coloring; strong chromatic index; outerplanar graph; bipartite graph

MSC:

Graph Theory with Applications

1. Introduction

Only simple graphs are considered in this paper. For a graph G, we use

V (G)

E (G)

, and

Δ (G)

to denote its vertex set, edge set and maximum degree, respectively. A vertex v is called a k-vertex (or

k^{+}

-vertex) if the degree

d_{G} (v)

of v is k (or at least k). Let

N_{G} (v)

denote the set of vertices adjacent to v in G. If no ambiguity arises in the context,

Δ (G)

d_{G} (v)

, and

N_{G} (v)

are simply written as

Δ

d (v)

, and

N (v)

, respectively. A subgraph of G is called a clique if any two of its vertices are adjacent in G. A subset

I \subset V (G)

of a connected graph G is called a clique-cut if

G [I]

is a clique and

G - I

is disconnected.

A proper edge-k-coloring of a graph G is a mapping

ϕ : E (G) \to {1, 2, \dots, k}

such that

ϕ (e) \neq ϕ (e^{'})

for any two adjacent edges e and

e^{'}

. The chromatic index

χ^{'} (G)

of G is the smallest k such that G has a proper edge k-coloring. An edge coloring of the graph G is called strong if every color class induces a matching in G. The strong chromatic index of G, denoted

χ_{s}^{'} (G)

, is the smallest k such that G has a strong edge-k-coloring.

The strong edge-coloring of graphs was introduced by Fouquet and Jolivet [1]. In 1985, Erdos and Nešetřil raised the following conjecture and showed that the upper bounds are tight:

Conjecture 1.

For a graph G,

χ_{s}^{'} (G) \leq \{\begin{matrix} 1.25 Δ^{2}, & if Δ is even; \\ 1.25 Δ^{2} - 0.5 Δ + 0.25, & if Δ is odd . \end{matrix}

Using probabilistic method, Molloy and Reed [2] showed that

χ_{s}^{'} (G) \leq 1.998 Δ^{2}

when

Δ

is sufficiently large. This result was further improved in [3] to that

χ_{s}^{'} (G) \leq 1.93 Δ^{2}

for any graph G. Using Four-Colour Theorem and Vizing Theorem, Faudree et al. [4] showed that every planar graph G has

χ_{s}^{'} (G) \leq 4 Δ + 4

; and constructed a planar graph G such that

χ_{s}^{'} (G) = 4 Δ - 4

A planar graph is called outerplanar if it has a plane embedding such that all the vertices lie on the boundary of the unbounded face. It was shown in [5] that a graph G is outerplanar if and only if G is

K_{4}

-minor-free and

K_{2, 3}

-minor-free. Hence outerplanar graphs are special

K_{4}

-minor-free graphs. Wang et al. [6] showed that every

K_{4}

-minor-free graph G with

Δ \geq 3

has

χ_{s}^{'} (G) \leq 3 Δ - 2

and the upper bound is tight. Hocquard et al. [7] proved that every outerplanar graph G with

Δ \geq 3

has

χ_{s}^{'} (G) \leq 3 Δ - 3

and the upper bound is tight.

In this paper we will give a characterization for an outerplanar graph G with

Δ \geq 3

to have

χ_{s}^{'} (G) = 3 Δ - 3

2. Sun-Graphs

Suppose that G is an outerplanar graph. We embed G in the plane so that all the vertices occur in the boundary of unbounded face. Let

F (G)

denote the set of faces in G. The unbounded face, denoted by

f_{0} (G)

, of G is called outer face, and other faces inner faces. For a face

f \in F (G)

, the boundary of f is denoted by

b (f)

. A 3-face with

x, y, z

as boundary vertices is written as

[x y z]

. The edges lying in the outer face are called outer edges and other edges inner edges. An inner face f is called an end-face if

b (f)

contains at most one inner edge. A leaf of G is a vertex of degree 1, and a pendant edge is an edge incident to a leaf. For a vertex

v \in V (G)

, let

L (v)

denote the set of pendant edges at vertex v. For a cycle C, an edge

x y \in E (G) \ E (C)

is called a chord of C if

x, y \in V (C)

Let

F_{1}

denote a subgraph of G, which consists of a 3-cycle

C_{3} = x_{0} x_{1} x_{2} x_{0}

with

d_{G} (x_{i}) = Δ \geq 3

for

i = 0, 1, 2

Let

F_{2}

denote a subgraph of G, which consists of a 4-cycle

C_{4} = x_{0} x_{1} x_{2} x_{3} x_{0}

with

d_{G} (x_{0}) = d_{G} (x_{1}) = Δ \geq 3

Let

F_{3}

denote a subgraph of G, which consists of a 7-cycle

C_{7} = x_{0} x_{1} \dots x_{6} x_{0}

with

d_{G} (x_{i}) = 3

for

i = 0, 1, \dots, 6

We assume that

C_{4}

F_{2}

and

C_{7}

F_{3}

have no chord.

The configurations

F_{1}, F_{2}, F_{3}

are depicted in Figure 1. By the outerplanarity of G, for

F_{j}

j \in {1, 2, 3}

, some vertex

y_{i} \in N (x_{i}) \ {x_{i - 1}, x_{i + 1}}

may identify with some vertex

y_{i + 1} \in N (x_{i + 1}) \ {x_{i}, x_{i + 2}}

, but there is at most one such pair

{y_{i}, y_{i + 1}}

satisfying

y_{i} = y_{i + 1}

, where indices i are taken as modulo n.

Lemma 1

([7]). If G is an outerplanar graph with

Δ \geq 3

, then

χ_{s}^{'} (G) \leq 3 Δ - 3

Lemma 2.

Let

F_{1}, F_{2}, F_{3}

are defined as above. Then

(1): $χ_{s}^{'} (F_{1}) = 3 Δ - 3$ .
(2): $χ_{s}^{'} (F_{2}) = 3 Δ - 3$ .
(3): $χ_{s}^{'} (F_{3}) = 6$ .

Proof.

(1): Since $| E (F_{1}) | = 3 Δ - 3$ and it is easy to check that any two edges of $F_{1}$ have distance at most two, so it follows that $χ_{s}^{'} (F_{1}) = 3 Δ - 3$ .
(2): Applying the similar analysis as in (1), we can derive that $χ_{s}^{'} (F_{2}) = 3 Δ - 3$ .
(3): It is evident that $χ_{s}^{'} (F_{3}) \leq 6$ by Lemma 1. Conversely, assume that $F_{3}$ admits a strong edge-5-coloring $ϕ$ using the color set $C = {1, 2, \dots, 5}$ . Let $E_{i}$ denote the set of edges colored with the color i under the coloring $ϕ$ . Set $E^{*} = E (F_{3}) - E (C_{7})$ . First, it is easy to inspect that $| E_{i} | \leq 3$ for each $i \in C$ . Next, because $| E (F_{3}) | = 14$ and $| C | = 5$ , we can assume that $| E_{i} | = 3$ for $i = 1, 2, 3, 4$ and $| E_{5} | = 2$ . Since $| E^{*} | = 7$ , some $E_{i}$ for $i \in {1, 2, 3, 4}$ , say $i = 1$ , satisfies $| E_{1} \cap E^{*} | \leq 1$ . It implies that $| E_{1} \cap E (C_{7}) | \geq 2$ . On the other hand, it is easy to inspect that $| E_{1} \cap E (C_{7}) | \leq 2$ . So $| E_{1} \cap E (C_{7}) | = 2$ and $| E_{1} \cap E^{*} | = 1$ , however such coloring is impossible, a contradiction. This shows that $χ_{s}^{'} (F_{3}) \geq 6$ . Consequently, $χ_{s}^{'} (F_{3}) = 6$ .

□

Let

C_{n} = x_{0} x_{1} \dots x_{n - 1} x_{0}

be a cycle with

n \geq 3

. Let

k \geq 3

be an integer. At each vertex

x_{i}

, we glue

k - 2

leaves and write the resultant graph as

S_{n}^{k}

. Then

S_{n}^{k}

is an outerplanar graph with maximum degree k and order

n (k - 1)

. We call

S_{n}^{k}

a sun-graph with parameters n and k. If

k = 3

, then we use

y_{i}

to denote a leaf adjacent to

x_{i}

for

i = 0, 1, \dots, n - 1

As an easy observation, we have the following:

Lemma 3.

Let

C_{n}

be a cycle with

n \geq 3

. Then

χ_{s}^{'} (C_{n}) = \{\begin{matrix} 5, & if n = 5; \\ 3, & if n \equiv 0 (\mod 3); \\ 4, & otherwise . \end{matrix}

Lemma 4.

Let

S_{n}^{3}

be a sun-graph with

n \geq 3

. Then

χ_{s}^{'} (S_{n}^{3}) = \{\begin{matrix} 6, & if n = 3, 4, 7; \\ 5, & otherwise . \end{matrix}

Proof.

n = 3, 4, 7

, the conclusion follows immediately from Lemma 2. So suppose that

n \neq 3, 4, 7

. It holds trivially that

χ_{s}^{'} (S_{n}^{3}) \geq 5

since

S_{n}^{3}

contains two adjacent 3-vertices. To show that

χ_{s}^{'} (S_{n}^{3}) \leq 5

, we make use of induction on n. It remains to construct a strong edge-5-coloring

ϕ

S_{n}^{3}

using the color set

C = {1, 2, \dots, 5}

If $n = 5$ , then we color the edges in ${x_{i} y_{i}, x_{i + 2} x_{i + 3}}$ with $i + 1$ for $i = 0, 1, 2, 3, 4$ , where indices are taken as modulo 5.
If $n \equiv 0$ (mod 6), then we alternatively color the edges in $E (C_{n})$ with $1, 2, 3$ , and color alternatively pendant edges with $4, 5$ .
If $n = 8$ , then we color ${x_{1} y_{1}, x_{3} x_{4}, x_{6} x_{7}}$ with 1, ${x_{3} y_{3}, x_{0} x_{1}, x_{5} x_{6},}$ with 2, ${x_{5} y_{5}, x_{0} x_{7},}$ ${x_{2} x_{3}}$ with 3, ${x_{7} y_{7}, x_{1} x_{2}, x_{4} x_{5}}$ with 4, and ${x_{0} y_{0}, x_{2} y_{2}, x_{4} y_{4}, x_{6} y_{6}}$ with 5.
If $n = 9$ , then we color ${x_{1} y_{1}, x_{3} y_{3}, x_{8} y_{8}, x_{5} x_{6}}$ with 1, ${x_{0} y_{0}, x_{5} y_{5}, x_{7} y_{7}, x_{2} x_{3}}$ with 2, ${x_{2} y_{2}, x_{4} y_{4}, x_{6} y_{6}, x_{0} x_{8}}$ with 3, ${x_{0} x_{1}, x_{3} x_{4}, x_{6} x_{7}}$ with 4, and ${x_{1} x_{2}, x_{4} x_{5}, x_{7} x_{8}}$ with 5.

Now assume that

n \geq 10

and

n \neg \equiv 0

(mod 6). Consider the graph

S_{n - 5}^{3}

. Note that

n - 5 \geq 5

, and

n - 5 \neq 7

. By the induction hypothesis,

χ_{s}^{'} (S_{n - 5}^{3}) = 5

. Let

ϕ

be a strong edge-5-coloring of

S_{n - 5}^{3}

, so that

ϕ (x_{0} x_{1}) = 1

ϕ (x_{0} y_{0}) = 2

ϕ (x_{n - 7} x_{n - 6}) = 3

ϕ (x_{n - 6} y_{n - 6}) = 4

, and

ϕ (x_{0} x_{n - 6}) = 5

. Clearly,

S_{n}^{3}

can be obtained from

S_{n - 5}^{3}

by inserting five vertices

x_{n - 5}

x_{n - 4}

x_{n - 3}

x_{n - 2}

x_{n - 1}

to the edge

x_{0} x_{n - 6}

and adding a leaf

y_{j}

x_{j}

for

j = n - 5, n - 4, \dots, n - 1

. We extend

ϕ

S_{n}^{3}

by coloring

{x_{n - 3} x_{n - 2}

x_{n - 5} y_{n - 5}}

with 1,

{x_{n - 5} x_{n - 4}, x_{n - 2} y_{n - 2}}

with 2,

{x_{n - 2} x_{n - 1}, x_{n - 4} y_{n - 4}}

with 3,

{x_{n - 4} x_{n - 3}, x_{n - 1} y_{n - 1}}

with 4, and

{x_{0} x_{n - 1}, x_{n - 6} x_{n - 5}, x_{n - 3} y_{n - 3}}

with 5. It is easy to testify that the extended coloring is a strong edge-5-coloring of

S_{n}^{3}

. □

For a sun-graph

S_{n}^{k}

with

C_{n} = x_{0} x_{1} \dots x_{n - 1} x_{0}

, we set

L (x_{i}) = {e_{i}^{1}, e_{i}^{2}, \dots, e_{i}^{k - 2}}

for

i = 0, 1, \dots, n - 1

. Recall that

L (x_{i})

stands for the set of pendant edges incident to

x_{i}

Lemma 5.

Let

S_{n}^{k}

be a sun-graph with

k, n \geq 4

and n being even. Then

χ_{s}^{'} (S_{n}^{k}) = \{\begin{matrix} 2 k, & if n = 4; \\ 2 k - 1, & if n \geq 6 . \end{matrix}

Proof.

Since

k \geq 4

, it follows that

k - 2 \geq 2

. The proof is split into the following two cases.

Assume that $n = 4$ . Color $x_{0} x_{1}, x_{1} x_{2}, x_{2} x_{3}, x_{3} x_{0}$ with $1, 2, 3, 4$ , respectively; For $i = 0, 2, \dots, n - 2$ , we color $k - 2$ pendant edges in $L (x_{i})$ with colors $5, 6, \dots, k + 2$ ; For $i = 1, 3, \dots, n - 1$ , we color $k - 2$ pendant edges in $L (x_{i})$ with colors $k + 3, k + 4, \dots, 2 k$ . It is easy to see that the defining coloring is a strong edge- $2 k$ -coloring of $S_{4}^{k}$ . Hence $χ_{s}^{'} (S_{4}^{k}) \leq 2 k$ . Conversely, we note that every pendant edge of $S_{4}^{k}$ has distance at most two to any edge in $E (C_{4})$ . This implies that, for any strong edge coloring of $S_{4}^{k}$ , the color of any pendant edge is distinct from that of edges in $C_{4}$ . Moreover, at least $2 (k - 2)$ colors are needed when we color the $4 (k - 2)$ pendant edges of $S_{4}^{k}$ . It follows therefore that $χ_{s}^{'} (S_{4}^{k}) \geq 4 + 2 (k - 2) = 2 k$ . This yields that $χ_{s}^{'} (S_{4}^{k}) = 2 k$ .
Assume that $n \geq 6$ . It is straightforward to conclude that $χ_{s}^{'} (S_{n}^{k}) \geq 2 k - 1$ since $S_{n}^{k}$ contains two adjacent k-vertices. Conversely, we notice that $S_{n}^{3}$ is a spanning subgraph of $S_{n}^{k}$ . By Lemma 4, $S_{n}^{3}$ has a strong edge-5-coloring $ϕ$ using colors $1, 2, 3, 4, 5$ . Based on $ϕ$ , we can color the remaining $k - 3$ pendant edges in $L (x_{i})$ with colors $6, 7, \dots, k + 2$ for each $i = 0, 2, \dots, n - 2$ ; and color the remaining $k - 3$ pendant edges in $L (x_{i})$ with colors $k + 3, k + 4, \dots, 2 k - 1$ for each $i = 1, 3, \dots, n - 1$ . The extended coloring is a strong edge- $(2 k - 1)$ -coloring of $S_{n}^{k}$ . It therefore turns out that $χ_{s}^{'} (S_{n}^{k}) \leq 2 k - 1$ . Consequently, $χ_{s}^{'} (S_{n}^{k}) = 2 k - 1$ .

□

Lemma 6.

Let

n \geq 4

be an odd number. Then

(1): $χ_{s}^{'} (S_{n}^{4}) \leq 8$ .
(2): $χ_{s}^{'} (S_{n}^{5}) \leq 11$ .

Proof.

We first prove (1), by discussing two cases below.

Assume that $n = 7$ . Give a strong edge-7-coloring $ϕ$ of $S_{7}^{4}$ as follows: $ϕ (x_{i} x_{i + 1}) = i + 1$ for $i = 0, 1, \dots, 6$ , where indices are taken as modulo 7; then we color $L (x_{0})$ with $3, 5$ , $L (x_{1})$ with $4, 6$ , $L (x_{2})$ with $5, 7$ , $L (x_{3})$ with $1, 6$ , $L (x_{4})$ with $2, 7$ , $L (x_{5})$ with $1, 3$ , and $L (x_{6})$ with $2, 4$ .
Assume that $n \neq 7$ . By Lemma 4, $S_{n}^{3}$ admits a strong edge-5-coloring $ϕ$ using the colors $1, 2, \dots, 5$ so that $e_{0}^{1}, e_{1}^{1}, \dots, e_{n - 1}^{1}$ have been colored. Afterward, we extend $ϕ$ to the remaining edges of $S_{n}^{4}$ by coloring $e_{0}^{2}$ with 6, ${e_{1}^{2}, e_{3}^{2}, \dots, e_{n - 2}^{2}}$ with 7, and ${e_{2}^{2}, e_{4}^{2}, \dots, e_{n - 1}^{2}}$ with 8. It is easily seen that the resultant coloring is a strong edge-5-coloring of $S_{n}^{4}$ .

Next we prove (2). By the result of (1),

S_{n}^{4}

has a strong edge-8-coloring

ϕ

using the colors

1, 2, \dots, 8

. Based on

ϕ

, we can color

e_{0}^{3}

with 9,

{e_{1}^{3}, e_{3}^{3}, \dots, e_{n - 2}^{3}}

with 10, and

{e_{2}^{3}, e_{4}^{3}, \dots, e_{n - 1}^{3}}

with 11. This leads to a strong edge-11-coloring of

S_{n}^{5}

. □

We first establish a useful claim:

Claim 1.

Let

A_{i} = {e_{i}^{'}, e_{i}^{''}} \subseteq L (x_{i})

for

i = 0, 1, \dots, n - 1

. Let

A = A_{0} \cup A_{1} \cup \dots \cup A_{n - 1}

. Then A can be strongly edge-5-colored on the graph

S_{n}^{k}

Proof.

Since

n \geq 5

is odd, we can give an edge 5-coloring

π

of A as follows: coloring

A_{1}

with 2, 4;

A_{2}

with 3, 5;

A_{3}

with 1, 4; each of

A_{0}, A_{5}, A_{7}, \dots, A_{n - 2}

with 1, 3; and each of

A_{4}, A_{6}, A_{8}, \dots, A_{n - 1}

with 2, 5. It is easy to confirm that

π

is a strong edge-5-coloring of A restricted in the graph

S_{n}^{k}

. □

Lemma 7.

Let

k \geq 6

, and let

n \geq 5

be odd. Then

χ_{s}^{'} (S_{n}^{k}) \leq ⌈ 2.5 k - 2 ⌉

Proof.

If k is even, then by Lemma 6(1) and repeatedly applying Claim 1, we get that

χ_{s}^{'} (S_{n}^{k}) \leq 8 + 5 \cdot \frac{k - 4}{2} = 2.5 k - 2 = ⌈ 2.5 k - 2 ⌉

If k is odd, then by Lemma 6(2) and repeatedly applying Claim 1, we get that

χ_{s}^{'} (S_{n}^{k}) \leq 11 + 5 \cdot \frac{k - 5}{2} = 2.5 k - 1.5 = ⌈ 2.5 k - 2 ⌉

. □

3. Outerplanar Graphs

Suppose that G is a connected outerplanar graph. Let

I \subseteq V (G)

be a clique-cut of G with

1 \leq | I | \leq 2

; that is,

G [I]

K_{1}

K_{2}

such that

G - I

is disconnected. If

G - I

has at least two components each containing at least one edge, then I is said to be a separable clique-cut.

For a separable clique-cut I of G, let

H_{1}, H_{2}, \dots, H_{s}

(

s \geq 2

) denote the components of

G - I

with

| E (H_{1}) | \geq 1

and

| E (H_{2}) | \geq 1

. We set

G_{1} = G [E (H_{1}) \cup E (I)]

and

G_{2} = G [E (H_{2}) \cup \dots \cup E (H_{s}) \cup E (I)]

, where

E (I)

denotes the set of edges in G which are incident to at least one vertex in I.

The following lemma plays a crucial role in the proof of our main results.

Lemma 8.

Let G be a connected outerplanar graph with a separable clique-cut I. Suppose that

G_{1}

and

G_{2}

are defined as above. Then

χ_{s}^{'} (G) = max {χ_{s}^{'} (G_{1}), χ_{s}^{'} (G_{2})}

Proof.

Let

l_{1} = χ_{s}^{'} (G_{1})

l_{2} = χ_{s}^{'} (G_{2})

, and

l = max {l_{1}, l_{2}}

. For

i = 1, 2

, let

ϕ_{i}

be a strong edge-l-coloring of

G_{i}

using the color set

C = {1, 2, \dots, l}

. By the definition of

G_{i}

, we deduce that

E (I) \subset E (G_{i})

for

i = 1, 2

, and

E (G_{1}) \cap E (G_{2}) = E (I)

. Observe that any edge in

E (G_{1}) \ E (I)

and any edge in

E (G_{2}) \ E (I)

have distance at least three in G. Moreover, since the distance between any two edges in

E (I)

is less than three, no two edges in

E (I)

are assigned same color in both

ϕ_{1}

and

ϕ_{2}

. So we may assume that

ϕ_{1} (e) = ϕ_{2} (e)

for each

e \in E (I)

. Combining

ϕ_{1}

and

ϕ_{2}

, we get a strong edge-l-coloring of G. This shows that

χ_{s}^{'} (G) \leq l

. On the other hand, since

G_{i}

is a subgraph of G, we have naturally that

χ_{s}^{'} (G) \geq max {χ_{s}^{'} (G_{1}), χ_{s}^{'} (G_{2})} = l

. Consequently,

χ_{s}^{'} (G) = l

. □

Theorem 1.

Let G be an outerplanar graph with

Δ \geq 4

. If G does not contain

F_{1}

as a subgraph, then

χ_{s}^{'} (G) \leq 3 Δ - 4

Proof.

Assume the contrary, let G be a counterexample with

| E (G) |

being as small as possible. Then G is connected,

| E (G) | \geq 3 Δ - 3

, and possesses the following properties:

(P1) No

F_{1}

is contained in G or its subgraphs.

(P2)G is not strongly edge-

(3 Δ - 4)

-colorable, but any subgraph H of G with

| E (H) | < | E (G) |

is strongly edge-

(3 Δ - 4)

-colorable.

In fact, if

Δ (H) < Δ

, then by Lemma 1,

χ_{s}^{'} (H) \leq 3 Δ (H) - 3 \leq 3 (Δ - 1) - 3 < 3 Δ - 4

since

Δ \geq 4

. If

Δ (H) = Δ

, then by the minimality of G,

χ_{s}^{'} (H) \leq 3 Δ (H) - 4 = 3 Δ - 4

(P3)G is not a tree; otherwise

χ_{s}^{'} (G) \leq 2 Δ - 1 < 3 Δ - 4

, contradicting (P2).

By Lemma 8, the following claim holds:

Claim 2.

G does not contain a separable clique-cut

I \subseteq V (G)

with

1 \leq | I | \leq 2

Embed G to the plane so that all the vertices lie in the boundary of

f_{0} (G)

. Let H denote the graph obtained from G by removing all leaves. By (P3) and Claim 2, we can easily deduce Claims 3 and 4 below.

Claim 3.

H is 2-connected, and

b (f_{0} (H))

forms a Hamiltonian cycle. This furthermore implies that all vertices in

V (G) \ V (H)

are leaves.

Claim 4.

Every inner edge

u v

of H is incident to an end-3-face

[u v w]

such that

d_{G} (w) = d_{H} (w) = 2

Claim 4 implies that

2 \leq Δ (H) \leq 4

; for otherwise H will contain an inner edge

x y

with

d_{H} (x) \geq 5

and

{x, y}

is a separable clique-cut of G.

Let

G^{*}

denote the graph obtained from G by carrying out repeatedly the following operation:

(*)

If x is a 2-vertex of H incident to an end-3-face

[x y z]

, then we split x into two new vertices

y_{1}

and

z_{1}

so that

y_{1}

joins with y, and

z_{1}

joins with z.

Intuitively speaking, every 2-vertex of H which is incident to an end-3-face is replaced by two leaves in G. It is easy to see that

Δ (G^{*}) = Δ (G)

, and

ϕ

is a strong edge-k-coloring of

G^{*}

if and only if

ϕ

is a strong edge-k-coloring of G.

It is easily observed that

G^{*}

is a spanning subgraph of some sun-graph

S_{n}^{k}

, where

k = Δ (G)

and n is the total number of

3^{+}

-vertices in G and the number of 2-vertices in G which are not on any 3-face. As an example, we observe the graphs G and

G^{*}

depicted in Figure 2.

Noting that

3 k - 4 \geq max {2 k, ⌈ 2.5 k - 2 ⌉}

, we deduce by Lemmas 5 and 7 that

χ_{s}^{'} (G) = χ_{s}^{'} (G^{*}) \leq χ_{s}^{'} (S_{n}^{k}) \leq 3 k - 4 = 3 Δ - 4

. This completes the proof of the theorem. □

Combining Theorem 1 and Lemmas 1 and 2(1), the following theorem holds:

Theorem 2.

Let G be an outerplanar graph with

Δ \geq 4

. Then

χ_{s}^{'} (G) \leq 3 Δ - 3

; and

χ_{s}^{'} (G) = 3 Δ - 3

if and only if G contains

F_{1}

as a subgraph.

Theorem 3.

Let G be an outerplanar graph with maximum degree

Δ = 3

. If G does not contain

F_{1}, F_{2}

F_{3}

as a subgraph, then

χ_{s}^{'} (G) \leq 5

Proof.

Assume the contrary, let G be a counterexample with

| E (G) |

being as small as possible. Then G is connected,

| E (G) | \geq 6

, and possesses the following properties:

(Q1) None of

F_{1}, F_{2}, F_{3}

is contained in G or its subgraphs.

(Q2)G is not strongly edge-5-colorable, but any subgraph H of G with

| E (H) | < | E (G) |

is strongly edge-5- colorable. Actually, if

Δ (H) \leq 2

, then by Lemma 3,

χ_{s}^{'} (H) \leq 5

. If

Δ (H) = 3

, then by the minimality of G, we obtain that

χ_{s}^{'} (H) \leq 5

(Q3)G is not a tree; otherwise

χ_{s}^{'} (G) \leq 5

, contradicting (Q2).

By Lemma 8, G does not contain a separable clique-cut

I \subseteq V (G)

with

1 \leq | I | \leq 2

Embed G to the plane so that all the vertices lie in

b (f_{0} (G))

. Removing all the leaves of G, we get a subgraph H of G. Similarly to the proof of Theorem 1, we conclude the following:

H is 2-connected, and all vertices in $V (G) \ V (H)$ are leaves.
Every inner edge $u v$ of H is incident to an end-3-face $[u v w]$ such that $d_{G} (w) = d_{H} (w) = 2$ .

Let

G^{*}

be the graph obtained from G by doing repeatedly the following operation:

(*)

If x is a 2-vertex of H incident to an end-3-face

[x y z]

in H, then we split x into two new vertices

y_{1}

and

z_{1}

so that

y_{1}

joins with y, and

z_{1}

joins with z.

Then

Δ (G^{*}) = Δ (G)

, and

χ_{s}^{'} (G) = χ_{s}^{'} (G^{*})

. Note that

G^{*}

is a spanning subgraph of some sun-graph

S_{n}^{3}

, where n is the total number of 3-vertices in G and the number of 2-vertices in G which are not on any 3-face. By Lemma 4, we derive immediately that

χ_{s}^{'} (G) = χ_{s}^{'} (G^{*}) \leq χ_{s}^{'} (S_{n}^{3}) \leq 5

. □

Combining Theorem 3 and Lemmas 1 and 2, we have the following:

Theorem 4.

Let G be an outerplanar graph with

Δ = 3

. Then

χ_{s}^{'} (G) \leq 6

; and

χ_{s}^{'} (G) = 6

if and only if G contains at least one of

F_{1}, F_{2}, F_{3}

as a subgraph.

When restricted to the family of bipartite outerplanar graphs G, smaller and tight upper bounds for

χ_{s}^{'} (G)

can be obtained.

Theorem 5.

Let G be a bipartite and outerplanar graph with maximum degree

Δ \geq 3

. Then

χ_{s}^{'} (G) \leq 2 Δ

; moreover,

χ_{s}^{'} (G) = 2 Δ

if and only if G contains

F_{2}

as a subgraph.

Proof.

We first show that

χ_{s}^{'} (G) \leq 2 Δ

. Assume the contrary, let G be a counterexample with

| E (G) |

being as small as possible. Then G is connected, other than a tree, and is not strongly edge

2 Δ

-colorable, but any subgraph H of G with

| E (H) | < | E (G) |

is strongly edge-

2 Δ

-colorable. Moreover, by Lemma 8, there is no separable clique-cut

I \subseteq V (G)

with

1 \leq | I | \leq 2

Embed G to the plane so that all the vertices occur in

b (f_{0} (G))

. Removing all the leaves of G, we obtain a subgraph H of G. Then H is a Hamiltonian cycle without chords, and

V (G) \ V (H)

are all leaves. So G is a subgraph of some

S_{n}^{k}

where

n = | V (H) |

is even and

k = Δ (G)

. By Lemma 5,

χ_{s}^{'} (G) \leq χ_{s}^{'} (S_{n}^{k}) \leq 2 k = 2 Δ

If G contains

F_{2}

as a subgraph, then

χ_{s}^{'} (G) \geq χ_{s}^{'} (F_{2}) = | E (F_{2}) | = 2 Δ

. Using the foregoing proof, we get that

χ_{s}^{'} (G) = 2 Δ

. Conversely, if G does not contain

F_{2}

as a subgraph, then similarly to the above discussion we can show that

χ_{s}^{'} (G) \leq 2 Δ - 1

. □

Author Contributions

Conceptualization, Y.W. (Ying Wang) and W.W.; methodology, Y.W. (Ying Wang) and Y.W. (Yiqiao Wang); validation, Y.W. (Yiqiao Wang) and W.W.; formal analysis, Y.W. (Yiqiao Wang); investigation, S.C.; resources, S.C.; writing-original draft preparation, Y.W. (Ying Wang) and S.C.; writing-review and editing, Y.W. (Ying Wang) and W.W.; visualization, Y.W. (Yiqiao Wang); supervision, W.W.; project administration, Y.W. (Yiqiao Wang); funding acquisition, Y.W. (Ying Wang) and W.W. All authors have read an agreed to the published version of the manuscript.

Funding

This research was funded by the NSFC (No. 12001156), NSFC (No. 12071048), NSFC (No. 12031018), Science and Technology Commission of Shanghai Municipality (No. 18dz2271000).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

All relevant date are within the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Fouquet, J.L.; Jolivet, J.L. Strong edge-colorings of graphs and applications to multi-k-gons. Ars Combin. 1983, 16, 141–150. [Google Scholar]
Molloy, M.; Reed, B. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 1997, 69, 103–109. [Google Scholar] [CrossRef]
Bruhn, H.; Joos, F. A stronger bound for the strong chromatic index. Combin. Probab. Comput. 2018, 27, 21–43. [Google Scholar] [CrossRef] [Green Version]
Faudree, R.J.; Gyárfás, A.; Schelp, R.H.; Tuza, D. The strong chromatic index of graphs. Ars Combin. 1990, 29, 205–211. [Google Scholar]
Chartrand, G.; Harary, F. Planar permutation graphs. Ann. Inst. Henri Poincaré Sect. B (N.S.) 1967, 3, 433–438. [Google Scholar]
Wang, Y.; Wang, P.; Wang, W. Strong chromatic index of K₄-minor free graphs. Inform. Process. Lett. 2018, 129, 53–56. [Google Scholar] [CrossRef]
Hocquard, H.; Ochem, P.; Valicov, P. Strong edge-colouring and induced matching. Inform. Process. Lett. 2013, 113, 836–843. [Google Scholar] [CrossRef] [Green Version]

Figure 1. Configurations

F_{1}, F_{2}

, and

F_{3}

Figure 1. Configurations

F_{1}, F_{2}

, and

F_{3}

Figure 2.

G^{*}

is obtained from G by carrying out

(*)

, and

G^{*}

is a subgraph of

S_{5}^{4}

Figure 2.

G^{*}

is obtained from G by carrying out

(*)

, and

G^{*}

is a subgraph of

S_{5}^{4}

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, Y.; Wang, Y.; Wang, W.; Cui, S. Strong Chromatic Index of Outerplanar Graphs. Axioms 2022, 11, 168. https://doi.org/10.3390/axioms11040168

AMA Style

Wang Y, Wang Y, Wang W, Cui S. Strong Chromatic Index of Outerplanar Graphs. Axioms. 2022; 11(4):168. https://doi.org/10.3390/axioms11040168

Chicago/Turabian Style

Wang, Ying, Yiqiao Wang, Weifan Wang, and Shuyu Cui. 2022. "Strong Chromatic Index of Outerplanar Graphs" Axioms 11, no. 4: 168. https://doi.org/10.3390/axioms11040168

APA Style

Wang, Y., Wang, Y., Wang, W., & Cui, S. (2022). Strong Chromatic Index of Outerplanar Graphs. Axioms, 11(4), 168. https://doi.org/10.3390/axioms11040168

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Strong Chromatic Index of Outerplanar Graphs

Abstract

1. Introduction

2. Sun-Graphs

3. Outerplanar Graphs

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI