Open AccessArticle

The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles

Huajing Lu

and

Fengwei Li

^1,2,*

College of Basic Science, Ningbo University of Finance & Economics, Ningbo 315175, China

Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

Author to whom correspondence should be addressed.

Axioms 2023, 12(2), 173; https://doi.org/10.3390/axioms12020173

Submission received: 22 December 2022 / Revised: 20 January 2023 / Accepted: 30 January 2023 / Published: 8 February 2023

(This article belongs to the Special Issue Graph Theory and Discrete Applied Mathematics)

Download

Browse Figures

Review Reports Versions Notes

Abstract

A graph G has a

(d, h)

-decomposition if there is a pair

(D, F)

such that F is a subgraph of G and D is an acyclic orientation of

G - E (F)

, where the maximum degree of F is no more than h and the maximum out-degree of D is no more than d. This paper proves that toroidal graphs having no adjacent triangles are

(3, 1)

-decomposable, and for

{i, j} \subseteq {3, 4, 6}

, toroidal graphs without i- and j-cycles are

(2, 1)

-decomposable. As consequences of these results, toroidal graphs without adjacent triangles are 1-defective DP-4-colorable, and toroidal graphs without i- and j-cycles are 1-defective DP-3-colorable for

{i, j} \subseteq {3, 4, 6}

Keywords:

toroidal graph; defective coloring; decomposability; defective DP-coloring

MSC:

05C15; 05C20

1. Introduction

The coloring of graphs coming from the famous four-color conjecture has always been one of the significant research topics in the field of graph theory. Colorings of graphs have a strong application background and have been widely used in computer science, optimization problems, network design and other fields. The concept of classical coloring of graphs has been extended to many aspects. List coloring, online list coloring, and DP-coloring are significant research topics in the field of graph coloring.

The graph mentioned in this paper is finite, without multiple edges and loops. For undefined notation and terminology, one can see [1].

Defective coloring was introduced by Harary, Jones [2], Andrews, Jacobson [3], and Cowen, Cowen and Woodall [4], independently. Let d be a nonnegative integer, and let

G = (V, E)

be a graph. We use

Δ (G)

to represent the maximum degree of G. If G has a coloring of the vertices such that each vertex v has at most d neighbors receiving the same color as v, i.e., the collection of vertices having same color form a subgraph F so that

Δ (F) \leq d

, then we say the G has a d-defective coloring. For a positive integer k, if there is a color set consisting of k colors so that G admits a d-defective coloring, then we say that G is d-defective k-colorable. For any vertex v, if there exists a mapping L distributing v a collection of k available colors, then L is named as a k-list assignment of G. For a k-list assignment L, if G has a d-defective coloring

ψ

satisfying

ψ (v) \in L (v)

for any

v \in V (G)

, then G is referred to as d-defective L-colorable. For any k-list assignment L, if graph G is d-defecitive L-colorable, we say G is d-defective k-choosable.

Defective coloring and defective list coloring has been concerned extensively in [5,6,7,8,9]. Škrekovski [8] showed that all planar graphs are 2-defective and 3-choosable, any planar graphs without triangles are 1-defective and 3-choosable. Later, Cushing and Kierstead [5] proved that all planar graphs are not only 1-defective but also 4-choosable, this result can be reformulated as: given an arbitrary 4-list assignment L to a plane graph G, G always contains a subgraph F satisfying that

Δ (F) \leq 1

such that G minus all edges of F is L-colorable. Grytczuk and Zhu [10] strengthened this result. From the main result of [10], it concludes that each plane graph G certainly contains a subgraph F,

Δ (F) \leq 1

, so that

G - E (F)

is 4-choosable. It is noticed the subgraph F here is independent of L. Lih et al. [11] showed that a plane graph containing neither 4-cycles nor l-cycles is 1-defecive 3-choosable for

l \in {5, 6, 7}

