Abstract
For non-negative integers and , if and are two partitions of a graph ’s vertex set , such that and induce two subgraphs of , called with maximum degree at most and with maximum degree at most , respectively, then the graph is said to be improper -colorable, as well as -colorable. A class of planar graphs without , and is denoted by . In 2019, Dross and Ochem proved that is -colorable, for each graph in . Given that , this inspires us to investigate whether is -colorable, for each graph in . In this paper, we provide a partial solution by showing that is (3, 3)-colorable, for each graph in .
1. Introduction
The term improper -colorable, as well as -colorable, refers to a graph , for non-negative integers and , if and are two partitions of a graph ’s vertex set , such that and induce two subgraphs of , called with maximum degree at most and with maximum degree at most , respectively. Planar graphs and their conditions suffice to be -colorable are widely studied. The cycle of length is denoted as or -cycle, for each . For each , Montassier and Ochem [1] constructed planar graphs without that are not -colorable. For any , planar graphs without , and that are not -colorable were constructed by Borodin et al. [2]. As opposed, some sufficient conditions for planar graphs to be -colorable for specific and are found. In 2022, Ma et al. [3] showed that every planar graph without and is (2, 9)-colorable. For any planar graph with girth (the length of the shortest cycle in the graph) at least 5, Borodin and Kostochka [4] proved that is (2, 6)-colorable. Recently, Zhang et al. [5] showed that planar graphs with girth at least 5 without adjacent 5-cycles are (1, 6)-colorable. Furthermore, Wang et al. [6] proved that planar graphs with girth at least 5 without adjacent 5-cycles are (3, 3)-colorable. This inspires us to investigate whether planar graphs without , and have this property.
Let be the class of planar graphs without , and . In [7], Choi et al. proved that is (0, 45)-colorable, for each graph in . Dross and Ochem [8] recently enhanced the findings by proving that is (0, 6)-colorable, for each graph in . Given that , this inspires us to investigate whether is -colorable, for each graph in . It should be noted that preventing , and from existing as subgraphs or induced subgraphs yields the same graph class. The following theorem provides a partial answer in this work.
Theorem 1. Every graph in is -colorable.
2. Notations and Helpful Properties
First, we present useful notions, observations, lemmas, and corollaries about a minimal planar graph in that is not (3, 3)-colorable.
We refer to the vertex set, edge set, and face set, respectively, as , , and . To indicate a face ’s boundary, we use the notation . In addition, the number of edges on the boundary of a face determines its degree. Let an -vertex (face), an -vertex (face), or an -vertex (face) be three different types of vertices (faces), each with a vertex (face) that has a degree of , at least , or at most , respectively.
Lemma 2. is connected.
Proof. Assume that is not connected. Then each connected component of is smaller than . Therefore, a -coloring is admissible for every connected component of . A -coloring of results from the union of these -colorings, which is contradictory.
Lemma 3. Every vertex in is a -vertex.
Proof. Assume that is a 1-vertex in . has a -coloring by employing the color set according to ’s minimality. Since we have two colors, we can extend to by properly coloring , a contrary to the choice of .
Observation 4. Every -face is bounded by -cycle for .
As a result of the absence of some cycles in , the following is easily observed.
Corollary 5. has neither 3-, 4-, nor 6-faces.
Lemma 6 (See [[9], in Lemmas 2.1, 2.2, and 2.3]). Let be a minimal graph which is not -colorable where . Then, we have the following:(i)If is a -vertex in , then is adjacent to at least two -vertices where one of which is a -vertex.(ii)If is a -vertex in , then is adjacent to at least one -vertex.
Lemma 6 yields the following lemma.
Lemma 7. Let be a minimal graph which is not (3, 3)-colorable. Then, we have the following:(i)If is a -vertex in , then is adjacent to at least two -vertices.(ii)If is a 5-vertex in , then is adjacent to at most four -vertices.
Lemma 8. If is a 2-vertex in , then is not incident to two 5-faces.
Proof. Let be a 2-vertex in incident to two faces and . Suppose to the contrary that and are 5-faces. By Observation 4, we may assume that a 5-cycle and a 5-cycle . Then, . If , then , a contrary to Lemma 7 (i). If , then is a 3-cycle, a contradiction. By symmetry, . Thus, . Hence, contains a 6-cycle. This contradiction completes the proof.
3. Proof of Theorem 1
Proof of Theorem 1. Suppose the contrary to Theorem 1 and let be a minimal counterexample. The following are our discharging processes.
Let be an initial charge of for all where .
Using Euler’s formula and Handshaking lemmaNext, we redistribute the charge of vertices and faces to have by transferring charge from one element to another later so that the total charge remains the same . However, upon the completion of the discharging, the final charge satisfies for all which is contradictory.
Discharging rules are as follows.
Let be a vertex of a graph . (R1) For , its incident 5-faces give charge to . (R2) For , its incident -faces give charge 1 to . (R3) For , its incident -faces give charge to . (R4) For , its adjacent -vertices give charge to .For each , the remaining part of the proof shows that .
If is a 4-vertex by (R1)-(R4), then it is obvious that .(i)Consider a 2-vertex . Lemma 7 (i) states that two -vertices are adjacent to . Moreover, has at least one incident -face according to Lemma 8. So, using (R1), (R2), and (R4), we get the following result: .(ii)Consider a 3-vertex . Lemma 7 (i) states that at least two -vertices are adjacent to a vertex . It should be noted that has three incident -faces. So, using (R3) and (R4), we get the following result: .(iii)Consider a 5-vertex . Lemma 7 (ii) states that at most four -vertices can be adjacent to a vertex . So, using (R4), we get the following result: .(iv)Consider a -vertex . Give a -vertex with . So, using (R4) and , we get the following result: .(v)Consider a 5-face . Lemma 7 (i) states that a face has no more than two incident 2-vertices. Case 1: There are two incident 2-vertices of a face . Lemma 7 (i) states that there are no 3-vertices incident to a face . So, using (R1), we get the following result: . Case 2: There is one incident 2-vertex of a face . Lemma 7 (i) states that at most two 3-vertices are incident to a face . So, using (R1) and (R3), we get the following result: . Case 3: There are no incident 2-vertices on a face . So, using (R3), we get the following result: .(vi)Consider a 7-face . Lemma 7 (i) states that a face has at most three incident 2-vertices. Case 1: Three 2-vertices are incident to a face . Lemma 7 (i) states that there are no 3-vertices incident to a face . So, using (R2), we get the following result: . Case 2: At most two 2-vertices are incident to a face . So, using (R2) and (R3), we get the following result: .(vii)Consider a -face where . Consider bounded by which each subscript is taken modulo . This case depends on (R2) and (R3). To facilitate the calculation, we provide a new rule in which is non-negative while its incident receive charges not less than by ones from (R2) and (R3). First, sends charge to each incident vertices ( for each ). Considering that is an -face, it implies that . Now, we redistribute the charge from as in the following new rule: () A -vertex gives (received from ) to or if it is a 2-vertex. Case 1: Consider a 2-vertex. Lemma 7 (i) states that a vertex has two adjacent -vertices which are on the boundary of , say and . So, using (), we get the following result: two its adjacent -vertices send charge to . Thus, receives charge from as in (R2). Case 2: Consider a 3-vertex. So, using (), receives charge at least as in (R3). Case 3: Consider a -vertex. So, using (R∗), we get the following result: a vertex send charge to or when it is a 2-vertex. Thus receives charge at least from as in (R2). Hence, .One can observe that our proof is finished when for every .
Data Availability
No data were used to support the findings of this study.
Conflicts of Interest
The authors declare that they have no conflicts of interest regarding the publication of this work.
Acknowledgments
This work (Grant No. RGNS 65-028) was supported by the Office of the Permanent Secretary, Ministry of Higher Education, Science, Research and Innovation (OPS MHESI), Thailand Science Research and Innovation (TRSI), and Kalasin University. In addition, we appreciate Kittikorn Nakprasit’s insightful suggestions and the constructive discussion.