WorksMathematics
On strong odd colorings of sparse graphs
Abstract
A strong odd coloring of a graph is a proper vertex coloring such that for every vertex , each color appearing on the neighborhood of appears an odd number of times. We investigate strong odd colorings of sparse graphs, where sparsity of a graph is measured in terms of maximum average degree, denoted . We prove that the optimal threshold on the maximum average degree guaranteeing a strong odd -coloring is as . Moreover, for every , this threshold is strictly smaller than the threshold for odd -coloring. We also determine the sharp threshold on the maximum average degree guaranteeing a strong odd -coloring: every graph with has a strong odd -coloring, and this bound is sharp. In addition, we show that every graph with and no induced -cycle has a strong odd -coloring. Note that the -cycle has maximum average degree 2 and no strong odd -coloring.
Introduction
All graphs in this paper are finite and simple, unless stated otherwise. For a graph , let , , and denote its vertex set, edge set, and maximum degree, respectively. The complete graph on vertices is denoted by . A proper -coloring of a graph is a function that assigns distinct colors to adjacent vertices, and the chromatic number of , denoted , is the minimum for which has a proper -coloring.
Recently introduced by Kwon and Park [7], a strong odd -coloring of a graph is a proper -coloring such that for each vertex , every color appearing on its neighborhood appears an odd number of times. The strong odd chromatic number of , denoted , is the minimum for which has a strong odd -coloring. Note that every graph has a strong odd coloring, as we can give every vertex its own color.
Strong odd coloring lies between two well-studied coloring notions. The first is an odd -coloring, introduced by Petr̆uševski and Škrekovski [9], which is a proper -coloring such that, for every nonisolated vertex , there exists a color appearing an odd number of times on . The second is a proper coloring of the square of , denoted , which is the graph obtained from by adding edges between vertices at distance 2. For a graph , every proper coloring of is a strong odd coloring of , since for every vertex , the vertices in receive pairwise distinct colors. Therefore, , where is the minimum for which has an odd -coloring.
Even for a sparse graph , strong odd coloring of and proper coloring of behave quite differently. Indeed, the closed neighborhood of a vertex in becomes a clique in , so . In particular, squares of planar graphs have unbounded chromatic number. In contrast, there exists a minimum constant for which all planar graphs have a strong odd -coloring. Caro et al. [1] proved that , which was recently improved to by Santra [11]. On the other hand, , as there is a planar graph with strong odd chromatic number 20 [4, 11]. More generally, Goetze et al. [4] showed that every proper minor-closed class has bounded strong odd chromatic number, and Pilipczuk [10] extended this result to classes of bounded expansion. Nevertheless, the strong odd chromatic number cannot be bounded by a function of the odd chromatic number [4].
In this paper, we study strong odd colorings of sparse graphs, where sparsity is measured in terms of maximum average degree; the maximum average degree of a graph , denoted , is
Kwon and Park [7] proved that every graph with satisfies , and every graph with no 4-cycle and satisfies . In contrast, we seek conditions on the maximum average degree that guarantee a strong odd -coloring for a given number of colors.
The corresponding problem for odd coloring is completely resolved for : the exact threshold on the maximum average degree guaranteeing an odd -coloring is known [2, 3]. Namely, for , if is a graph with , then . The bound on the density is sharp: the graph obtained by subdividing every edge of exactly once satisfies and . Therefore, for every , the odd chromatic number is bounded on the class of graphs with , whereas it is unbounded on the class of graphs with .
Our first main result establishes the analogous phenomenon for strong odd coloring. Namely, for every , the strong odd chromatic number is bounded on the class of graphs with . We also determine the optimal order of this bound as .
Theorem 1.1. Let be an integer. For a graph , if , then .
Note that the density bound in Theorem 1.1 is . We also construct a family of graphs satisfying and . Therefore, the density threshold guaranteeing a strong odd -coloring is as . Equivalently, the minimum number of colors required for a strong odd coloring of every graph with is as . Moreover, satisfies for every . Thus, , so the threshold on the maximum average degree guaranteeing a strong odd -coloring is strictly smaller than that for odd -coloring.
We next consider strong odd colorings with few colors. For five colors, we obtain the following sharp result.
Theorem 1.2. For a graph , if , then .
The bound on the maximum average degree in Theorem 1.2 is sharp as there is a graph with and no strong odd 5-coloring.
For four colors, the 5-cycle has maximum average degree 2 and no strong odd 4-coloring. Nonetheless, excluding induced 5-cycles allows us to obtain a bound greater than 2 on the maximum average degree that guarantees a strong odd 4-coloring.
Theorem 1.3. If a graph has no induced 5-cycles and , then .
The graph consisting of two 4-cycles sharing exactly one vertex has no induced 5-cycle, has maximum average degree , and has no strong odd 4-coloring.
Our results imply corollaries regarding planar graphs with girth restrictions. Every planar graph with girth at least has maximum average degree less than . From our results, we obtain the following corollary:
Corollary 1.4. Let be a planar graph with girth at least .
If , then .
If , then .
If , then .
The paper is organized as follows. In § 2, we present the graph showing that Theorem 1.2 is sharp and the graph related to Theorem 1.1. In § 3, we prove structural lemmas to establish the reducible configurations needed to prove Theorems 1.2 and 1.3, which are completed in § 4 and § 5, respectively, via discharging. In § 6, we prove Theorem 1.1 using a theorem of Lužar, Petruševski, and Škrekovski [8] on odd edge-colorings of loopless multigraphs. Finally, we suggest a potential future research direction in § 7.
We end this section with some notation used throughout the paper. For a graph and a vertex , let , , and denote the degree, open neighborhood, and closed neighborhood of , respectively. Subscripts are omitted when the graph is clear. A -vertex, a -vertex, and a -vertex are vertices of degree , at least , and at most , respectively. A -neighbor, a -neighbor, and a -neighbor are neighbors of degree , at least , and at most , respectively.
Extremal examples
In this section, we construct sparse graphs that have no strong odd -coloring. Note that a subgraph of with average degree is always an induced subgraph. Moreover, if , then must have minimum degree at least 2, otherwise we can remove a vertex of degree at most 1 from to increase its average degree.
Five colors
Let be the graph obtained by connecting two vertices with three internally vertex-disjoint paths , , . We first show . Note that the average degree of is . Let be a (induced) subgraph of with the maximum average degree; note that must have minimum degree at least 2. If is a cycle, then . Otherwise, is the entire graph , so . Hence . Now, we prove has no strong odd 5-coloring. Suppose to the contrary that has a strong odd 5-coloring . Every two distinct vertices in are either adjacent or the neighborhood of a 2-vertex of . Therefore, all four vertices in must receive distinct colors. Since is adjacent to and , . If , then, since , must be the same as , so appears exactly twice on , which is a contradiction. Thus . Similarly, . Hence, does not appear on . By symmetry, also does not appear on . Then , which is a contradiction since now appears exactly twice on . Therefore has no strong odd 5-coloring.
A general construction
Given a graph , let denote the graph obtained from by subdividing each edge exactly once; the branch vertices are the vertices that existed before the subdivision. For an integer , set , , and . We define the graph from the disjoint union of and by adding a vertex adjacent to all branch vertices. Note that has vertices and edges.
We first show has no strong odd -coloring. Suppose to the contrary that has a strong odd -coloring . All neighbors of are branch vertices from and . Two branch vertices from the same copy of for some form the neighborhood of a 2-vertex, so must receive distinct colors. Therefore if two branch vertices receive the same color, then the color appears exactly twice on , which is a contradiction. Thus all vertices in receive pairwise distinct colors. Now, there is no color for , which is a contradiction. Hence, has no strong odd -coloring.
We show that where and . Note that the graph has average degree . Let be a (induced) subgraph of with maximum average degree; note that must have minimum degree at least 2. Suppose has and branch vertices from and , respectively. Since has minimum degree at least 2, we have . The graph is 2-degenerate, so every subgraph of has average degree less than 4. Thus, adding to does not decrease its average degree, so we may assume that contains . Moreover, whenever contains two branch vertices from the same copy of for some , adding the -path of length 2 to does not decrease its average degree. Therefore we may assume that has edges and vertices. Hence the average degree of is where and . Maximizing is equivalent to maximizing , since and the function is strictly increasing for . For fixed , the function is strictly convex in , since . By symmetry, is strictly convex in each variable, so every maximizer in must lie at a corner. Since , we have . Moreover, since and imply . Thus is maximized at a unique point , so .
Reducible configurations
Fix an integer . A graph is strong odd -minimal if has no strong odd -coloring but every proper subgraph of has a strong odd -coloring. In this section, we identify several reducible configurations that cannot occur in a strong odd -minimal graph . By minimality, is connected. We will use the color set of colors; in particular, when .
An open -thread is a path between distinct vertices with exactly internal vertices, which are all 2-vertices; are its terminals. A closed -thread is a cycle with exactly one -vertex and 2-vertices; the -vertex is its terminal. A thread is maximal if it is not properly contained in a longer thread. We say that a terminal is incident with the thread. For a positive integer , an -thread is a -thread where .
A 2-vertex is nearby a -vertex if lies on a thread incident with . A -vertex is responsible for nearby 2-vertices if the total number of nearby 2-vertices of , counted with multiplicity, is , where a nearby 2-vertex on a maximal open and closed thread incident with is counted once and twice, respectively.
Common configurations
Lemma 3.1. If , then satisfies the following:
(i) Every vertex has at most one 1-neighbor.
(ii) If a vertex has a 1-neighbor, then and . In particular, a 1-vertex has a -neighbor, and no -vertex has a 1-neighbor.
Proof. (i): Suppose to the contrary that a vertex has two 1-neighbors and . Let be a strong odd -coloring of . If has no neighbors in , then is a path on three vertices, which has a strong odd 3-coloring. Otherwise, has a neighbor distinct from , so color both and with . In either case, we obtain a strong odd -coloring of , which is a contradiction.
(ii): Suppose that a vertex has a 1-neighbor . Let be a strong odd -coloring of . If a color does not appear in , then let to obtain a strong odd -coloring of , which is a contradiction. Otherwise, all colors appear in , so . Moreover, every color distinct from appears on an odd number of times, so
Lemma 3.2. Let . If a vertex of is incident with a closed -thread, then and is a -vertex. Moreover, if has a 1-neighbor, then is a -vertex.
Proof. Let be a closed -thread. Let be a strong odd -coloring of . Since is a -vertex, has a neighbor not on . Let and . Suppose to the contrary that . Extend to by coloring with . Now, we can easily extend this coloring to a strong odd -coloring of , a contradiction. Therefore . Suppose to the contrary that . Since , there are distinct colors . Extend to by coloring with , respectively. If , then we color with the color of . Otherwise , so color the only uncolored vertex with . In either case, we obtain a strong odd -coloring of , which is a contradiction.
For the moreover part, suppose to the contrary that is a -vertex with a 1-neighbor . Since is a -vertex and , has a neighbor . Let be a strong odd -coloring of . Let and . Since , there is a color . In particular, . Extend to by coloring with and both and with . If , then we colored all of . Otherwise , so color the only uncolored vertex with a color not in . In either case, we obtain a strong odd -coloring of , which is a contradiction.
Four colors
Lemma 3.3. Let be an open -thread of with and let be an induced subgraph of where . Suppose that is a proper 4-coloring of where the strong odd condition is not violated at any vertex of , except possibly at . If either and or , then can be extended to so that the resulting coloring is proper and the strong odd condition is not violated at any vertex of , except possibly at . Moreover, if either and or and , then may be assigned any color other than in such an extension.
Proof. If and , then color with a color not in . Suppose . Sequentially, for each from to 2, color with a color not appearing on vertices within distance 2; is not colored yet, so there are at most three colors to avoid. Finally, color with a color not in .
We now prove the moreover part. Assign a color other than for . If and , then color with a color not in . Assume and . If , then color with and color with a color not in . Otherwise, , so color with a color not in and color with a color not in .
Lemma 3.4. satisfies the following:
There is no open -thread.
A 3-vertex is not incident with two internally disjoint open -threads.
A 4-vertex with a 1-neighbor is not incident with an open -thread.
Proof. (i): Suppose to the contrary that is an open 6-thread of . Let be a strong odd 4-coloring of . We may assume that ; otherwise, recolor with a color not in . Then color with a color not in . By the moreover part of Lemma 3.3, we can extend to a strong odd 4-coloring of , which is a contradiction.
(ii): Suppose to the contrary that a 3-vertex is incident with two open -threads and . Let be the neighbor of distinct from . Let be a strong odd 4-coloring of . Let be distinct colors not in . If , then color both with . Otherwise, extend to by coloring with or , respectively, so that and . In either case, for each , color with a color not in . By the moreover part of Lemma 3.3, we can extend to a strong odd 4-coloring of , which is a contradiction.
(iii): Suppose to the contrary that a 4-vertex has a 1-neighbor and is incident with an open -thread . Let be the neighbors of distinct from . Let be a strong odd 4-coloring of . Then are pairwise distinct. Color both with a color in . Choose a color for not in . By the moreover part of Lemma 3.3, we can extend to a strong odd 4-coloring of , a contradiction.
:::
Lemma 3.5. Let be a vertex of . If and has a 1-neighbor or , then cannot be incident with three pairwise internally disjoint open -threads where .
Proof. Suppose to the contrary that is incident with three pairwise internally disjoint open threads for for some . Let if is a 4-vertex with a 1-neighbor , and let otherwise. Let be a strong odd 4-coloring of . We first color with a color where
if ,
if ,
if .
By Lemma 3.3, we can extend to . We now show how to choose a color (that is not ) for to guarantee that the strong odd condition holds at . Let and . If , then color with if and with a color not in otherwise. If (so has a 1-neighbor ), then color with , and color with if and with a color not in otherwise. Thus, the strong odd condition holds at . By the moreover part of Lemma 3.3, any color that is not on can be extended to complete a strong odd 4-coloring of , a contradiction. □
Lemma 3.6. Every 4-vertex of is responsible for at most 18 nearby 2-vertices.
Proof. Suppose to the contrary that has a 4-vertex that is responsible for more than 18 nearby 2-vertices. By Lemma 3.2, is not incident with a closed -thread. By Lemma 3.4(i), there is no open -thread. Thus, must be incident with at least three distinct open 5-threads where . Let be the neighbor of distinct from . Let be a strong odd 4-coloring of . Take distinct colors not in . If , then extend by coloring with for all . Otherwise, we may assume . By the same argument, we may assume . Now, extend by coloring both with and with a color in . Thus, the strong odd condition holds at . For each , choose a color for not in . By the moreover part of Lemma 3.3, we can extend to a strong odd 4-coloring of , which is a contradiction. □
Lemma 3.7. Let be adjacent vertices of . Suppose that each of is either a 4-vertex with a 1-neighbor or a 3-vertex. Then either contains a 5-cycle or and cannot both be incident with two internally disjoint open - and -threads.
Proof. Assume that has no 5-cycle. Suppose to the contrary that each of is incident with two internally disjoint open - and -threads. By Lemma 3.2, neither nor is incident with a closed thread. For each , let and be the corresponding maximal threads incident with and , respectively, where . For convenience, let and . We call a thread among shared if its terminals are and .
First, suppose that there is a shared thread . Since and has no 5-cycle, . Thus by Lemma 3.4(i). Obtain from by deleting all internal vertices of and the 1-neighbors of , if any. Let be a strong odd 4-coloring of . Let and be the neighbors of and in other than and , respectively. Since , the colors on each of and are pairwise distinct. If , then color with a color not in . Otherwise, , so color both and the 1-neighbor of with . Similarly, color and the 1-neighbor of , if any. Then the strong odd condition holds at , , and . Color with . Since , the strong odd condition holds at . Since and , by the moreover part of Lemma 3.3, we can extend to a strong odd 4-coloring of , a contradiction.
Now, suppose that there is no shared thread. Obtain from by deleting , their 1-neighbors, if any, and the vertices for each . Let be a strong odd 4-coloring of . Color with a color . By Lemma 3.3, extend to , and let . Color with a color . If , then color with a color not in . Otherwise, , so color both and the 1-neighbor of with . In either case, the strong odd condition holds at . By the moreover part of Lemma 3.3, we can extend to . By Lemma 3.3, extend to . If , then color with when , and with a color not in when . Otherwise, color with , and color the 1-neighbor of with when , and with a color not in when . In either case, the strong odd condition holds at . By the moreover part of Lemma 3.3, we can extend to . Thus extends to a strong odd 4-coloring of , which is a contradiction.
Five colors
The results in this subsection will be used for , but we state and prove them for all .
Lemma 3.8. Let . Both terminals of every open 3-thread of are -vertices. In particular, there is no -thread in .
Proof. Suppose to the contrary that there exists a 3-thread with . Let be a strong odd -coloring of . Since , there is a color . Since , there is a color . Color with , respectively, to obtain a strong odd -coloring of , a contradiction.
Lemma 3.9. Let . Suppose two neighbors of a vertex of are on two open 2-threads and . If is not on a closed thread, then at least one of is a -vertex. In particular, every vertex is incident with at most one open 3-thread.
Proof. Suppose to the contrary that both and are -vertices. Let be a strong odd -coloring of . Let . If some is not in , then color with . Otherwise , so has size at most 3. We color with distinct colors , respectively. In either case, the strong odd condition holds at . For each , sequentially color with a color not appearing on , which has size at most . This is a strong odd -coloring of , which is a contradiction.
Lemma 3.10. Let . If , then the neighbors of a -vertex of are not on open -threads and an open -thread.
Proof. Suppose to the contrary that the neighbors of a -vertex are on open 2-threads for and an open 1-thread . Let be a strong odd -coloring of . Since , we can extend to by coloring with a color not in . For , let , so . If have distinct representatives , then color with for each . Otherwise, Hall’s theorem implies that all sets are the same set with elements. This further implies for every . Thus color with and color with distinct colors from . In either case, extends to a strong odd -coloring of , which is a contradiction.
Five colors for sparse graphs
In this section, we prove Theorem 1.2. We begin by summarizing the useful reducible configurations for a strong odd 5-minimal graph from § 3.
Corollary 4.1. A strong odd 5-minimal graph satisfies the following:
(i) Every vertex has at most one 1-neighbor, and the neighbor of a 1-vertex has odd degree at least 5.
(ii) The terminal of a closed thread is a -vertex. Moreover, a 5-vertex with a 1-neighbor is not incident with a closed thread.
(iii) There is no -thread.
(iv) Both terminals of a 3-thread are -vertices. In particular, a 3-vertex is not incident with a 3-thread.
(v) Every vertex is incident with at most one open 3-thread.
(vi) The neighbors of a 3-vertex are not on two open 2-threads and an open 1-thread.
Proof. (i) and (ii) follow from Lemma 3.1 and Lemma 3.2, respectively. (iii) and (iv) follow from Lemma 3.8. (v) and (vi) follow from Lemma 3.9 and Lemma 3.10, respectively.
Now, suppose to the contrary that there exists a graph with that has no strong odd 5-coloring. Choose a strong odd 5-minimal subgraph of . Then is connected and . Moreover, is not a cycle, since every cycle has a strong odd 5-coloring.
Let be the set of 1-vertices of , and let . By Corollary 4.1(i), each vertex in has a -neighbor, so has minimum degree at least 2 and the 2-vertices of are exactly the 2-vertices of . Every -vertex of remains a -vertex in , so the maximal threads containing 2-vertices are unchanged. In particular, every 2-vertex of lies on a maximal thread with -terminals in .
We obtain our final contradiction via discharging. To each vertex of , assign an initial charge of and let denote its final charge after applying the discharging rule. Since the discharging procedure preserves the total charge, we obtain . We will show that the final charge of each vertex is at least , which is a contradiction. The following is the single discharging rule:
(R) Every -vertex sends charge to each nearby 2-vertex
(R1) once if is on a maximal open thread incident with . (R2) twice if is on a closed thread incident with .
Let be a vertex of . If , then is on a maximal thread , so the terminal(s) of sends charge a total of to . Thus, .
Suppose , and let be responsible for nearby 2-vertices. If , then is a 3-vertex of . By Corollary 4.1(ii), is not incident with a closed thread. Moreover, by Corollary 4.1(iv), (v), , so .
If , then is either a 5-vertex of with a 1-neighbor or a 4-vertex of . By Corollary 4.1(ii), is not incident with a closed thread. Moreover, by Corollary 4.1(v), at most one thread incident with is an open 3-thread. Thus , so .
If , then by Corollary 4.1(iii), so .
Hence, every vertex of has final charge at least .
Four colors for sparse graphs without induced 5-cycles
In this section, we prove Theorem 1.3. We first collect the necessary reducible configurations from § 3.
Corollary 5.1. A strong odd 4-minimal graph with no 5-cycle satisfies the following:
(i) Every vertex has at most one 1-neighbor, and the neighbor of a 1-vertex has even degree at least 4.
(ii) Every closed thread has at most three internal vertices, and its terminal is a 4-vertex. Moreover, a 4-vertex with a 1-neighbor is not incident with a closed thread.
(iii) There is no 6-thread.
(iv) If is a 4-vertex with a 1-neighbor or a 3-vertex, then is responsible for at most eight nearby 2-vertices, unless is a 3-vertex and the neighbors of are on maximal 0-, 4-, 5-threads.
(v) Every 4-vertex is responsible for at most 18 nearby 2-vertices.
(vi) Let be the 3-neighbor of a 3-vertex whose other two neighbors are on maximal 4-, 5-threads. If is a 4-vertex with a 1-neighbor or a 3-vertex, then is responsible for at most seven nearby 2-vertices.
Proof. (i), (ii), (iii), (v) follow from Lemma 3.1, Lemma 3.2, Lemma 3.4(i), Lemma 3.6, respectively.
(iv): Let be a 4-vertex with a 1-neighbor or a 3-vertex. By (ii), is not incident with a closed thread. Excluding the possible 1-neighbor of , let denote the number of 2-vertices on the three maximal threads incident with . We may assume . By (iii), , and by Lemma 3.4(ii), (iii), . If , then , with equality only for . If and , then by Lemma 3.5 so . If and , then and by Lemma 3.5, so . Finally, a 4-vertex with a 1-neighbor is not incident with a 5-thread by Lemma 3.4(iii), so only a 3-vertex can be responsible for nine nearby 2-vertices.
(vi): Suppose that satisfy the hypotheses. By (ii), is not incident with a closed thread. Excluding the possible 1-neighbor of , let denote the number of 2-vertices on the three maximal threads incident with . We may assume and . By (iii), . By Lemma 3.7, either or . Thus .
Let be a graph with and no induced 5-cycles. Since a 5-cycle together with a chord has average degree , every 5-cycle in must be induced, so has no 5-cycles. Suppose to the contrary that has no strong odd 4-coloring. Choose a strong odd 4-minimal subgraph of . Then is connected, has no 5-cycles, and . Moreover, is not a cycle, since every cycle other than a 5-cycle has a strong odd 4-coloring.
Let be the set of 1-vertices of , and let . By Corollary 5.1(i), each vertex in has a -neighbor, so has minimum degree at least 2 and the 2-vertices of are exactly the 2-vertices of . Every -vertex of remains a -vertex in , so the maximal threads containing 2-vertices are unchanged. In particular, every 2-vertex of lies on a maximal thread with -terminals in . Every 3-vertex of is either a 4-vertex of with a 1-neighbor or a 3-vertex of . Since the neighbor of a 1-vertex has even degree by Corollary 5.1(i), every 4-vertex of is a 4-vertex of .
Let be the set of 3-vertices of whose three neighbors are on maximal 0-, 4-, 5-threads. By Corollary 5.1(iv), every vertex of is a 3-vertex of . Each vertex of has a unique -neighbor in , which is not in , by Corollary 5.1(vi).
We obtain our final contradiction via discharging. To each vertex of , assign an initial charge of and let denote its final charge after applying the discharging rule. Since the discharging procedure preserves the total charge, we obtain . We will show that the final charge of each vertex is at least , which is a contradiction. We use the following discharging rules:
(R1) Every -vertex sends charge to each nearby 2-vertex
(R1a) once if is on a maximal open thread incident with .
(R1b) twice if is on a closed thread incident with .
(R2) Every -vertex sends charge to each neighbor in .
Let be a vertex of . If , then is on a maximal thread , so the terminal(s) of sends charge a total of to . Thus, . If , then sends charge by (R1) and receives from its unique -neighbor by (R2). Note that has no neighbor in . Hence .
Suppose that and . Let be responsible for nearby 2-vertices, and let be the number of neighbors of in . Note that sends charge . If , then is either a 4-vertex with a 1-neighbor in or a 3-vertex in . Since , we know by Corollary 5.1(iv). If , then by Corollary 5.1(vi). If , then since each neighbor in is a -vertex, by Corollary 5.1(iii). Thus, in every case, so .
If , then by Corollary 5.1(v). If , then by Corollary 5.1(iii). Thus, in every case, so .
If , then Corollary 5.1(iii) gives , so .
Hence, every vertex of has final charge at least .
Asymptotically tight bound
In this section, we prove Theorem 1.1. An orientation of a graph gives a direction to each edge. We use a fact attributed to Hakimi [5]. Let denote the maximum outdegree of an orientation .
Theorem 6.1 ([5]). Let be a graph and let be a nonnegative integer. Then has an orientation with if and only if .
An edge-coloring of a loopless multigraph is odd if, at each vertex, every color appears 0 or an odd number of times on its incident edges. We use the following theorem of Lužar, Petruševski, and Škrekovski [8].
Theorem 6.2 ([8]). Every loopless multigraph has an odd 6-edge-coloring.
We establish the below statement, from which Theorem 1.1 follows.
Proposition 6.3. For , let . If is a graph with , then .
Proof. Let be a graph with . Since , has an orientation with by Theorem 6.1. For each vertex , let and , so and form a partition of . Since , we know and every vertex of belongs to for at most two vertices .
We define two auxiliary simple graphs and on . Let be an edge of , if there is a vertex , called a 1-witness of , such that either or ; namely, a path or exists. We claim , by showing that has an orientation with and applying Theorem 6.1. Indeed, for each edge of , choose a 1-witness and orient as follows: if , and , otherwise. For a vertex , , so .
Next, let be an edge of whenever for some vertex , called a 2-witness of . Since , each vertex of determines at most one edge of , so distinct edges of have distinct 2-witnesses. Let be a nonempty subgraph of with vertices and edges, so its average degree is . For each edge of , choose a 2-witness and let . Since the 2-witnesses are distinct, and , so
Hence , and therefore .
Let . Then
Thus is -degenerate, so it has a proper -coloring . For each , let . Two distinct vertices cannot receive the same color if since , and if since . Therefore, for every vertex and , either , or and . \hfill
For each , we construct a loopless multigraph , whose edges correspond to the vertices of . For every vertex , since , define as follows:
If , then let .
If , then introduce a new vertex and let .
If , then introduce two new vertices and let .
:::♀♀♀♀♀♀ Let be the multigraph with vertex set consisting of together with all newly introduced vertices, and with edge multiset . In particular, is a bijection between and . By construction, for every and , is incident with in if and only if . By Theorem 6.2, the multigraph has an odd 6-edge-coloring .
Finally, we define a -coloring of where . Since is a proper coloring of and is a subgraph of , we know is a proper coloring. We now verify the strong odd condition. Fix and consider a color . If , then by , consists of a single vertex, so appears at most once in . Otherwise, , so . By the construction of , we have
which is or odd since is an odd edge-coloring. Thus is a strong odd coloring of with at most colors.
To prove Theorem 1.1, let , so for ; equivalently, is the positive solution of . Hence, by Proposition 6.3, if , then .
Future directions
We conclude with a potential future research direction. For , let . In other words, is the threshold on the maximum average degree guaranteeing a strong odd -coloring. Theorem 1.2 and the construction of imply . It would be interesting to determine for all .
Problem 7.1. Determine for all .
In particular, we conjecture .
Conjecture 7.2. For a graph , if , then .
The bound on the maximum average degree would be best possible. Let be the graph obtained from two 4-cycles sharing exactly one vertex and adding an edge between the two vertices farthest away from the shared vertex. Then and as all seven vertices must receive distinct colors in every strong odd coloring of .
We remark that Conjecture 7.2 holds for every graph with , as Havet [6] proved that is 6-choosable for every graph with and .
Declaration of LLM use.
The authors acknowledge the use of OpenAI’s ChatGPT, which suggested a connection to odd edge-coloring that was helpful in developing the proof of Theorem 1.1 and provided editorial assistance. The authors independently developed and verified all mathematical arguments, revised the exposition, and take full responsibility for the contents of the article.
References
- [1]Y. Caro, M. Petruševski, R. Škrekovski, and Z. Tuza, On strong odd colorings of graphs, Discrete Math. 348 (2025), no. 11, 114601.arxiv.org/abs/2410.02336
- [2]E.-K. Cho, I. Choi, H. Kwon, and B. Park, Odd coloring of sparse graphs and planar graphs, Discrete Math. 346 (2023), no. 5, 113305.arxiv.org/abs/2202.11267
- [3]D. W. Cranston, Odd colorings of sparse graphs, J. Combin. 15 (2024), no. 4, 439–450.arxiv.org/abs/2201.01455
- [4]M. Goetze, F. Klute, K. Knauer, I. Parada, J. P. Peña, and T. Ueckerdt, Strong odd coloring in minor-closed classes, 2025, Preprint, arXiv:2505.02736 [math.CO].
- [5]S. L. Hakimi, On the degrees of the vertices of a directed graph, J. Frankl. Inst. 279 (1965), no. 4, 290–308.DOI
- [6]F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009), no. 11, 3553–3563.DOI
- [7]H. Kwon and B. Park, Strong odd coloring of sparse graphs, Discrete Math. 349 (2026), no. 11, 115292.arxiv.org/abs/2401.11653
- [8]B. Lužar, M. Petruševski, and R. Škrekovski, Odd edge coloring of graphs, Ars Math. Contemp. 9 (2015), no. 2, 267–277.DOI
- [9]M. Petruševski and R. Škrekovski, Colorings with neighborhood parity condition, Discrete Appl. Math. 321 (2022), 385–391.arxiv.org/abs/2112.13710
- [10]M. Pilipczuk, Strong odd colorings in graph classes of bounded expansion, Electron. J. Combin. 32 (2025), no. 4, P4.14.arxiv.org/abs/2505.15288
- [11]K. Santra, An improved upper bound for the strong odd chromatic number of planar graphs, 2026, Preprint, arXiv:2608.03522 [math.CO].arxiv.org/abs/2608.03522