. Recently, Lu and Zhu [12] strengthened this result. The main result in [12] concludes that if G a plane graph containing neither 4-cycles nor l-cycles, then G must contain a subgraph F whose maximum degree is no more than 1 so that G minus all edges of F is 3-choosable. On the other hand, Xu and Zhang [13] posed a question: if a planar graph does not contain any adjacent triangles, is it 1-defecive 3-choosable? Up to now, it has not yet been answered.

The statement that “G is d-defective k-colorable" is equivalent to the description that “G possesses a subgraph F satisfying that

Δ (F) \leq d

meet the condition that

G - E (F)

is k-colorable". On the other side, “G must be d-defective k-choosable" is considerably weaker than the statement that “G has a subgraph F,

Δ (F) \leq d

, in order that

G - E (F)

is k-choosable". Although every planar graph is not only 2-defective but also 3-choosable, Kim et al. [14] proved that there must exist planar graph G meet the condition that for any subgraph F of G satisfying

Δ (F) \leq 3

G - E (F)

is definitely not 3-choosable. The statement below was proved in [15]:

(*) Any planar graph G possesses a subgraph F having

Δ (F) \leq 6

such that

G - E (F)

must be 3-choosable.

Is this really right when the maximum degree of F in (*) is reduced to 5 or 4? This question remains open.

Statement (*) is actually a consequence of a stronger statement proved in [15]. Presume G is provided with an orientation D. We use

d_{D}^{+} (v)

, or simply

d^{+} (v)

, to represent the out-degree of v in D. In particular, if

d^{+} (v) = 0

, we call v a sink vertex. Similarly,

d_{D}^{-} (v)

, or simply

d^{-} (v)

, is the in-degree of v in D. v is a source vertex when

d^{-} (v) = 0

. Let

Δ_{D}^{+}

to represent the maximum out-degree of G. Assume

h, d

are non-negative integers. A graph G possesses a

(d, h)

-decomposition if there is a pair

(D, F)

such that F is a subgraph contained in G such that

Δ (F) \leq h

, D is an acyclic orientation of

G - E (F)

so that

Δ_{D}^{+} \leq d

. Or equivalently,

(d, h)

-decomposition of G decomposes G into two subgraphs F and T such that

Δ (F) \leq h

and T is d-degenerate. If G admits a

(d, h)

-decomposition, then G is referred to as

(d, h)

-decomposable. It was shown in [15] that every plane graph is

(2, 6)

-decomposable. Note that d-degenerate graphs are

(d + 1)

-choosable, so (*) is a consequence of the above result.

The

(d, h)

-decomposability is a problem of independent interest. It was showed in [15] that planar graphs are

(4, 1)

-decomposable and

(3, 2)

-decomposable. These results are sharp, in this sense, the maximum degree condition cannot be reduced.

This paper focuses on the

(d, h)

-decomposability of toroidal graphs. A closed surface which is a sphere possessing a single handle is named as a torus. Supposing that a graph can be imbedded into a torus, then we call it a toroidal graph. We prove that all toroidal graphs having no adjacent triangles are

(3, 1)

-decomposable, and all toroidal graphs without i- and j-cycles are

(2, 1)

-decomposable, where

{i, j} \subseteq {3, 4, 6}

. As consequences of these results, all toroidal graphs without adjacent triangles are 1-defective DP-4-colorable, and all toroidal graphs without i- and j-cycles are 1-defective DP-3-colorable. These strengthens the results in [13] that all toroidal graphs which do not contain adjacent triangles are 1-defective 4-choosable and in [6] that all toroidal graphs without i- and j-cycles are 1-defective 3-choosable.

Assume G is a toroidal graph having been embedded.

V (G)

F (G)

and

E (G)

represent the collections of vertices, faces and edges of G, respectively. Moreover,

| V (G) |

| F (G) |

and

| E (G) |

, respectively, are the number of vertices, faces and edges.

d_{G} (u)

represents the degree of

u \in V (G)

. Without causing confusion, we often write

d (u)

for

d_{G} (u)

. We call u a p-vertex, a

p^{+}

-vertex and a

p^{-}

-vertex, respectively, when

d (u) = p

d (u) \geq p

and

d (u) \leq p

. For an edge

u v \in E (G)

, if

d (v) = a

and

d (u) = b

, then we say v is an a-neighbour of u and u is a b-neighbour of v. A cycle with length l is called an l-cycle. A 3-cycle is often called a triangle. An l-cycle is called short cycle if

l \leq 6

. For a face

f \in F (G)

, if

x_{1}, x_{2}, \dots, x_{n}

are consecutive vertices belonging to f in cyclic order, write

f = [x_{1} x_{2} \dots x_{n}]

. Assume

f = [x_{1} x_{2} \dots x_{k}]

is a k-face. If

d (x_{i}) = d_{i}

i = 1, 2, \dots, k

, we say f is a

(d_{1}, d_{2}, \dots, d_{k})

-face.

2. The $(3, 1)$ -Decomposability of Toroidal Graphs

This section is about the decomposability of toroidal graphs without adjacent triangles. We prove Theorem 1.

Theorem 1.

All toroidal graphs which do not contain any adjacent triangles are

(3, 1)

-decomposable.

Suppose Theorem 1 is false. Then we choose a counterexample G such that the number of vertices is the smallest. We first derive some properties of G.

Definition 1.

Let

f = [v_{1} v_{2} v_{3}]

be a

(4, 5, 5)

-face. If either

v_{2}

v_{3}

has a 4-neighbour other than

v_{1}

, then f is a minor 3-face.

Lemma 1.

G satisfies the following properties:

(1): there is no $3^{-}$ -vertex in G;
(2): there is no adjacent 4-vertices in G;
(3): there is no minor 3-face in G.

Proof.

(1) Suppose that w is a

3^{-}

-vertex in G. Let

G^{*} = G - {w}

, then there must be a

(3, 1)

-decomposition

(D^{*}, F)

G^{*}

by the choice of G. Extend

D^{*}

to D such that w is a source vertex. Clearly, D is acyclic and

d_{D}^{+} (v) \leq 3

for each v of G. That is, G is

(3, 1)

-decomposable.

(2) Suppose that there exist two 4-vertices adjacent in G. Let

d (y) = d (z) = 4

for

y z \in E (G)

. Deleting y and z from G, we will obtain

G^{'}

. By induction hypothesis,

G^{'}

admits a

(3, 1)

-decomposition

(D^{'}, F^{'})

. Let

F_{1} = F^{'} \cup {y z}

. Extending

D^{'}

to D such that y and z are two source vertices, we get that G is

(3, 1)

-decomposable. Since D is acyclic and

d_{D}^{+} (v) \leq 3

for each v of G,

(D, F_{1})

is the pair we need.

(3) Assume that there exists a minor 3-face

f = [v_{1} v_{2} v_{3}]

, in which

d (v_{1}) = 4

and u is a 4-neighbour of

v_{3}

other than

v_{1}

, as shown in Figure 1a. Let

S = {v_{1}, v_{2}, v_{3}, u}

, and let

G^{″} = G - S

. Then

G^{″}

admits a

(3, 1)

-decomposition

(D^{″}, F^{″})

by the choice of G. Let

F_{2} = F^{″} \cup {v_{1} v_{2}, v_{3} u}

. Adding arcs

(v_{1}, v_{3})

and

(v_{3}, v_{2})

, and orienting all edges from S to

V (G) - S

, as shown in Figure 1b, we get an orientation D of

G - F_{2}

. It is easily found out that D is acyclic. Moreover,

d_{D}^{+} (v) \leq 3

v \in V (G)

. So

(D, F_{2})

is the pair we need, a contradiction. □

By the configurations established above, a discharging procedure will be applied to obtain a contradiction.

The initial charge,

c h

, is defined as: for

y \in V (G)

c h (y) = 3 d (y) - 10

, and for

f \in F (G)

c h (f) = 2 d (f) - 10

. Applying formula

| V (G) | - | E (G) | + | F (G) | = 0

and

\sum_{y \in V (G)} d (y) = 2 | E (G) | = \sum_{f \in F (G)} d (f)

, it follows that

\sum_{z \in V (G) \cup F (G)} c h (z) = 0 .

We denote the totally charge transferred from or to z by

c h (z \to)

and

c h (\to z)

, respectively. After transferring, final charge denoted by

c h^{*} (z)

will be obtained, that is,

c h^{*} (z) = c h (z) + c h (\to z) - c h (z \to)

. According to suitable discharging rules, we will get that for any vertices and faces z,

c h^{*} (z)

is nonnegative, and there exists an element

z \in V (G) \cup F (G)

satisfying

c h^{*} (z) > 0

. Since the total charge remains unchanged throughout the process, this leads to a contradiction.

Next we give the rules as follows:

R1: For a 4-vertex, it transfers $\frac{1}{2}$ charge to each incident 3- and 4-face.
R2: For a 5-vertex, it transfers $\frac{7}{4}$ charge to each incident 3-face and $\frac{1}{2}$ charge to each incident 4-face.
R3: For a $6^{+}$ -vertex, it transfers $\frac{7}{4}$ charge to each incident 3-face and $\frac{11}{12}$ charge to each incident 4-face.

Now, for all

z \in V (G) \cup F (G)

, we check the final charge of z. Let v be a k-vertex. For the absence of adjacent triangles in G, v is incident with no more than

⌊ \frac{k}{2} ⌋

3-faces. Assume

k \geq 7

, then

c h^{*} (v) \geq 3 k - 10 - (\frac{7}{4} \times ⌊ \frac{k}{2} ⌋ + \frac{11}{12} \times (k - ⌊ \frac{k}{2} ⌋)) > 0

Assume

k = 6

, then

c h (v) = 8

, v is incident with up to three 3-faces. When v is incident with exactly three 4-faces and three 3-faces, it concludes that

c h (v \to) = \frac{7}{4} \times 3 + \frac{11}{12} \times 3 = 8

. That is

c h^{*} (v) = 0

. Otherwise, that is, either v is incident with three 3-faces and no more than two 4-faces, or v is incident with no more than two 3-faces, then either

c h (v \to) \leq \frac{7}{4} \times 3 + \frac{11}{12} \times 2 < 8

c h (v \to) \leq \frac{7}{4} \times 2 + \frac{11}{12} \times 4 < 8

. That is

c h^{*} (v) > 0

Assume

k = 5

, then

c h (v) = 5

and the number of 3-face incident with v is no more than two. When v is incident with exactly two 3-faces and three 4-faces, we have

c h^{*} (v) = 5 - (\frac{7}{4} \times 2 + \frac{1}{2} \times 3) = 0

. Otherwise, either v is incident with exactly two 3-faces and no more than two 4-faces, or v is incident with at most one 3-face, then either

c h^{*} (v) \geq 5 - (\frac{7}{4} \times 2 + \frac{1}{2} \times 2) > 0

c h^{*} (v) \geq 5 - (\frac{7}{4} + \frac{1}{2} \times 4) > 0

Assume

k = 4

. Then, by R1,

c h^{*} (v) \geq 3 \times 4 - 10 - (\frac{1}{2} \times 4) = 0

Let f be an l-face. If

l \geq 5

, then we have

c h^{*} (f) \geq 2 l - 10 \geq 0

Assume

l = 4

. If there is at least one

6^{+}

-vertex on f, then we get

c h^{*} (f) \geq 2 \times 4 - 10 + \frac{11}{12} + \frac{1}{2} \times 3 > 0

. Otherwise,

c h^{*} (f) = 2 \times 4 - 10 + \frac{1}{2} \times 4 = 0

Assume

l = 3

. By Lemma 1 (2), there is at most one 4-vertex on f. If f has no 4-vertex, then

c h^{*} (f) \geq 2 \times 3 - 10 + \frac{7}{4} \times 3 > 0

. If f has one 4-vertex, then

c h^{*} (f) \geq 2 \times 3 - 10 + \frac{1}{2} + \frac{7}{4} \times 2 = 0

To sum up, for any

z \in V (G) \cup F (G)

, we get a nonnegative

c h^{*} (z)

. If we can find an element

z \in V (G) \cup F (G)

satisfying

c h^{*} (z) > 0

, then we are done. Suppose that

c h^{*} (z) = 0

for any

z \in V (G) \cup V (f)

. Then G has no

7^{+}

-vertex. If G contains a 6-vertex u, then u must be incident with exactly three 4-faces and three 3-faces. Thus, the 4-face incident with u is the the element we need. So we may assume that

6^{+}

-vertex is forbidden in G. If G contains a 5-vertex w, then w must be incident with two 3-faces denoted by

g_{1}, g_{2}

and three 4-faces. Furthermore, both

g_{1}

and

g_{2}

are

(4, 5, 5)

-faces. Thus,

g_{1}

is a minor 3-face, contradicting to the choice of G. Now we find that G is 4-regular which contradicts to Lemma 1 (2). Theorem 1 is proved.

3. The $(2, 1)$ -Decomposability of Toroidal Graphs

This section considers the decomposability of a toroidal graph which does not contain some short cycles.

Theorem 2.

For

{i, j} \subseteq {3, 4, 6}

, all toroidal graphs without i- and j-cycles are

(2, 1)

-decomposable.

Assume Theorem 2 is not true and G is a counterexample of Theorem 2 such that

| V (G) |

is the smallest. The lemma below can be got straightforwardly, since it is quite similar to Lemma 1 (1) and (2).

Lemma 2.

The forbidden structures of G are as follows:

(1): $2^{-}$ -vertex;
(2): a 3-vertex adjacent to another 3-vertex.

According to structural properties above, combining with discharging procedure, we will gain a contradiction to finish the proof of Theorem 2. The definition of the initial charge,

c h

, is expressed as: for any

z \in V (G) \cup F (G)

c h (z) = d (z) - 4

. By

| V (G) | - | E (G) | + | F (G) | = 0

and

\sum_{v \in V (G)} d (v) = 2 | E (G) | = \sum_{f \in F (G)} d (f)

, it concludes that

\sum_{z \in V (G) \cup F (G)} c h (z)

is equal to zero. Applying suitable rules, we will get to an eventual charge such that

c h^{*} (z) \geq 0

for

z \in V (G) \cup F (G)

. Furthermore, we shall find an element

z \in V (G) \cup F (G)

satisfying

c h^{*} (z) > 0

. Since the total charge keeps fixed throughout the process, this leads to a contradiction.

For simplicity, we use

G_{l, m}

to represent the collection of toroidal graphs G containing neither l-cycle nor m-cycle. For

{l, m} \subseteq {3, 4, 6}

, we need to define different discharging rules for graphs

G \in G_{l, m}

. So we discuss in three cases.

Case 1.

G \in G_{3, 4}

In this case, we only need one rule.

R1.1: A $5^{+}$ -face transfers $\frac{1}{3}$ to every incident 3-vertex.

For

d (v) = 3

c h^{*} (v) = 3 - 4 + \frac{1}{3} \times 3 = 0

. For

d (v) \geq 4

, there is no charge discharged, we have

c h^{*} (v) = c h (v) = d (v) - 4 \geq 0

. For

d (f) \geq 5

, by Lemma 2 (2), f is incident with no more than

⌊ \frac{d (f)}{2} ⌋

3-vertices. So

c h^{*} (f) = d (f) - 4 - ⌊ \frac{d (f)}{2} ⌋ \times \frac{1}{3} > 0

. It is easy to see that

\sum_{x \in V (G) \cup F (G)} c h^{*} (x)

is positive, which leads to a contradiction.

Case 2.

G \in G_{3, 6}

Under this circumstances, the minimal counterexample has more properties.

Definition 2.

Assume v is a 3-vertex in G. We say the 3-vertex v is light if v is incident with one

(3, 4, 4, 4)

-face and two

(3, 4, 3, 4, 4)

-faces.

Lemma 3.

The additional forbidden structures of G are:

(1): a $(3, 4, 3, 4)$ -face;
(2): a light 3-vertex.

Proof.

(1) Assume G has a

(3, 4, 3, 4)

-face

f = [u_{1} u_{2} u_{3} u_{4}]

, where

d (u_{1}) = d (u_{3}) = 3

. Let

S = V (f)

. Deleting S from G, we will get

G^{'}

. Obviously,

G^{'}

has a pair

(D^{'}, F^{'})

such that

G^{'}

(2, 1)

-decomposable. Let

F = F^{'} \cup {u_{1} u_{4}, u_{2} u_{3}}

. Adding arcs

(u_{1}, u_{2})

and

(u_{3}, u_{4})

, and orienting all edges from a vertex in S to a vertex in

V (G) - S

, we will get an orientation D of

G - F

. It follows that

d_{D}^{+} (v) \leq 2

v \in V (G)

, D is acyclic. That is to say, G is

(2, 1)

-decomposable, a contradiction.

(2) Assume G has a light 3-vertex u. Let

f_{1} = [v_{1} v_{2} v_{3} v_{4} u]

f_{2} = [v_{4} v_{5} v_{6} v_{7} u]

and

f_{3} = [v_{7} v_{8} v_{1} u]

be three faces that incident with u, as depicted in Figure 2a. According to the definition of light 3-vertex and Lemma 2 (2), assume that the other two 3-vertices are either

v_{2}

and

v_{6}

, or

v_{3}

and

v_{6}

, or

v_{3}

and

v_{5}

. Assume

v_{2}

and

v_{6}

are 3-vertices. Let

S = \cup_{i = 1}^{3} V (f_{i})

, and let

G^{'} = G - S

. From the choice of G,

G^{'}

includes a subgraph

F^{'}

and there is an orientation

D^{'}

G^{'} - F^{'}

such that

G^{'}

has a

(2, 1)

-decomposition. Let

F = F^{'} \cup {v_{2} v_{3}, v_{4} v_{5}, v_{6} v_{7}, v_{1} u}

. Adding arcs

(v_{2}, v_{1})

(v_{4}, v_{3})

(v_{6}, v_{5})

(v_{7}, v_{8})

(v_{1}, v_{8})

and

(u, v_{7})

, and orienting all edges between S and

V (G) - S

from a vertex in S to a vertex in

V (G) - S

, as shown in Figure 2b, we obtain an orientation D. Clearly, D is acyclic,

d_{D}^{+} (v) \leq 2

and

d_{F} (v) \leq 1

for all

v \in V (G)

. It follows that G is

(2, 1)

-decomposable and

(D, F)

is the pair we need. The other two cases are completely similar, we omit the details while the locally subgraph and orientation are represented in Figure 2c. □

One rule on a 3-vertex is listed as follows:

R2.1: For a 3-vertex, if it is on a 4-face, then it acquires $\frac{1}{2}$ charge from each incident $5^{+}$ -face; otherwise, it acquires $\frac{1}{3}$ charge from each incident face.

Clearly, for

d (v) = 3

c h^{*} (v) = - 1 + \frac{1}{2} \times 2 = 0

c h^{*} (v) = - 1 + \frac{1}{3} \times 3 = 0

. For a

4^{+}

-vertex, there is no charge transferred from or to others, we have

c h^{*} (v) = c h (v)

. For

d (v) = 4

c h^{*} (v) = 0

. For

d (v) \geq 5

c h^{*} (v) > 0

. Let f be a k-face. For

k = 4

, clearly,

c h^{*} (f) = c h (f) = 0

. For

k \geq 5

, by Lemma 2 (2), f has no more than

⌊ \frac{k}{2} ⌋

3-vertices. Thus,

c h^{*} (f) = k - 4 - ⌊ \frac{k}{2} ⌋ \times \frac{1}{2} \geq 0

. Note that

c h^{*} (f) > 0

for

k \geq 7

Next we are going to find an element z in

V (G) \cup F (G)

satisfying

c h^{*} (z) > 0

. Suppose G has a

5^{+}

-vertex or a

7^{+}

-face, then we are done. We may assume G only has 3-, 4-vertices and 4-, 5-faces. Since 6-cycle is forbidden in G, by the choice of G, there must be a 5-face in G. Assume g is the 5-face. If g is incident with at most one 3-vertex which is on a 4-face, then g is the element that we need. Assume g has exactly two 3-vertices each of which is on a 4-face. Clearly, g is a

(3, 4, 3, 4, 4)

-face. Denote one of these two 3-vertices by u, the 4-face incident with u by

f_{u}

, and the 5-face incident with u other than g by

g_{u}

. By Lemma 3 (1),

f_{u}

is a

(3, 4, 4, 4)

-face. Combining with Lemma 3 (2),

g_{u}

is not a

(3, 4, 3, 4, 4)

-face. Then

g_{u}

is the element we need.

Consequently, we again get that

0 < \sum_{y \in V (G) \cup F (G)} c h^{*} (y) = \sum_{y \in V (G) \cup F (G)} c h (y) = 0

, a contradiction.

Case 3.

G \in G_{4, 6}

We shall define the following two rules:

R3.1: For a 3-face f, it acquires $\frac{1}{3}$ charge from each adjacent $7^{+}$ -face.
R3.2: For a 3-vertex v, if v is on a 3-face, it acquires $\frac{1}{2}$ charge from each incident $7^{+}$ -face; otherwise, v acquires $\frac{1}{3}$ charge from each incident face.

R3.2 guarantees

c h^{*} (v) = 0

for

d (v) = 3

. For any

4^{+}

-vertex, there is no transferring by rules, so

c h^{*} (v) \geq 0

. We then calculate the final charge of the faces. Let f be a k-face. When

k = 3

, R3.1 ensures that

c h^{*} (f) = 0

. When

k = 5

, since 6-cycle is forbidden in G, there does not exist any 3-face which is contiguous to f. By the rules, f only transfers

\frac{1}{3}

to each incident 3-vertex. By Lemma 2 (2), there is no more than two 3-vertices which are incident with f. Hence,

c h^{*} (f) \geq 5 - 4 - \frac{1}{3} \times 2 > 0

. For

k \geq 7

, denote the number of 3-vertices on f by s. From Lemma 2 (2), we have

s \leq ⌊ \frac{k}{2} ⌋

. By the rules, f transfers at most

\frac{1}{2} s

to 3-vertices and

(k - s) \times \frac{1}{3}

to 3-faces. Therefore,

c h^{*} (f) \geq k - 4 - \frac{1}{2} s - (k - s) \times \frac{1}{3} \geq \frac{7}{12} k - 4 > 0

. Note that

c h^{*} (f) > 0

for any

5^{+}

-face f.

Thus, for any vertex and face z we have

c h^{*} (z) \geq 0

. If there is a

5^{+}

-face in G, then

\sum_{z \in V (G) \cup F (G)} c h^{*} (z) > 0

, it is done. Presume graph G only contains 3-faces. G is a triangle according to the fact that G has no 4-cycle, a contradiction to the selection of G.

Author Contributions

H.L. and F.L. contributed equally in conceptualization, methodology, validation, formal analysis, writing—review and editing; project administration, H.L. All authors have read and agreed to the published version of the manuscript.

Funding

This Project was supported by Ningbo Natural Science Foundation (No. 2021J234).

Data Availability Statement

Not applicable.

Acknowledgments

The authors are very grateful to anonymous referees and editor for their constructive suggestions and insightful comments, which have considerably improved the presentation of this paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Bondy, J.A.; Murty, U.S.R. Graph Theory; Springer: New York, NY, USA, 2008. [Google Scholar]
Harary, F.; Jones, K. Conditional colorability n: Bipartite variations. Congressus Numer. 1985, 50, 205–218. [Google Scholar]
Andrews, J.; Jacobson, M. On a generalization of chromatic number. Congressus Numer. 1985, 47, 33–48. [Google Scholar]
Cowen, L.J.; Cowen, R.H.; Woodall, D.R. Defective colorings of graphs in surfaces:Partitions into subgraphs of bounded valency. J. Graph Theory 1986, 10, 187–195. [Google Scholar] [CrossRef]
Cushing, W.; Kierstead, H.A. Planar graphs are 1-relaxed, 4-choosable. Eur. J. Combin. 2010, 31, 1385–1397. [Google Scholar]
Dong, W.; Xu, B. On (3, 1)^*-Choosability of toroidal graphs. Discrete Math. Algorithms Appl. 2009, 1, 291–297. [Google Scholar]
Eaton, N.; Hall, T. Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. 1999, 25, 79–87. [Google Scholar]
Škrekovski, R. List improper colourings of planar graphs. Combin. Probab. Comput. 1999, 8, 293–299. [Google Scholar]
Woodall, D. Defective choosability of graphs in surfaces. Discuss. Math. Graph Theory 2011, 31, 441–459. [Google Scholar]
Grytczuk, J.; Zhu, X. The Alon-Tarsi number of a planar graph minus a matching. J. Combin. Theory Ser. B 2020, 145, 511–520. [Google Scholar]
Lih, K.; Song, Z.; Wang, W.; Zhang, K. A note on list improper coloring planar graphs. Appl. Math. Lett. 2001, 14, 269–273. [Google Scholar] [CrossRef]
Lu, H.; Zhu, X. The Alon-Tarsi number of planar graphs without cycles of lengths 4 and l. Discrete Math. 2020, 343, 111797. [Google Scholar]
Xu, B.; Zhang, H. Every toroidal graph without adjacent triangles is (4, 1)^*-choosable. Discrete Appl. Math. 2007, 155, 74–78. [Google Scholar] [CrossRef]
Kim, R.; Kim, S.-J.; Zhu, X. The Alon-Tarsi number of subgraphs of a planar graph. arXiv 2019, arXiv:1906.01506. [Google Scholar]
Cho, E.-K.; Choi, I.; Kim, R.; Park, B.; Shan, T.; Zhu, X. Decomposing planar graphs into graphs with degree restrictions. J. Graph Theory 2022, 101, 165–181. [Google Scholar] [CrossRef]

Figure 1. (a) A minor 3-face. (b) Local orientation of D, where the thick lines are edges in

F_{2}

Figure 1. (a) A minor 3-face. (b) Local orientation of D, where the thick lines are edges in

F_{2}

Figure 2. (a) A light 3-vetex. (b) and (c) Local orientation of D, where thick lines are edges in subgraph F.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 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

Lu, H.; Li, F. The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles. Axioms 2023, 12, 173. https://doi.org/10.3390/axioms12020173

AMA Style

Lu H, Li F. The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles. Axioms. 2023; 12(2):173. https://doi.org/10.3390/axioms12020173

Chicago/Turabian Style

Lu, Huajing, and Fengwei Li. 2023. "The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles" Axioms 12, no. 2: 173. https://doi.org/10.3390/axioms12020173

APA Style

Lu, H., & Li, F. (2023). The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles. Axioms, 12(2), 173. https://doi.org/10.3390/axioms12020173

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

Article Menu

The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles

Abstract

1. Introduction

2. The $(3, 1)$ -Decomposability of Toroidal Graphs

3. The $(2, 1)$ -Decomposability of Toroidal Graphs

Author Contributions

Funding

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

The Decomposability of Toroidal Graphs without Adjacent Triangles or Short Cycles

Abstract

1. Introduction

2. The ( 3 , 1 ) -Decomposability of Toroidal Graphs

3. The ( 2 , 1 ) -Decomposability of Toroidal Graphs

Author Contributions

Funding

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

2. The $(3, 1)$ -Decomposability of Toroidal Graphs

3. The $(2, 1)$ -Decomposability of Toroidal Graphs