Monochromatic Graph Decompositions Inspired by Anti-Ramsey Theory and Parity Constraints

Abstract

We open here many new tracks of research in anti-Ramsey Theory, considering edge-coloring problems inspired by rainbow coloring and further by odd colorings and conflict-free colorings. Let G be a graph and $\mathcal{F}$ any given family of graphs. For every integer $n\ge \left|G\right|$, let $f(n,G|\mathcal{F})$ denote the smallest integer k such that any edge coloring of $K_n$ with at least k colors forces a copy of G in which each color class induces a member of $\mathcal{F}$. Observe that in anti-Ramsey problems, each color class is a single edge, i.e., $\mathcal{F}=\left\{K_2\right\}$. Among the many results introduced in this paper, we mention the following. (1) For every graph G, there exists a constant $c=c\left(G\right)$ such that in any edge coloring of $K_n$ with at least $cn$ colors there is a copy of G in which every vertex v is incident with an edge whose color appears only once among all edges incident with v. (2) In sharp contrast to the above result we prove that if $\mathcal{F}$ is the class of all odd graphs (having vertices with odd degrees only) then $f(n,K_k|\mathcal{F})=(1+o\left(1\right))\mathrm{ex}(n,K_{\lceil k/2\rceil })$, which is quadratic for $k\ge 5$. (3) We exactly determine $f(n,G|\mathcal{F})$ for small graphs when $\mathcal{F}$ belongs to several families representing various odd/even coloring constraints.

1. Introduction

In this extensive work, we introduce a large number of new functions related to the Anti-Ramsey/Rainbow Theory of graphs and present a first detailed study of them. In doing, so we continue the approach that we presented in our preceding paper [1]. As a generalization of rainbow coloring, each monochromatic class is allowed to form a graph that belongs to a prescribed family $\mathcal{F}$ of graphs, rather than required to be just a single edge.

In [1], we mainly considered hereditary families of graphs. Here, we focus on families, mostly non-hereditary ones, that have parity conditions imposed on the degrees of the graphs allowed to form the color classes.

1.1. Brief History of Anti-Ramsey Theory

The rainbow coloring or anti-Ramsey theorems date back to the work of Erdős, Simonovits and Sós [2]. The main problem is as follows. Given a graph G, at least how many colors are needed so that every edge coloring of $K_n$ with that many colors forces a copy of G with all edges of it getting distinct colors? This minimum is denoted by $\mathrm{Ar}(n,G)$. The main result of [2] is as follows. Let ${\chi }_e\left(G\right)=min\{\chi (G-e):e\in E\left(G\right)\}$, where $\chi$ denotes the chromatic number. If ${\chi }_e\left(G\right)=k\ge 3$, then $\mathrm{Ar}(n,G)=(1+o\left(1\right))\mathrm{ex}(n,K_k)$, and in particular, $\mathrm{Ar}(n,K_{k+1})=\mathrm{ex}(n,K_k)+2$ for large n, where $\mathrm{ex}(n,G)$ is the famous Turán number. The proof relies heavily on the Erdős–Stone–Simonovits theorem [3,4] that states $\mathrm{ex}(n,G)=(1+o\left(1\right))\mathrm{ex}(n,K_k)$ whenever $\chi \left(G\right)=k\ge 3$. Decades later, the tight formula for $\mathrm{Ar}(n,K_{k+1})$ was extended to all $n\ge k\ge 3$ [5]; moreover $\mathrm{Ar}(n,C_k)$, was determined up to an additive constant [6]. The subject is still very active today; see the survey [7] and some recent papers [8,9,10,11,12,13,14].

Recently, in [1], the authors initiated the study of the following more general problem. Let G be a graph, and let $\mathcal{F}$ any given family of graphs. For every integer $n\ge \left|G\right|$, let $f(n,G|\mathcal{F})$ denote the smallest integer k such that any edge coloring of $K_n$ with at least k colors forces a copy of G in which each color class induces a member of $\mathcal{F}$. Observe that in anti-Ramsey problems, each color class is a single edge; i.e., $\mathcal{F}=\left\{K_2\right\}$. A major result in [1] is as follows. Let $\mathcal{F}$ be a hereditary family, and let ${\chi }_{\mathcal{F}}\left(G\right)=min\{\chi (G-D):D\subset G,D\in \mathcal{F}\}$. If ${\chi }_{\mathcal{F}}\left(G\right)=k\ge 3$; then, $f(n,G|\mathcal{F})=(1+o\left(1\right))\mathrm{ex}(n,K_k)$. Again, a heavy use of the Erdős–Stone–Simonovits theorem is inevitable, together with new tools of interest in their own right, e.g., the “Independent Transversal Lemma” in directed graphs of bounded outdegree. Also, it is proved that if G is stable with respect to $\mathcal{F}$, namely ${\chi }_{\mathcal{F}}\left(G\right)=\chi \left(G\right)=k\ge 3$, then (regardless of whether or not $\mathcal{F}$ is hereditary) $f(n,G|F)=(1+o\left(1\right))\mathrm{ex}(n,K_k)$ is valid. Many examples of interesting and natural hereditary families and the implied results concerning $f(n,G|\mathcal{F})$ or $f(n,K_p|\mathcal{F})$ are given in [1].

Already in [1], we announced that in parallel, we consider other similar problems inspired by odd-coloring and conflict-free coloring, cf. [15,16], respectively, with the several follow-ups and the references therein. This track of research emerged from a conversation with Riste Škrekovski and is also motivated by the famous theorem of Pyber [17] stating that every graph has an edge decomposition into at most four odd subgraphs (and every multigraph without loops into at most six). Anti-Ramsey-type problems related to conflict-free and odd-colorings constitute the main subject of the current paper.

1.2. Hierarchy of Some Basic Invariants Under Parity Constraints

Beside the classical anti-Ramsey numbers $\mathrm{Ar}(n,G)$ we define seven further notions. Their hierarchic relations are exhibited in

Table 1. Hierarchy of eight subclasses of anti-Ramsey colorings; boldface indicates possible quadratic growth, the other two classes are linearly bounded, as we shall see below.

				AR
				⇓
				LR
			⇙		⇘
		SOD				CF
	⇙		⇘		⇙
SP				OD
⇓	⇘
CP		LP

.

Definition 1.

Let ψ be an edge coloring of $K_n$, and let G be a given graph. A subgraph $H\cong G$ of $K_n^{\psi }$, with its edge coloring induced by ψ, is called

• Rainbow if all its edges have mutually distinct colors;
• Proper or local rainbow if it is properly edge-colored;
• Strong-odd-colored, or just strong, if each color class induces an odd graph;
• Odd-colored, or briefly weak (as opposed to “strong”) if at each vertex at least one color occurs on an odd number of edges;
• Conflict-free-colored—Cf-colored for short—if at each vertex at least one color occurs on exactly one edge;
• Strong-parity-colored if all color classes induce odd graphs or all color classes induce even graphs;
• Class-parity-colored if the edges of each color c form either an odd graph or an even graph (but distinct color classes are not required to have the same parity);
• Local-parity-colored if, at each vertex, every incident color class has an odd number of edges or every incident color class has an even number of edges (but for distinct vertices the parity may not be the same).

We denote by $\mathrm{Ar}(n,G)$/$\mathrm{Lr}(n,G)$/$\mathrm{Sod}(n,G)$/$\mathrm{Od}(n,G)$/$\mathrm{Cf}(n,G)$/$\mathrm{Sp}(n,G)$/$\mathrm{Cp}(n,G)$/$\mathrm{Lp}(n,G)$ the smallest m such that, for every ψ with at least m colors, $K_n^{\psi }$ contains a rainbow/proper/strong-odd-colored/odd-colored/Cf-colored/strong-parity-colored/class-parity-colored/local-parity-colored subgraph isomorphic to G, respectively. Where the corresponding coloring types and requirements are concerned, we write fully capitalized AR, LR, SOD, OD, CF, SP, CP, LP.

For easier comparison among the definitions, we include two further tables for different aspects.

Table 2. Conditions for the four local variants of anti-Ramsey functions.

Color Degree	Odd	1
some color	$\mathrm{Od}$	$\mathrm{Cf}$
all colors	$\mathrm{Sod}$	$\mathrm{Lr}$

summarizes the combinations of local conditions assumed for each vertex, from which $\varphi (n,G)$ is derived for the four functions $\varphi \in \{\mathrm{Od},\mathrm{Sod},\mathrm{Cf},\mathrm{Lr}\}$.

Table 3. Global vs. local conditions on anti-Ramsey functions.

Condition	Global	Local	Color Class
rainbow	$\mathrm{Ar}$	$\mathrm{Lr}$	—
same parity	$\mathrm{Sp}$	$\mathrm{Lp}$	$\mathrm{Cp}$

exhibits the differences between assumptions posed globally for all vertices or locally at each vertex, involving the five functions $\varphi \in \{\mathrm{Ar},\mathrm{Lr},\mathrm{Sp},\mathrm{Lp},\mathrm{Cp}\}$.

Representation in Terms of $f(n,G|\mathcal{F})$

Four of the eight functions above, namely $\mathrm{Ar}(n,G)$, $\mathrm{Lr}(n,G)$, $\mathrm{Sod}(n,G)$, and $\mathrm{Cp}(n,G)$, are easily expressible in the form $f(n,G|\mathcal{F})$ where $\mathcal{F}$ is a suitably chosen family of graphs. The reason is that in those cases an edge coloring of any graph satisfies the requirements if and only if each color class has a specified type. In accordance with this principle, two of the anti-Ramsey functions can be characterized by hereditary families:

$$\begin{array}{c}\mathrm{Ar}(n,G)⟶\mathcal{F}=\left\{K_2\right\} \left(\mathrm{single}\mathrm{edge}\right),\\ \mathrm{Lr}(n,G)⟶\mathcal{F}=\{t{K}_2:t\ge 1\}\left(\mathrm{matchings}\right);\end{array}$$

and further, two of them can be characterized by non-hereditary families:

$$\begin{array}{c}\mathrm{Sod}(n,G)⟶\mathrm{family}\mathrm{of}\mathrm{all}\mathrm{odd}\mathrm{graphs},\\ \mathrm{Cp}(n,G)⟶\mathrm{all}\mathrm{odd}\mathrm{graphs}\mathrm{and}\mathrm{all}\mathrm{even}\mathrm{graphs}.\end{array}$$

However, the other four functions, namely $\mathrm{Cf}(n,G)$, $\mathrm{Od}(n,G)$, $\mathrm{Sp}(n,G)$, and $\mathrm{Lp}(n,G)$, are more complicated from this point of view:

• If $E\left(G\right)=E\left(F\right)\cup E\left(M\right)$, where F is an even graph and M is a perfect matching, then assigning color 1 to M and color 2 to F, the obtained coloring of G is both odd and conflict-free. Thus, if the complement of an even graph F contains a perfect matching, then F may occur in a conflict-free (and hence also an odd) coloring as a color class. But the edge-disjoint union of two even graphs F and $F^{\prime }$, one of color 1 and the other of color 2, is never an odd or conflict-free coloring.
• Any even graph and any odd graph may occur in a strong parity coloring as a color class. But the edge-disjoint union of an even graph of color 1 and an odd graph of color 2 is never a strong parity coloring.
• Every graph can occur as a color class in a local parity coloring. But it is absolutely false that any edge-disjoint union of any graphs as color classes yields a local parity coloring.

For this reason, it is very unlikely that any of the functions $\mathrm{Cf}(n,G)$, $\mathrm{Od}(n,G)$, $\mathrm{Sp}(n,G)$, or $\mathrm{Lp}(n,G)$ coincides with a function $f(n,G|\mathcal{F})$ for all graphs G and all integers $n\ge \left|G\right|$.

1.3. Summary of Results and Structure of the Paper

At the beginning of this extensive work, we give some information with the intention of orienting the reader concerning the arrangement of the material. First, we describe the flavor of the various sections and then give a brief list of a few representative results.

1.3.1. Basic Structure

General definitions are given in the next subsection.

Section 2 mostly deals with types of edge colorings from which one can derive constructive lower bounds on the considered anti-Ramsey functions. In further subsections, inequalities between those functions are given, the effects of some elementary graph operations are investigated, and it is shown that the functions may perform big jumps when an edge is inserted or deleted.

Section 3 presents results in which the key role is played by vertex degrees. After some general inequalities, the section continues with the study of the anti-Ramsey functions on stars of any degree and on stars supplied with a further pendant edge. Then, a subsection investigates graphs in which the degrees of all vertices have the same parity. Finally, two types of vertex orders defined in terms of parity constraints are introduced, and their influence on the considered functions is analyzed.

Section 4 studies conflict-free colorings and weak odd colorings; the behavior of these two differs substantially from that of the other six types.

Section 5 begins with general estimates of paths and cycles. After that, the bulk of the section is a systematic study of all the considered functions on all graphs with at most four edges or at most four vertices.

Section 6 concludes the paper with a collection of open problems. They are organized into five thematic subsections, arranged according to the nature of the problems.

1.3.2. Selected Results

We first emphasize the heavy use of the Erdős–Rado canonical coloring theorem (Theorem 1) in many results in this paper. It seems that this theorem was used only rarely in anti-Ramsey theory previously (see, e.g., [18]), while in the present paper, introducing the parity-dependent anti-Ramsey parameters, it has become rather useful.

In Section 2, we choose to state the following theorem, showing that six of the eight parameters have quadratic growth in n, as indicated in the hierarchy presented in Table 1. For comparison, we recall the tight formula $\mathrm{Ar}(n,K_p)=\mathrm{ex}(n,K_{p-1})+2$ for $p\ge 4$, proved in [5], that has a leading coefficient substantially larger than the one below.

Theorem 2: for every $p\ge 5$, all of $\mathrm{Lr}(n,K_p)$, $\mathrm{Sod}(n,K_p)$, $\mathrm{Sp}(n,K_p)$, $\mathrm{Cp}(n,K_p)$, $\mathrm{Lp}(n,K_p)$ are asymptotically equal to $(1+o\left(1\right))\mathrm{ex}(n,K_{\lceil p/2\rceil })$.

In Section 3, we choose a theorem that dictates the values for stars whenever n is not too small.

Theorem 3: For $n\ge 2r$ we have $\mathrm{Sod}(n,K_{1,r})=1$ if $r\equiv 1$ (mod 2), and $\mathrm{Sod}(n,K_{1,r})=2$ if $r\equiv 0$ (mod 2). Moreover, the condition $n\ge 2r$ is tight in both cases.

Another result from Section 3 shows a dichotomy in the behavior of three parameters:

Theorem 6: If all vertices have an odd degree in G, then either all of $\mathrm{Sod}(n,G)$, $\mathrm{Sp}(n,G)$, $\mathrm{Lp}(n,G)$ tend to infinity with n, or all are equal to 1 for every n sufficiently large.

A major theorem of Section 4, completing the support of Table 1 in the branch of linear growth, is

Theorem 11: If G is a graph on p non-isolated vertices; then, $\mathrm{Od}(n,G)\le \mathrm{Cf}(n,G)\le (p-2)n-\lfloor p^2/2\rfloor +p+1$.

In Section 5, we mostly deal with small graphs up to four edges, as well as the graphs $P_6$, $K_4-e$, and $K_4$. These results are summarized in Table 5 on page 13. For $P_6$ and all graphs with at most four edges, we have exactly determined the values of all the newly introduced parameters. However, several cases are left open regarding $K_4-e$ and $K_4$. Yet we mention here one result concerning $K_4$ where the order of growth is determined.

Theorem 26: We have $\mathrm{Lr}(n,K_4)=\mathrm{\Theta }\left(n^{3/2}\right)$ as $n\to \infty$.

Lastly, it is inevitable that from such a collection of parameters, lots of new problems will emerge. Section 6 collects many of them for future research.

1.4. Standard Definitions and Notation

Throughout the paper, we consider simple undirected graphs G, without loops and multiple edges, with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. We write $\left|G\right|$ for the order $\left|V\right(G\left)\right|$ of G. The degree of vertex v in graph G is denoted by $d_G\left(v\right)$, abbreviated as $d\left(v\right)$ when G is understood. Also, as usual, $\delta \left(G\right)$ and $\mathrm{\Delta }\left(G\right)$ denote the minimum and maximum degrees in G, respectively.

We say that G is an odd graph if the degree of all its vertices is odd and G is an even graph if all vertex degrees in G are even.

Particular types of graphs are the path $P_n$, the cycle $C_n$, and the complete graph $K_n$, each of order n, and the complete bipartite graph $K_{p,q}$ with p and q vertices in its partite sets. Where a considered edge coloring $\psi$ of $K_n$ has to be emphasized, we write $K_n^{\psi }$.

Some important graph operations are edge insertion $G+e$ (with $e\subset V\left(G\right)$ and $e\notin E\left(G\right)$), edge deletion $G-e$ (with $e\in E\left(G\right)$), and the vertex-disjoint union $G_1\cup G_2$ of two graphs $G_1$ and $G_2$. The vertex-disjoint union of t copies of G is denoted as $tG$.

A famous extremal graph-theoretic function of great importance in the current context is the Turán number $\mathrm{ex}(n,F)$ of a “forbidden graph” F. It is defined as the maximum number of edges in a graph of order n that contains no subgraph isomorphic to F.

2. Basic Coloring Patterns, General Inequalities, and Graph Operations

In this section, we present three kinds of material. The first part describes explicit constructions of coloring patterns that can be used for lower bounds on anti-Ramsey numbers. The second part deals with inequalities based on hierarchy among notions and simple structural observations. The third part discusses the effect of some operations that simplify the determination of anti-Ramsey parameters, pointing out reducibility relations among them.

2.1. Coloring Patterns

Let us categorize the edge coloring patterns of $K_n$ below into two major types: homogeneous and compound.

Homogeneous ones are fundamental and will be useful in proving upper bounds on several anti-Ramsey functions under study. On the other hand, the various constructions of compound patterns are tools for proving lower bounds. Already after the definitions, we will indicate several ways they can be used in that direction.

2.2. Homogeneous Coloring Patterns

The three fundamental types of homogeneous coloring patterns are as follows.

• Monochromatic—all edges of $K_n$ are assigned with the same color;
• Rainbow—each edge of $K_n$ has its private color, distinct from all the colors of the other edges;
• LEX coloring—labeling the vertices of $K_n$ as $v_1,v_2,\dots ,v_n$, for all $1\le i<j\le n$, the edge $v_i{v}_j$ is assigned color $j-1$.

Hence, the classical LEX coloring of $K_n$ assumes a sequential order on the vertex set, and partitions the edge set into $n-1$ color classes, which are stars. (In some papers LEX is also termed UMIC as an abbreviation for Universal Majority Index Coloring, but throughout this work we use the more standard name LEX).

The following important Ramsey-type result connects the above three coloring patterns.

Theorem 1

(Erdős–Rado Canonical Theorem [19]). For every $k\ge 3$, there exists an integer $n_0\left(k\right)$ such that, for every $n\ge n_0\left(k\right)$, in every edge coloring of $K_n$, some k vertices induce a copy of $K_k$, which is either monochromatic or rainbow or LEX-colored.

2.3. Compound Coloring Patterns

The three basic patterns introduced above can be combined with each other in many ways; here, we describe some of those possibilities. The ones used below are collected in

Table 4. Compound coloring patterns where the number of colors grows as a function of n.

Pattern Combination	Applied First in
rainbow $K_p$, monochromatic $K_n-K_p$	Proposition 4
h-LEX, rainbow $K_h$ followed by LEX	Theorem 7
h-RS, rainbow $K_n-K_{n-h}$, monochromatic $K_{n-h}$	Theorem 12
LEX with rainbow perfect matching	Theorem 23
rainbow spanning graph, monochromatic complement	Theorem 26
LEX with rainbow spanning star	Theorem 27

, the others partly provide tools for lower bounds in [1] and can be partly applied to improve estimates that are asymptotically tight but for which better error terms can be achieved.

2.3.1. Generalizations of LEX Coloring

Recall that LEX assumes a sequential order $v_1,v_2,\dots ,v_n$ on the vertices of $K_n$. We generalize LEX to a pattern with two parameters.

Let $k\ge 1$ and $h\ge k+1$. Compose the coloring (k,h)-LEX as follows.

• For each $j=h+1,\dots ,n$ and all $k\le l<j$, assign the color $\psi \left(v_l{v}_j\right)=j-h$. Those colors range from 1 to $n-h$.
• For each $j=h+1,\dots ,n$ and each $1\le l<k$, assign a private color $\psi \left(v_l{v}_j\right)$, ranging from $n-h+1$ to $(n-h)k$. (This step is void if $k=1$).
• Take a rainbow $K_h$ on the vertices $v_1,\dots ,v_h$ using the colors $(n-h)k+1,\dots ,(n-h)k+h(h-1)/2$.

Here, LEX is obtained by putting $k=1$ and $h=1$ or $h=2$. Fixing $k=1$, the intermediate one-parameter case with $h>2$, termed h-LEX, is also of interest; the number of colors in that pattern is

$$\mathrm{Lex}(n,h):=\mathrm{Lex}(n,1,h)=n-h+h(h-1)/2=n+h(h-3)/2.$$

In general, the number of colors is

$$\mathrm{Lex}(n,k,h)=(n-h)k+h(h-1)/2.$$

Application 1.

If $\left|G\right|=h+1$ and $\delta \left(G\right)=k+1$, then

$$\mathrm{Lr}(n,G)\ge \mathrm{Lex}(n,k,h)+1=(n-h)k+h(h-1)/2+1.$$

Indeed, taking $K_n^{\psi }$ with the (k,h)-LEX coloring, in any copy of G, the vertex $v_j$ with highest index satisfies $j>h$; therefore, only k colors occur on the edges from $v_j$ to its neighbors (all with smaller indices), but $d\left(v_j\right)\ge k+1$; hence, some colors appear at least twice at $v_j$, so the coloring of G cannot be proper. This coloring sometimes provides a useful lower bound when $\chi \left(G\right)\le 4$, as $\mathrm{Lr}(n,G)$ is determined by the hereditary family $\mathcal{F}=\{t{K}_2:t\ge 1\}$ and in view of the results presented in the introduction from [1].

2.3.2. Split Coloring Combined with LEX

We present here two variants. Their common feature is that the vertex set of $K_n$ is split into two parts, $V\left(K_n\right)=A\cup B$, where $\left|A\right|=k$; and $\left|B\right|=n-k$ for a given $k\ge 1$, and

• On the edges of the clique on A and all edges from A to B, all colors are distinct.

(i)

In the coloring k-RS (k-rainbow split graph coloring)

• One extra color is used on all the other edges, to make the clique on B monochromatic.

The number of colors used is

$$s(n,k)=k(n-k)+\left({\displaystyle \genfrac{}{}{0pt}{}{k}{2}}\right)+1=kn-\left({\displaystyle \genfrac{}{}{0pt}{}{k+1}{2}}\right)+1.$$

Application 2.

If $\delta \left(G\right)\ge k+2$, then

$$\mathrm{Lr}(n,G)\ge s(n,k)+1=kn-\left({\displaystyle \genfrac{}{}{0pt}{}{k+1}{2}}\right)+2$$

because any copy of G has a vertex v in B, which is incident with no more than k distinct colors toward A and just one color in B; hence, at least two edges of v must have the same color inside B. Consequently, G is not properly colored under k-RS. This coloring is sometimes useful for lower bounds when $\chi \left(G\right)\le 4$.

(ii)

In the Split-Lex coloring pattern SPLC, we again take the rainbow set of all edges meeting A, and

• Apply the (t,h)-LEX coloring inside B.

The number of colors used is

$$\begin{array}{ccc}\hfill s(n,k,t,h)& =& s(n,k)-1+\mathrm{Lex}(n-k,t,h)\hfill \\ & =& k(n-k)+\left({\displaystyle \genfrac{}{}{0pt}{}{k}{2}}\right)+(n-k-h)t+\left({\displaystyle \genfrac{}{}{0pt}{}{h}{2}}\right).\hfill \end{array}$$

Already, the very particular case $k=t=1$, $h=2$ (rainbow spanning star and LEX on its leaves) with $s(n,k,t,h)=2n-3$ is of interest.

Application 3.

This pattern provides the currently best known lower bound on the strong odd anti-Ramsey number of $K_4$; that is, $\mathrm{Sod}(n,K_4)\ge 2n-2$.

2.3.3. Clique Coloring

Let $k\ge 2$ be given. To obtain the k-Clique coloring pattern k-CC, we write n in the form $n=qk+r$, and partition the vertex set of $K_n$ as $V\left(K_n\right)=A_0\cup A_1\cup \dots \cup A_q$, where $|A_0|=r<k$ (possibly $A_0=⌀$) and $|A_1|=\dots =|A_q|=k$.

• Inside every $A_i$ ($i=0,1,\dots ,q$) let the complete subgraph obrtain the rainbow coloring, with each color appearing in just one $A_i$.
• Assign a fresh new color to all other edges to make a monochromatic complete multipartite graph.

The number of colors used is

$$q(n,k)=(n-r)(k-1)/2+\left({\displaystyle \genfrac{}{}{0pt}{}{r}{2}}\right)+1.$$

Application 4.

This coloring is sometimes useful in giving lower bounds when $\chi \left(G\right)\le 4$, and also can be applied to derive a lower bound on $\mathrm{Lr}(n,G)$ in terms of maximum degree; cf. Proposition 3.

2.3.4. Rainbow Multipartite Coloring

Let $k\ge 2$ be given. We present two versions of a pattern, a simpler and a more involved one. For both of them, we take a balanced k-partition of the vertex set, $V\left(K_n\right)=A_1\cup \dots \cup A_k$ with $\lfloor n/k\rfloor \le |A_i|\le \lceil n/k\rceil$ for all $1\le i\le k$.

• Assign mutually distinct colors to all edges between distinct parts $A_i,A_j$.

(i)

In the simpler form, k-RUM coloring,

• Apply LEX inside each $A_i$ no color appearing in more than one part.

The balanced multipartite graph uses $\mathrm{ex}(n,K_{k+1})$ colors, and inside each part $A_i$ the number of colors is $|A_i|-1$. Hence, the total number of colors is

$$r(n,k)=n-k+\mathrm{ex}(n,K_{k+1}).$$

Application 5.

This construction yields a quadratic lower bound on all boldface functions as indicated in Table 1. More explicitly, the following asymptotics can be proved for five of the six functions; the exception is $\mathrm{Ar}(n,K_p)$, whose behavior is substantially different as proved in [2].

Theorem 2.

For every $p\ge 5$, all of $\mathrm{Lp}(n,K_p)$, $\mathrm{Cp}(n,K_p)$, $\mathrm{Sp}(n,K_p)$, $\mathrm{Sod}(n,K_p)$, $\mathrm{Lr}(n,K_p)$ are asymptotically equal to $(1+o\left(1\right))\mathrm{ex}(n,K_{\lceil p/2\rceil })$.

Proof. 

Consider the (⌈p/2⌉–1)-RUM coloring on $K_n$, which uses $\mathrm{ex}(n,K_{\lceil p/2\rceil })+n-\lceil p/2\rceil +1$ colors. Then any subgraph $K\cong K_p$ of $K_n$ contains at least three vertices in some $A_i$. In the LEX ordering, the edges from the third vertex to the first and second vertices form a color class $P_3$; moreover, from the third vertex, there is an edge either to another $A_j$ or a vertex of a higher index inside $A_i$. The monochromatic $P_3$ is not allowed in a class parity coloring, and the presence of degrees 1 and 2 simultaneously at a vertex is not allowed in a local parity coloring. This yields the lower bound $\mathrm{ex}(n,K_{\lceil p/2\rceil })+n-\lceil p/2\rceil +1$ for all the five functions under consideration, because $\mathrm{Cp}$ and $\mathrm{Lp}$ are lower bounds on all of $\mathrm{Sp}$, $\mathrm{Sod}$, and $\mathrm{Lr}$.

The matching asymptotic upper bound for $\mathrm{Lr}(n,K_p)$ holds by Theorem 5.2 (i) of [1], and it dominates the other four functions involved in the assertion. □

Beyond the present setting, this pattern is among the few standard colorings that are heavily used in our paper [20] where we consider the problem of determining $f(n,G|\mathcal{F})$ in full generality. The families $\mathcal{F}$ are not required to be hereditary, nor do they have any relation to odd-coloring or conflict-free coloring.

(ii)

In the more complex form, rainbow coloring is combined with the generalization of LEX:

• Apply (t,h)-LEX inside each $A_i$, no color appearing in more than one part.

Disregarding small deviation due to integer parts, the number of colors is approximately

$$r(n,k,t,h)=\mathrm{ex}(n,K_{k+1})+k\mathrm{Lex}(n/k,t,h)=\mathrm{ex}(n,K_{k+1})+k((n/k-h)t+h(h-1)/2)$$

which means a somewhat larger linear addition in the number of colors to $\mathrm{ex}(n,K_{k+1})$.

Application 6.

Concerning $\mathrm{Lr}(n,G)$ it can be shown that this coloring pattern gives better lower bounds than the simpler version. A small example is $G=K_{2,2,2,2,2}$, and in general, one can consider, e.g., the complete p-partite graphs $K_{p\ast t}=K_{t,\dots ,t}$, where $p\ge 5$ and t is sufficiently large with respect to p. Although the asymptotics $\mathrm{Lr}(n,K_{p\ast t})=(1+o\left(1\right))\mathrm{ex}(n,K_{\lceil p/2\rceil })$ are well determined, this improvement may be relevant when exact results are concerned.

2.4. Inequalities Between Anti-Ramsey Functions

Some basic relations among the five functions not involving “modulo 2” constraints are collected next.

Observation 1.

For any graph G and any $n\ge \left|G\right|$ we have

1. 

$\mathrm{Od}(n,G)\le \mathrm{Sod}(n,G)\le \mathrm{Lr}(n,G)\le \mathrm{Ar}(n,G)$;

2. 

$\mathrm{Od}(n,G)\le \mathrm{Cf}(n,G)\le \mathrm{Lr}(n,G)\le \mathrm{Ar}(n,G)$;

3. 

The equalities $\mathrm{Od}(n,G)=\mathrm{Sod}(n,G)=\mathrm{Cf}(n,G)=\mathrm{Lr}(n,G)$ are valid whenever G has maximum degree at most 2.

Concerning anti-Ramsey functions involving parity, the following facts are valid.

Proposition 1.

Let G be any graph, and $n\ge \left|G\right|$.

1. 

For every G, we have $\mathrm{Sod}(n,G)\ge \mathrm{Sp}(n,G)$, $\mathrm{Sp}(n,G)\ge \mathrm{Lp}(n,G)$ and $\mathrm{Sp}(n,G)\ge \mathrm{Cp}(n,G)$.

2. 

If there is a vertex of odd degree in G, then $\mathrm{Sp}(n,G)=\mathrm{Sod}(n,G)$; if G is an odd graph, then $\mathrm{Lp}(n,G)=\mathrm{Sp}(n,G)=\mathrm{Sod}(n,G)$.

3. 

If G has a component H with all degrees even, then $\mathrm{Sp}(n,G)\ge \mathrm{Cp}(n,G)\ge n$ is forced by LEX for $H=C_3$ and $\mathrm{Sp}(n,G)\ge \mathrm{Cp}(n,G)\ge n+1$ by 3-LEX for any other H.

4. 

If $\mathrm{\Delta }\left(G\right)\le 2$, then $\mathrm{Lp}(n,G)=1$.

5. 

If G is a linear forest (i.e., contains no cycles and $\mathrm{\Delta }\left(G\right)\le 2$), then $\mathrm{Lr}(n,G)=\mathrm{Cf}(n,G)=\mathrm{Od}(n,G)=\mathrm{Sod}(n,G)=\mathrm{Sp}(n,G)=\mathrm{Cp}(n,G)$.

6. 

The $\mathrm{Lp}$ condition is satisfied by every monochromatic graph and also by every rainbow graph.

Proof. 

1.

Strong odd coloring is the restricted version of strong parity coloring where even degrees are not allowed in any color class. On the other hand, as compared to strong parity coloring, the color classes in a class parity coloring may mix odd graphs and even graphs, whereas in local parity coloring, graphs are also allowed to be color classes that contain vertices with degrees from both parities.

2.

At an odd-degree vertex, at least one color occurs an odd number of times, in any edge coloring. This forces all colors to have odd degrees at all vertices, in every strong parity coloring. In a general graph, the parity may vary vertex by vertex, but in odd graphs, all parities must be odd; hence, the difference between local parity and strong parity disappears.

3.

In LEX, using $n-1$ colors, the three edges of every triangle have exactly two colors that do not occur anywhere else in G that is not a class parity coloring.

The pattern 3-LEX uses n colors. If the component H of G is an even graph other than $C_3$, then necessarily, $\left|H\right|>3$. Thus, in any copy of G, the edges at the vertex of the highest index in H form a monochromatic star of even degree, which is not allowed in a class parity coloring.

4.

The edges at a vertex of degree 2 either are monochromatic or have a color distribution $1+1$. Both cases are allowed in local parity coloring.

5.

All six parameters listed in the assertion require that the color class present at a vertex of degree 1 be a single edge. Induction yields that every allowed coloring of G is a proper edge coloring.

6.

Either there is only one color class at a vertex—having degree parity $d\left(v\right)$ mod 2—or all colors present at v occur just once, and thus, all are odd.

□

2.5. Effect of Graph Operations

Based on the principle behind Part 3 of Observation 1, the following further inequalities can be derived.

Proposition 2

(Adding Edge Lemma).

$\left(i\right)$

Let $v,w$ be nonadjacent vertices of even degrees in a graph G, and let $G^{+}$ be the graph obtained from G by inserting the new edge $vw$. Then $\mathrm{Od}(n,G^{+})\le \mathrm{Od}(n,G)$.

$\left(ii\right)$

If G is a spanning subgraph of a graph H, and for every vertex v either $d_H\left(v\right)=d_G\left(v\right)$ or $d_H\left(v\right)$ is odd, then $\mathrm{Od}(n,H)\le \mathrm{Od}(n,G)$. In particular, if $\mathrm{\Delta }\left(H\right)=2k+1$ and $\delta \left(H\right)\ge 2k-1$, and each vertex of degree $2k-1$ in G has degree $2k-1$ or $2k+1$ in H, then $\mathrm{Od}(n,H)\le \mathrm{Od}(n,G)$.

$\left(iii\right)$

Let $v,w$ be nonadjacent vertices of degree 2 in a graph G, and let $G^{+}$ be the graph obtained from G by inserting the new edge $vw$. Then $\mathrm{Cf}(n,G^{+})\le \mathrm{Cf}(n,G)$.

Proof. 

For $\varphi =\mathrm{Od}$ in (i)–(ii) and $\varphi =\mathrm{Cf}$ in (iii), we consider any edge coloring $\psi$ of $K_n$ with at least $\varphi (n,G)$ colors.

(i)

By assumption, a weak copy of G exists under $\psi$. No matter what the color of $\psi \left(vw\right)$ is, after the insertion of edge $vw$, the degrees of v and w become odd, and by parity, an odd color must occur at each of them in $G^{+}$.

(ii)

Also, here, a weak copy of G exists under $\psi$. Let $\psi$ be a coloring realizing $\mathrm{Od}(n,G)$, and consider H. A vertex of even degree in H remains with the original coloring and has at least two odd colors. A vertex of odd degree in H must have an incident odd-degree color by parity.

(iii)

In a Cf-colored graph $H\subset K_n^{\psi }$, $H\cong G$, both v and w in H are incident with two distinct colors. Inserting the edge $vw$, the color distributions at v and w are modified from $1+1$ to $1+2$ or $1+1+1$, both satisfying the requirements for $H^{+}\cong G^{+}$ to be a Cf-colored graph.

□

2.6. Large Jumps When Adding/Deleting Edges

Here, we list some examples illustrating the possible effects of edge insertion, causing large jumps in most of the parameters, or being non-monotone as in the second variable of $\mathrm{Od}(n,G)$ even on graphs with $\mathrm{\Delta }\left(G\right)\le 2$ (cf. Proposition 2).

1.

The sequence $P_4⟶C_4⟶K_4-e⟶K_4$ obtained by inserting edges between vertices of degree at most 2 has $\mathrm{Od}(n,P_4)=3$, $\mathrm{Od}(n,C_4)=n+1$, $\mathrm{Od}(n,K_4-e)=3$, $\mathrm{Od}(n,K_4)=1$. Hence, any large increase and any large decrease can occur, even of linear order, despite the fact that $\mathrm{Od}(n,G)$ is linear for every graph G.

In comparison, the same sequence of graphs yields the following spectacular increase in the growth orders in n for $\mathrm{Ar}(n,G)$, which is clearly monotone in terms of G:

$$\mathrm{constant}\to \mathrm{linear}\to \mathrm{of} \mathrm{order} n^{3/2}\to \mathrm{quadratic}$$

.

2.

For cycles of even length k, we know from Theorem 12 that $\mathrm{Od}(n,C_k)$ grows with $\lfloor (k-1)/3\rfloor n$ at least. However, by inserting a perfect matching M, we obtain an odd graph (more explicitly 3-regular) that has $\mathrm{Od}=1$. It follows that by inserting the edges of M one by one, if $k\equiv 4\left(\mathrm{mod}6\right)$, the average fall of $\mathrm{Od}$ per insertion can be estimated with nearly $2n/3$ from below. The worst case of decrease during the insertion of a single edge (between two vertices of degree 2, and also between any two vertices) is currently not known.

3.

From the results of [1], we know that $\mathrm{Lr}(n,K_5-P_3)=o\left(n^2\right)$, caused by the fact that there is a way to omit $2K_2$ from $K_5-P_3$ to obtain the bipartite graph $K_{2,3}$. On the other hand, $\mathrm{Lr}(n,K_5-e)=(1+o\left(1\right))\mathrm{ex}(n,K_3)$ because $K_3\subset (K_5-e)-2K_2$, no matter how the removal of $2K_2$ is performed. Hence, the insertion of a new edge into $K_5-P_3$ makes $\mathrm{Lr}$ jump from subquadratic to quadratic.

4.

The parameters $\varphi (n,C_5)$ are linear in n for all eight functions $\varphi \in \{\mathrm{Ar}$, $\mathrm{Lr}$, $\mathrm{Sod}$, $\mathrm{Sp}$, $\mathrm{Cp}$, $\mathrm{Lp}$, $\mathrm{Cf}$, $\mathrm{Od}\}$, and $\varphi (n,K_5)$ is quadratic for six of them, except for $\mathrm{Cf}$ and $\mathrm{Od}$. Hence, when inserting edges one by one to reach $K_5$ from $C_5$, interesting jumps occur in those functions.

3. Vertex Degrees

3.1. Some General Inequalities

Proposition 3.

Let G be a graph with maximum degree $\mathrm{\Delta }=\mathrm{\Delta }\left(G\right)$. Suppose $n\equiv r(\mathrm{mod}\mathrm{\Delta }-1)$. Then $\mathrm{Lr}(n,G)\ge q(n,\mathrm{\Delta }-1)+1=(n-r)(\mathrm{\Delta }-2)/2+\left({\displaystyle \genfrac{}{}{0pt}{}{r}{2}}\right)+2$.

Proof. 

Consider $(\mathrm{\Delta }-1)$-Clique coloring of $K_n$, with $q(n,\mathrm{\Delta }-1)$ colors. A vertex v of degree $\mathrm{\Delta }$ in any copy of G can obtain only $\mathrm{\Delta }-2$ distinct colors in a rainbow $K_{\mathrm{\Delta }-1}$, so at least two edges of the same extra color must be incident with v, and therefore, no properly colored G occurs. □

Proposition 4.

If the number of vertices with positive even degrees is $s>0$ in a graph G, then $\left({\displaystyle \genfrac{}{}{0pt}{}{s-1}{2}}\right)+2$ is a lower bound on all of $\mathrm{Ar}(n,G)$, $\mathrm{Lr}(n,G)$, $\mathrm{Cf}(n,G)$, $\mathrm{Sod}(n,G)$, and $\mathrm{Od}(n,G)$.

Proof. 

Based on Observation 1, we only have to prove $\mathrm{Od}(n,G)\ge \left({\displaystyle \genfrac{}{}{0pt}{}{s-1}{2}}\right)+2$. Inside $K_n$, take a rainbow $K_{s-1}$ and make $K_n-K_{s-1}$ monochromatic in a new color. At least one of the even-degree vertices belongs to $V\left(K_n\right)\setminus V\left(K_{s-1}\right)$, and its incident edges form a monochromatic star. Hence, this coloring with $\left({\displaystyle \genfrac{}{}{0pt}{}{s-1}{2}}\right)+1$ colors does not admit any odd-colored copy of G. □

It will be shown in Section 3.4 that a substantial improvement can be given if all vertices have even degrees.

3.2. Stars

For stars we can present tight results under the assumption that the number n of vertices is not very small. In the next theorem we do not make efforts to optimize the bound on n.

Theorem 3.

$\left(i\right)$

If $r\equiv 1$ (mod 2)and $n\ge 2r$, then $\mathrm{Sod}(n,K_{1,r})=1$.

$\left(ii\right)$

If $r\equiv 0$ (mod 2)and $n\ge 2r$, then $\mathrm{Sod}(n,K_{1,r})=2$.

Moreover, the condition $n\ge 2r$ is tight in both cases.

Proof. 

If $n=2r-1$, then we can decompose $K_n$ into $r-1$ Hamiltonian cycles as color classes. Under this coloring, a strong-odd-colored $K_{1,r}$ does not occur because only one edge can be selected from each color. Hence, it is necessary to assume that $n\ge 2r$.

If r is odd, then $K_{1,r}$ is an odd graph, and the monochromatic $K_n$ contains it for any $n\ge r+1$. If r is even, then $K_{1,r}$ itself is not allowed to be a color class in a strong odd coloring, so $\mathrm{Sod}(n,K_{1,r})>1$. So, from now on, we may restrict ourselves to colorings that use at least two colors.

If $n\ge 2r$, consider any non-monochromatic coloring of $K_n$. Choose a vertex v whose incident edges are also non-monochromatic. If some color occurs at least r times at v, then we find monochromatic $k_{1,r}$ if r is odd, or monochromatic $k_{1,r-1}$ with a further edge from another color class if r is even, and the proof is complete.

Otherwise, select a star S with any $2r-1$ edges at v. Assume that color i has $d_i$ edges in S, where the degrees $d_1\ge d_2\ge \dots$ are in decreasing order (re-indexed if necessary). Denote by k the number of colors in S; we certainly have $k\ge 2$, because $d_1<r$. We may assume $k<r$ (otherwise, a rainbow $K_{1,r}$ is present, and we have nothing to prove). This assumption implies $d_1\ge 3$.

If $k\equiv r$ (mod 2), then we select one edge from each of the k color classes, and sequentially supplement them with monochromatic pairs of edges, until at most one unselected edge remains in each class. The process stops when $d_i$ or $d_i-1$ edges of color i are selected, whichever is odd; in either case, it means at least $d_i/2$ edges, and in fact at least ${\displaystyle \frac{3}{4}}{d}_i$ unless $d_i=2$. Thus, the number of selected edges is not smaller than $\lceil (d_1+\dots +d_k)/2\rceil =\lceil (2r-1)/2\rceil =r$, and there is an intermediate step with exactly r edges. In that moment, a strong-odd-colored $K_{1,r}$ is obtained.

If $k\not\equiv r$ (mod 2), we cannot use all colors; we then perform the above selection in the first $k-1$ colors.

The case $k=2$ forces r to be odd. Then, a $K_{1,r}$ in color 1 is present, because $d_1\ge \lceil (d_1+d_2)/2\rceil =\lceil (2r-1)/2\rceil =r$.

If $k\ge 3$, recall that $d_1\ge 3$, and at least $max(3,d_i-1)\ge max(3,\lceil {\displaystyle \frac{3}{4}}{d}_i\rceil )$ edges can be selected from each color class $i<k$ of size $d_i\ge 3$ (and one edge if $d_i=2$). If $d_k\le 2$, we have $max(3,d_i-1)\ge (d_1+d_k)/2$, so eventually, at least half of the $2r-1$ edges will be selected. And if $d_k\ge 3$, then $d_1+d_2\ge {\displaystyle \frac{2}{3}}(d_1+d_2+d_k)$; moreover all $d_i$ are at least 3. Thus, we can apply ${\displaystyle \frac{3}{4}}(d_1+d_2)\ge {\displaystyle \frac{1}{2}}(d_1+d_2+d_k)$, completing the proof. □

Corollary 1.

$\mathrm{Od}(n,K_{1,r})=\mathrm{Sod}(n,K_{1,r})$ for $n\ge 2r$.

Proof. 

Clearly, $1\le \mathrm{Od}(n,K_{1,r})\le \mathrm{Sod}(n,K_{1,r})$. Hence, any coloring satisfies the requirements for both parameters if r is odd. If r is even, we also have $\mathrm{Od}(n,K_{1,r})\ge 2$, which matches the upper bound. □

Theorem 4.

If $r\ge 3$ and $n\ge 2r-2$, then $\mathrm{Cf}(n,K_{1,r})=2$. Moreover, the condition $n\ge 2r-2$ is the best possible.

Proof. 

Clearly, we need at least two colors at the center of the star. Consider any non-monochromatic coloring of $K_n$, and let v be a vertex incident with at least two colors. The degree of v is at least $2r-3$, hence, omitting the smallest color class at v, there remain at least $r-1$ edges. Thus, we can take $r-1$ of them together with one edge from the smallest color class and obtain a Cf-colored $K_{1,r}$.

For $n=2r-3$, the degree is $2r-4$ and we can color the edges with two colors such that each color class is an $(r-2)$-regular spanning subgraph of $K_n$. Then, any r edges at any vertex contain more than one edge from each color; hence, no Cf-colored $K_{1,r}$ occurs. □

3.3. Shortest Brooms

We denote by $K_{1,k}^{+}$ the tree obtained from the star $K_{1,k}$ by attaching a pendant edge to one of its leaves. It is the same as the double star $D_{1,k-1}$, whose two central vertices have degrees of 2 and k, respectively; it is a caterpillar and can also be viewed as the broom graph obtained by identifying the central vertex of $K_{1,k-1}$ with an end of the path $P_3$.

Before turning to this graph, let us mention that the anti-Ramsey number of stars with $k\ge 3$ edges was determined in [21,22,23] as

$$\mathrm{Ar}(n,K_{1,k})=\lfloor n(k-2)/2\rfloor +\lfloor n/(n-k+2)\rfloor +\epsilon$$

where $\epsilon \in \{0,1\}$. For example, $\epsilon =1$ applies if $k=n-1$ [24]. Of course, $\mathrm{Ar}(n,K_{1,k})=\mathrm{Lr}(n,K_{1,k})$ holds because stars do not contain $2K_2$. Here, we prove that the presence of $2K_2$ in $K_{1,k}^{+}$ does not change the value of $\mathrm{Lr}$ if n is not too small. The particular case of $k=3$ will be reconsidered in Section 5.6, where exact formulas for all n will be proved for further anti-Ramsey functions.

Theorem 5.

For every $k\ge 3$, there is a threshold $n_0=n_0\left(k\right)$ such that $\mathrm{Lr}(n,K_{1,k}^{+})=\mathrm{Ar}(n,K_{1,k})$ holds for all $n\ge n_0\left(k\right)$.

Proof. 

The lower bound $\mathrm{Lr}(n,K_{1,k}^{+})\ge \mathrm{Ar}(n,K_{1,k})$ is clear because $K_{1,k}\subset K_{1,k}^{+}$. For the upper bound $\mathrm{Lr}(n,K_{1,k}^{+})\le \mathrm{Ar}(n,K_{1,k})$, let us suppose $n\gg k$, and let $\psi$ be an edge coloring of $K_n$ with at least $\mathrm{Ar}(n,K_{1,k})$ colors. Then a rainbow star $S\cong K_{1,k}$ occurs, by definition; say vertex v is its center and $u_1,\dots ,u_k$ are its leaves, and $\psi \left(u_{i}v\right)=i$ for $i=1,\dots ,k$. If S cannot be extended to a properly colored $K_{1,k}^{+}$, we must have $\psi \left(u_{i}w\right)=i$ for all $w\in V\left(K_n\right)\setminus V\left(S\right)$ and all $1\le i\le k$.

If $\psi \left(xy\right)$ is distinct from $1,\dots ,k$ for some $x,y\notin \{u_1,\dots ,u_k\}$ (but $x=v$ or $y=v$ is allowed), then we find a properly colored $K_{1,k}^{+}$ with center x, 2-length leg $xy{u}_1$, and pendant edges $u_{i}x$ for $i=2,3,\dots ,k$. Otherwise, the number of colors is at most $\left({\displaystyle \genfrac{}{}{0pt}{}{k}{2}}\right)$ on the edges $u_i{u}_j$, plus k on the remaining edges. But $\left({\displaystyle \genfrac{}{}{0pt}{}{k}{2}}\right)+k$ is smaller than $\mathrm{Ar}(n,K_{1,k})$ if n is not too small, so the theorem follows. □

We note that the condition $k\ge 3$ in the above theorem is necessary because, for $k=2$, we have $K_{1,k}^{+}\cong P_4$ with $\mathrm{Lr}(n,P_4)=3$ while $K_{1,2}\cong P_3$ with $\mathrm{Ar}(n,P_3)=2$ (see

Table 5. Anti-Ramsey numbers (possibly except for very small $n\le 8$), odd and parity versions: exact values for all graphs with at most four edges and for $P_6$, and currently known best estimates for the other two graphs with four vertices. LB = lower bound, UB = upper bound, $\mathrm{ex}(G_1,G_2)=\mathrm{ex}(n,\{G_1,G_2\})$; “≡” means that the equalities $\mathrm{Sod}=\mathrm{Od}=\mathrm{Cf}=\mathrm{Lr}$ hold, as Observation 1(3) applies to G; “=” means that the value is equal to the preceding entry of the same row but not necessarily due to a general structural principle. The eighth function has $\mathrm{Lp}(n,G)=1$ for all $G\ne K_4$ (and $\mathrm{Lp}(n,K_4)=\mathrm{Sp}(n,K_4)=\mathrm{Sod}(n,K_4)$ by Proposition 1(2)), either for all n or for all sufficiently large n.

G	Ar(n, G)	Lr(n, G)	Sod(n, G)	Cf(n, G)	Od(n, G)	Sp(n, G)	Cp(n, G)
$P_2$	1	1	≡	≡	≡	=	=
$P_3$	2	2	≡	≡	≡	=	=
$2P_2$	2	1	≡	≡	≡	=	=
$P_4$	3	3	≡	≡	≡	=	=
$P_3\cup P_2$	3	2	≡	≡	≡	=	=
$K_{1,3}$	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	1	2	1	=	=
$3P_2$	$n+1$	1	≡	≡	≡	=	=
$C_3$	n	n	≡	≡	≡	=	=
$K_{1,3}$ + leaf	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	2	3	2	=	=
$K_{1,3}\cup P_2$	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	$\lfloor {\displaystyle \frac{n}{2}}\rfloor +2$	1	2	1	=	=
$K_3$ + leaf	n	n	2	3	2	=	=
$P_3\cup 2P_2$	$n+1$	2	≡	≡	≡	=	=
$C_3\cup P_2$	$n+1$	n	≡	≡	≡	=	=
$P_4\cup P_2$	$n+1$	3	≡	≡	≡	=	=
$P_5$	$n+1$	4	≡	≡	≡	=	=
$2P_3$	$n+1$	$n+1$	≡	≡	≡	=	=
$K_{1,4}$	$n+2$	$n+2$	2	=	=	=	=
$C_4$	$\lfloor {\displaystyle \frac{4n}{3}}\rfloor$	$n+1$	≡	≡	≡	=	=
$4P_2$	$2n-1$	1	≡	≡	≡	=	=
$P_6$	$n+2$	$n+1$	≡	≡	≡	=	=
$K_4-e$	LB: $\mathrm{ex}(C_3,C_4)+2$	LB: $\lfloor {\displaystyle \frac{3n-1}{2}}\rfloor$	$n+1$	$n+1$	3	$n+1$	5
	UB: $\mathrm{ex}(C_3,C_4)+n+1$	UB: $2n-3$
$K_4$	$\lfloor {\displaystyle \frac{n^2}{4}}\rfloor +2$	LB: $\mathrm{ex}\left(C_4\right)+2$	LB: $2n-2$	$n+1$	1	$=\mathrm{Sod}$	LB: $2n-2$
		UB: $n⌈\sqrt{2n}⌉$	UB: $n⌈\sqrt{2n}⌉$				UB: $\mathrm{Sod}$

).

3.4. Graphs with Degrees All Odd or All Even

Theorem 6

(Odd Graphs). Let G be an odd graph. Then,

$\left(i\right)$

$\mathrm{Od}(n,G)=1$;

$\left(ii\right)$

$\mathrm{Sod}(n,G)=\mathrm{Sp}(n,G)=\mathrm{Lp}(n,G)$ either tends to infinity with n or is equal to 1 for all sufficiently large $n\ge n_0\left(G\right)$.

Proof. 

The first part is immediately seen, as the sum of any even integers is even, while all vertices have odd degrees. Concerning the second part, $\mathrm{Sod}(n,G)\ge \mathrm{Sp}(n,G)\ge \mathrm{Lp}(n,G)$ holds by definition, and in fact, the three values are equal whenever G is an odd graph, as observed in Proposition 1. We are going to prove that $\mathrm{Sod}(n,G)=1$ holds if n is large, unless ${lim}_{n\to \infty }\mathrm{Sod}(n,G)=\infty$.

If $\mathrm{Sod}(n,G)=1$ for some $n\ge \left|G\right|$, then $\mathrm{Sod}(n^{\prime },G)=1$ holds for all $n^{\prime }\ge n$ because a required copy of G is present in every n-vertex subgraph of $K_{n^{\prime }}$ in any edge coloring. Otherwise, suppose for a contradiction that $k:=lim\; inf\mathrm{Sod}(n,G)$ is finite and $k>1$. We choose n with $\mathrm{Sod}(n_0,G)=k$ and $n\ge {max}_{1\le t<k}R(G,t)$, the Ramsey number of G with t colors. Consider any edge coloring of $K_n$. If at least k colors are used, then a strong-odd-colored copy of G occurs, as $\mathrm{Sod}(n,G)=k$. If a smaller number t of colors is used, then $K_n$ contains a monochromatic—and consequently strong-odd-colored—copy of G, as $n\ge R(G,t)$. Thus, $\mathrm{Sod}(n,G)=1$, contradicting the assumption $k>1$. □

It follows from Proposition 4 that every even graph G has $\mathrm{Od}(n,G)\ge \left({\displaystyle \genfrac{}{}{0pt}{}{\left|G\right|-1}{2}}\right)+2$. We next show that this constant lower bound can be improved to linear in n. Recall from Section 2.3.1 that $\mathrm{Lex}(n,h)=n+h(h-3)/2$ is the number of colors in a h-LEX coloring.

Theorem 7

(Even Graphs/No Leaf). If G with $\left|G\right|=k$ is an even graph, then $\mathrm{Sod}(n,G)\ge \mathrm{Od}(n,G)\ge \mathrm{Lex}(n,k-1)+1\ge n$; and if $\delta \left(G\right)\ge 2$, then $\mathrm{Cf}(n,G)\ge \mathrm{Lex}(n,k-1)+1\ge n$.

Proof. 

Let $\psi$ be the $(k-1)$-LEX coloring of $K_n$ with vertex order $v_1,\dots ,v_n$. Consider any copy of G, and let $v_j$ be the vertex of the largest index in G. Since $\psi \left(v_i{v}_j\right)=j-k+1$ holds for all $v_i\in V\left(G\right)\setminus \left\{v_j\right\}$, and the degree of $v_j$ is even, $G^{\psi }$ does not satisfy the requirement of odd coloring, nor of conflict-free coloring if $\delta \left(G\right)\ge 2$. Hence $\mathrm{Sod}(n,G)\ge \mathrm{Od}(n,G)\ge \mathrm{Lex}(n,k-1)+1\ge n$ if all degrees are even, as well as $\mathrm{Cf}(n,G)\ge \mathrm{Lex}(n,k-1)+1\ge n$ if $\delta \left(G\right)\ge 2$. □

Theorem 8

(Corona of Even Graphs). Let H be any even graph, and G obtained from H by adding a leaf to every vertex of H. Then, for $n\ge n_0\left(G\right)$, $\mathrm{Sod}(n,G)=1$.

Proof. 

We apply Theorem 1 for $K=K_{3m}$, where $m=\left|G\right|=2\left|H\right|$. If there is a monochromatic or rainbow copy of K, we are finished, as a copy of G is strong-odd-colored. Hence it suffices to consider a LEX-colored K, say with vertices $v_1,\dots ,v_{3m}$, in this order under LEX. (In fact, from now on it would be enough to take $3m/2$ vertices only). Embed H in $v_{m+1},\dots ,v_{2m}$ arbitrarily.

At any $v_i$, the edges going to neighbors of higher indices in H have mutually distinct colors. A vertex can have either an odd or an even number of neighbors with lower indices, inducing a monochromatic star of odd or even degree, respectively.

If $v_i$ has an even number of lower neighbors in H, embed its leaf as $v_{i-m}$, and if it has an odd number of lower neighbors, embed its leaf as $v_{i+m}$. In this way, a strong odd coloring of G is obtained. So, no matter how many colors we use, $\mathrm{Sod}(n,G)=1$ holds for $n\ge n_0\left(G\right)$. □

3.5. Odd Majority Orientation and Odd–Even Ordering

Here, we introduce a certain type of permutation on the vertex set and present some consequences in connection with the anti-Ramsey functions under consideration.

Definition 2.

Given a graph G on k vertices $v_1,\dots ,v_k$ and a permutation π (of the $k!$ possible permutations) of its vertices, π is called odd majority orientation if

1. 

Each edge $e=(v_{\pi \left(i\right)},v_{\pi \left(j\right)})$, with $\pi \left(i\right)<\pi \left(j\right)$, is oriented from $v_{\pi \left(j\right)}$ to $v_{\pi \left(i\right)}$;

2. 

Each vertex v has either no outgoing edges (i.e., ${deg}^{+}\left(v\right)=0$) or has an odd number of outgoing edges (${deg}^{+}\left(v\right)\equiv 1\left(\mathrm{mod}2\right)$).

We also consider the following related notion.

Definition 3.

Given a graph G on k vertices $v_1,\dots ,v_k$, a permutation π of its vertices is called odd-even ordering if each vertex $v_{\pi \left(i\right)}$ satisfies one of the following conditions:

1. 

$v_{\pi \left(i\right)}$ has either zero or an odd number of neighbors $v_{\pi \left(j\right)}$ with $\pi \left(j\right)<\pi \left(i\right)$;

2. 

$v_{\pi \left(i\right)}$ has an even number of neighbors $v_{\pi \left(j\right)}$ with $\pi \left(j\right)<\pi \left(i\right)$, and no neighbors $v_{\pi \left(j^{\prime }\right)}$ with $\pi \left(i\right)<\pi \left(j^{\prime }\right)$.

By definition, every odd majority orientation $\pi$ is an odd-even ordering, but not vice versa. Also, if G is an even graph, then it admits no odd majority orientation because the vertex of the highest index assigned by any permutation violates the condition. But many even graphs (the cycles, for instance) admit an odd-even ordering.

Example 1.

$\left(i\right)$

For $k\ge 3$, the complete graph $K_k$ does not admit an odd majority orientation. Indeed, in any permutation, the third vertex has exactly two neighbors whose indices are smaller.

$\left(ii\right)$

If G is not an odd graph but has an odd majority orientation (e.g., $G=K_4-e$), then by inserting a new vertex and joining it to the odd-degree vertices of G, we obtain an even graph that admits an odd–even ordering. (The highest index can be assigned to the new vertex.)

The role of odd graphs and odd majority orientations is explored in the following result.

Theorem 9.

$\left(i\right)$

If G is an odd graph, and G has an odd majority orientation, then $\mathrm{Sod}(n,G)=\mathrm{Od}(n,G)=\mathrm{Sp}(n,G)=\mathrm{Cp}(n,G)=\mathrm{Lp}(n,G)=1$ for all $n\ge n_0\left(G\right)$.

$\left(ii\right)$

If a graph G admits an odd-even ordering, then $\mathrm{Lp}(n,G)=1$ holds for all $n\ge n_0\left(G\right)$.

$\left(iii\right)$

If G does not admit any odd majority orientation, then, for all $n\ge \left|G\right|$, $\mathrm{Sod}(n,G)\ge \mathrm{Sp}(n,G)\ge \mathrm{Cp}(n,G)\ge n$, and if in addition G has no odd-even ordering, then also $\mathrm{Lp}(n,G)\ge n$.

Proof. 

(i)

Since $\mathrm{Sod}(n,G)$ dominates all the other parameters, it suffices to consider strong odd colorings. Assume that G has p vertices, and apply Theorem 1 for $K_p$. Then, for every sufficiently large $n\ge n_0\left(p\right)$, no matter how many colors are used in an edge coloring of $K_n$, there is a copy K of $K_p$ whose coloring is monochromatic, rainbow, or LEX. This coloring pattern is inherited for any embedding of G into K. Since all vertex degrees are odd, a monochromatic G is strong-odd-colored. Also, every rainbow graph is strong-odd-colored. Finally, if K is LEX-colored, we choose a permutation $\pi$ that generates an odd majority orientation. Embed G into K in accordance with $\pi$. Any color j from the corresponding vertex $v_{j+1}$ to its smaller-index neighbors in G occurs on an odd number of vertices, and the edges from $v_{j+1}$ to its higher-index neighbors have mutually distinct colors. Thus, a strong odd coloring is obtained, independently of the number of colors in $K_n$, whenever n is sufficiently large. Consequently, $\mathrm{Sod}(n,G)=1$.

(ii)

We again apply Theorem 1. If n is sufficiently large, then any edge coloring contains a monochromatic or rainbow or LEX-colored $K_p$, $p=\left|G\right|$. The first two patterns immediately yield local-parity-colored copies of G. If a LEX-colored $K_p$ is found, we take an odd-even ordering on $V\left(G\right)$. The monochromatic star toward the lower-indexed neighbors of a vertex either has odd degree, which is of the same parity as the non-repeated colors to the higher-indexed neighbors, or has even degree equal to the degree of the vertex in G. Both cases are compatible with local parity coloring.

(iii)

To show that $n-1$ colors do not guarantee a class-parity-colored copy of G, nor a local-parity-colored copy if G satisfies the extra condition, we apply LEX. Any copy of G in $K_n$ must have a vertex, say $v_{j+1}$, with an even number of neighbors with lower indices; hence, in the corresponding orientation induced by $\pi$, it has an even number of incident color-j edges dictated by LEX in $K_n$. This star is not allowed in class parity coloring. Moreover, if G has no odd-even ordering, then any embedding of G in the LEX-colored $K_n$ contains a vertex v where a monochromatic star of even degree occurs toward its lower-indexed neighbors and also it has at least one higher-indexed neighbor, to which the color of the edge is not repeated at v. This is not allowed in local-parity-coloring.

□

This approach is easily applicable to bipartite graphs.

Theorem 10.

Let G be a bipartite graph. Then,

$\left(i\right)$

G admits an odd-even ordering; hence, $\mathrm{Lp}(n,G)=1$ for all $n\ge n_0\left(G\right)$.

$\left(ii\right)$

If G is an odd graph, and also if all even-degree vertices of G belong to the same vertex class, then G has an odd-majority orientation, and hence, $\mathrm{Sod}(n,G)=\mathrm{Od}(n,G)=\mathrm{Sp}(n,G)=\mathrm{Cp}(n,G)=\mathrm{Lp}(n,G)=1$ holds for all $n\ge n_0\left(G\right)$.

Proof. 

Let $A\cup B$ be the bipartition of G. Take a permutation that enumerates first (with the smallest indices) all the vertices from A and then all the vertices from B. The vertices of B only have lower-index neighbors, and those of A are adjacent only to higher-index neighbors. Hence, an odd-even ordering is obtained. And if all vertices of even degree are in A, then it is also an odd-majority orientation. Thus, the results of Theorem 9 apply to G. □

Cycles,both even and odd, do not admit an odd-majority orientation, as the vertex of the highest index in any permutation has exactly two lower neighbors. On the other hand, the exclusion of cycles suffices:

Proposition 5.

Every tree and forest admits an odd-majority orientation.

Proof. 

We apply induction on the number of vertices. Let T be a tree or a forest. The assertion is trivial if T has no edges. Otherwise, let $uv$ be a pendant edge, where v is a leaf of T. By the induction hypothesis, $T-v$ admits an odd-majority orientation. Insert v as the last vertex of T with the highest index, and for the rest of the vertices, keep the odd-majority orientation of $T-v$. Then, the number of lower neighbors of u remains odd, and of course, v has just one lower neighbor (and hence an odd number). □

It is important to note that there exist graphs admitting an odd-majority orientation and still having both $\mathrm{Cp}(n,G)$ and $\mathrm{Od}(n,G)$ that tend to infinity with n. In this sense, $\mathrm{Lp}(n,G)$ substantially differs from all the seven other anti-Ramsey functions.

4. Conflict-Free Anti-Ramsey Numbers Are Linear

The main result of this section is a general linear upper bound on all $\mathrm{Cf}(n,G)$. Since every conflict-free coloring is also a (weak) odd coloring, the theorem implies the linearity of $\mathrm{Od}(n,G)$ as well.

We begin with a simple observation.

Proposition 6.

For every $p\ge 2$, we have $\mathrm{Cf}(p,K_p)=\left({\displaystyle \genfrac{}{}{0pt}{}{p}{2}}\right)-⌊{\displaystyle \frac{p}{2}}⌋+1=⌈{\displaystyle \frac{p^2}{2}}⌉-p+1$.

Proof. 

To obtain a non-conflict-free coloring of $K_p$, it is necessary and sufficient that at least one vertex v has all its incident colors occur at least twice. If the vertex degree $p-1$ is even, then the loss compared to the number $\left({\displaystyle \genfrac{}{}{0pt}{}{p}{2}}\right)$ of colors in a rainbow $K_p$ is $(p-1)/2$, and if the degree is odd, then the loss is $p/2$. Hence, $\left({\displaystyle \genfrac{}{}{0pt}{}{p}{2}}\right)-⌊{\displaystyle \frac{p}{2}}⌋$ colors do not guarantee conflict-free coloring, but more colors do. □

On general graphs, a universal upper bound can be guaranteed as follows.

Theorem 11.

Let $G=(V,E)$ be a graph with p non-isolated vertices. Then,

$$\mathrm{Cf}(n,G)\le (p-2)(n-p)+⌈{\displaystyle \frac{p^2}{2}}⌉-p+1=(p-2)n-⌊{\displaystyle \frac{p^2}{2}}⌋+p+1.$$

Proof. 

We apply induction to n. The anchor with $n=p$ is settled in Proposition 6.

In the induction step, we prove $\mathrm{Cf}(n+1,G)\le \mathrm{Cf}(n,G)+p-2$. To do this, consider $K=K_{n+1}$ and any of its edge colorings $\psi$ with at least $\mathrm{Cf}(n,G)+p-2$ colors. If there is a vertex $v\in V\left(K\right)$ such that $\psi$ uses at least $\mathrm{Cf}(n,G)$ colors in $K-v$, then we have finished by the induction hypothesis. Otherwise, each v is the center of at least $p-1$ color classes that are stars. Let $Q_v\subset N\left(v\right)$ be a set composed by selecting one vertex from each star color class centered at v. (If an edge $e=vw$ is a singleton color class, then $w\in Q_v$ and $v\in Q_w$ are unique choices representing that color at the two ends of e).

Before designing a procedure for how a conflict-free copy of G is found in $K^{\psi }$, we make some preparations in G. Let S be any non-extendable independent set in G, and denote $Z:=V\setminus S$. Then, every $z\in Z$ has at least one neighbor in S. Assume that $X=\{x_1,\dots ,x_k\}\subset S$ is a minimal set dominating Z. If the set $W:=S\setminus X$ is nonempty, further let $Y=\{y_1,\dots ,y_l\}\subset Z$ be a minimal set dominating W. The definition of Y is meaningful because S is maximal and G has no isolates, so every $w\in W$ has a neighbor that must belong to Z as S is an independent set. Observe that, by the minimality of X and Y, each $x_i$ has a neighbor in Z whose unique neighbor in X is $x_i$, and each $y_i$ has a neighbor in W whose unique neighbor in Y is $y_i$.

For convenience, we label the vertices in X and Y in a way that the degrees of the $x_i$ are non-increasing, $d_G\left(x_1\right)\ge d_G\left(x_2\right)\ge \dots \ge d_G\left(x_k\right)$ and the degrees of the $y_i$ towards W are non-increasing, $d_W\left(y_1\right)\ge d_W\left(y_2\right)\ge \dots \ge d_W\left(y_l\right)$.

Next, still in G, we specify vertex subsets $X_i\subset Z$ ($i=1,\dots ,k$) and $Y_i\subset W$ ($i=1,\dots ,l$) sequentially in the order of increasing subscript as follows. Artificially setting $X_0=Y_0=⌀$, let $X_i$ be the set of all those vertices of Z that have no neighbors in ${\bigcup }_{j=0}^{i-1}{X}_j$, and let $Y_i$ be the set of all those vertices of W that have no neighbors in ${\bigcup }_{j=0}^{i-1}{Y}_j$.

Now, we are in a position to design an injective mapping $\eta :V\to V\left(K\right)$ that embeds G into K and yields a conflict-free-colored subgraph $H\cong G$. First, let $v_1=\eta \left(x_1\right)$ be any vertex of K, and let $\eta \left(X_1\right)$ be an arbitrarily chosen subset of $Q_{v_1}$ (with a size $|Q_{v_1}|=|X_1|$ of course). After that, for $i=2,\dots ,k$ in this order, we select $\eta \left(X_i\right)$ as an $|X_i|$-element subset of $Q_{v_i}\setminus {\bigcup }_{j=1}^{i-1}\eta \left(X_j\right)$. At this point, each $z\in \eta \left(X_i\right)$ is incident with a single edge of color $\psi \left(z\eta \left(x_i\right)\right)$, and this color occurs only once at $\eta \left(x_i\right)$ as well. Note further that these colors do not appear inside $V\left(K\right)\setminus \eta \left(X\right)$, so the corresponding edges remain single representatives of their colors even when we add any further vertices to $\eta (X\cup Z)$.

We complete the construction by applying a similar procedure for the vertices of $\eta \left(Y\right)$. To simplify notation, let us denote $U:=V\left(K\right)\setminus \eta (X\cup Z)$. Let $\eta \left(Y_1\right)$ be any $\left|\eta \right(Y_1\left)\right|$-element subset of $U\cap Q_{\eta \left(y_1\right)}$; then, for $i=2,\dots ,l$ in that order, select $\eta \left(Y_i\right)$ as a $|Y_i|$-element subset of $(U\cap Q_{\eta \left(y_i\right)})\setminus {\bigcup }_{j=1}^{i-1}\eta \left(Y_j\right)$. Now, each $w\in \eta \left(Y_i\right)$ is incident with a single edge of color $\psi \left(w\eta \left(y_i\right)\right)$, ensuring that the conflict-free requirement is satisfied at w.

Since $|Q_v|\ge p-1$ holds for every $v\in V\left(K\right)$, all the above selections are possible, and a conflict-free coloring of a subgraph isomorphic to G is found in K. □

Since $\mathrm{Od}(n,G)\le \mathrm{Cf}(n,G)$ holds for all graphs G and all $n\ge \left|G\right|$, we also obtain the following corollary:

Corollary 2.

We have $\mathrm{Od}(n,G)=O\left(n\right)$ for every graph G.

5. Paths, Cycles and Small Graphs

In this section, we mostly deal with the exhaustive list of all graphs of at most four vertices or edges, with $P_6$ as a slight extension, complementing the work carried out in [25,26] concerning $\mathrm{Ar}(n,G)$ where G is either a small graph or has only small components. Our results are then summarized in Table 5 for the convenience of the reader. Moreover, some general estimates for paths and cycles of any length will also be presented.

Before turning to particular types of graphs, let us introduce a general concept that will be useful in several proofs, notably in Section 5.5 and Section 5.8.

5.1. Locally Critical Colors

Let $\psi$ be any edge coloring of $K_n$ with any number of colors k. Call a color i critical at a vertex v if all edges of color i are incident with v. There are two kinds of critical color classes: a single edge with its private color, and a star with at least two edges. Denote the number of the former and the latter by s and t, respectively. A single edge is critical at both ends, and a star is critical at its center but not at its ends. Hence the total number of incidences is equal to

$$\#(\mathrm{vertex}, \mathrm{incident} \mathrm{critical} \mathrm{color})=2s+t$$

(5.1)

The relevance of critical colors becomes apparent in proofs by induction:

Observation 2.

In an inductive proof of $\varphi (n,G|\mathcal{F})\le an+b$ for an anti-Ramsey-related function ϕ under consideration, assuming that $\varphi (n-1,G|\mathcal{F})\le a(n-1)+b$ has been proved, one may restrict attention to edge colorings ψ of $K_n$ such that every vertex is incident with at least $a+1$ critical colors. Due to equality (5.1), in this case, we have

$$2s+t\ge (a+1)n.$$

5.2. Local Parity Coloring

Let us recall that $\mathrm{Lp}(n,G)=1$ if $\mathrm{\Delta }\left(G\right)\le 2$ (Proposition 1(4)) and $\mathrm{Lp}(n,G)=1$ holds for large enough n whenever G is bipartite or, more generally, admits an odd-even ordering (Theorems 9$\left(ii\right)$ and 10$\left(i\right)$), respectively). Of the graphs considered in this section, $K_4$ is the only one to which none of these principles can be applied. In fact, $K_4$ is an odd graph and its $\mathrm{Lp}$ has a substantially different behavior, satisfying $\mathrm{Lp}(n,K_4)=\mathrm{Sod}(n,K_4)=\mathrm{Sp}(n,K_4)$ by Proposition 1(2). For these reasons, we will not discuss $\mathrm{Lp}(n,G)$ separately for the various graphs G below.

5.3. Lower Bound for Paths and Cycles

Let us recall first that the anti-Ramsey numbers of cycles have been asymptotically determined as $\mathrm{Ar}(n,C_k)=\left((k-2)/2+1/(k-1)\right)n+O\left(1\right)$, by Montellano–Ballesteros and Neumann–Lara [6]; the problem of $\mathrm{Ar}(n,P_k)$ for paths has been solved recently by Yuan [14]. We note, however, that the coloring suggested by Erdős, Simonovits and Sós as a lower bound for anti-Ramsey $C_k$ is not applicable for $\mathrm{Lr}(n,C_k)$. This fact is worth mentioning because most of the considered functions defined in terms of local conditions are equal on any graph of maximum degree 2, but $\mathrm{Ar}(n,G)$ and $\mathrm{Lp}(n,G)$ usually have a different behavior.

For the local versions concerning these graphs, we have the following general lower bounds.

Theorem 12.

Recalling that $s(n,h)=hn-\left({\displaystyle \genfrac{}{}{0pt}{}{h+1}{2}}\right)+1$,

$\left(i\right)$

For $k\ge 4$, we have $\mathrm{Lr}(n,C_k)=\mathrm{Sod}(n,C_k)=\mathrm{Od}(n,C_k)=\mathrm{Cf}(n,C_k)\ge s(n,\lfloor (k-1)/3)\rfloor )+1$;

$\left(ii\right)$

For $k\ge 6$, we have $\mathrm{Lr}(n,P_k)=\mathrm{Sod}(n,P_k)=\mathrm{Od}(n,P_k)=\mathrm{Cf}(n,P_k)\ge \mathrm{Sp}(n,P_k)\ge \mathrm{Cp}(n,P_k)\ge s(n,\lfloor (k-3)/3\rfloor )+1$.

Proof. 

Recall that for any graph G with a maximum degree of at most 2, the four functions $\mathrm{Lr}$, $\mathrm{Sod}$, $\mathrm{Od}$, and $\mathrm{Cf}$ are equal. Moreover, the inequalities $\mathrm{Sod}(n,G)\ge \mathrm{Sp}(n,G)\ge \mathrm{Cp}(n,G)$ are valid for every graph G. Therefore, we only have to prove lower bounds on $\mathrm{Lr}(n,C_k)$ and $\mathrm{Cp}(n,P_k)$. The constructions for the two cases are quite similar, but there are some differences in the details. However, in either case, the idea is that the constructed edge coloring does not contain any paths and cycles above a certain length, so it suffices to restrict our attention to the smallest length relevant for a formula.

(i)

Let $k\ge 4$, $k\equiv 1$ (mod 3), and consider the (k-1)/3-RS-coloring of $K_n$. In any properly colored cycle C of length ℓ, at most two consecutive vertices can occur in the monochromatic part B; otherwise, there would be a vertex of the cycle with two incident edges in B having the same color. Hence, if $\ell \ge 3\left|A\right|+1$, then C is not properly colored.

(ii)

Let $k\ge 6$, $k\equiv 0$ (mod 3), and consider the (k-3)/3-RS-coloring of $K_n$. Also here, in any properly colored path P of length ℓ, at most two consecutive vertices can occur in the monochromatic part B; otherwise, there would be a vertex of the path with two incident edges in B having the same color. Hence, if $\ell \ge 3\left|A\right|+3$, then the edges of P inside B form a linear forest with at least one component of length exceeding 1. This is not allowed in class parity coloring.

The inequalities proved for ℓ verify the lower bounds in both parts of the theorem. □

5.4. The Cycle $C_4$

Theorem 13.

We have $\mathrm{Lr}(n,C_4)$ = $\mathrm{Sod}(n,C_4)$ = $\mathrm{Od}(n,C_4)$ = $\mathrm{Cf}(n,C_4)$ = $\mathrm{Sp}(n,C_4)$ = $\mathrm{Cp}(n,C_4)$ = $n+1.$

Proof. 

Due to Observation 1, i.e., the observation that the first four values are equal on any cycle, they also provide an upper bound on the last two values for any graph.

The lower bound on $\mathrm{Lr}(n,C_4)$ is the particular case $k=4$ of Theorem 12, using the 1-RS coloring. Although it does not work for the functions involving parity conditions, here, an alternative coloring can be defined. In fact, the same number of colors is achieved with the substantially different 3-LEX as well. In 3-LEX, the vertex of the highest index determines a color class $P_3$ with exactly two edges of the same color in any copy of $C_4$, so no class-parity-colored $C_4$ occurs.

For the upper bound, let $\psi$ be any edge coloring of $K_n$ with more than n colors. Selecting one edge from each of the first $n+1$ color classes, we obtain a rainbow graph with more edges than vertices. The same inequality also holds in at least one connected component of this selection. Such a component contains more than one cycle, so we can select a connected rainbow subgraph whose structure is one of the following:

$\left(a\right)$

Two vertices connected by three paths $P,P^{\prime },P^{″}$, any two of which are internally vertex-disjoint;

$\left(b\right)$

Two vertex-disjoint cycles $C^{\prime },C^{″}$ connected by a path P;

$\left(c\right)$

Two cycles $C^{\prime },C^{″}$ sharing precisely one vertex.

As a matter of fact, we can reduce $\left(a\right)$ to the following favorable case:

$\left(d\right)$

Some rainbow cycle C of even length contains no repeated color.

It is clear that $\left(a\right)$ reduces to $\left(d\right)$ because any two of $P,P^{\prime },P^{″}$ form a rainbow cycle and the lengths of (at least) two of those paths have the same parity.

If $\left(d\right)$ holds, we assume that C is a shortest rainbow cycle of an even length. If C is a 4-cycle, then we are done. Otherwise, let $u,v$ be two vertices at distance 3 along C. They are connected by two paths along C, say $P^{\prime }=uxyv$ and $P^{″}=C\setminus \{x,y\}$. Now, consider the edge $e=uv$ of $K_n$. If $\psi \left(uv\right)\ne \psi \left(ux\right)$ and also $\psi \left(uv\right)\ne \psi \left(yv\right)$, then an odd-colored $C_4$ is found on $\{u,x,y,v\}$. Otherwise, $\psi \left(uv\right)$ is absent from $P^{″}$, so $P^{″}\cup e$ is a rainbow even cycle shorter than C, a contradiction.

In case $\left(b\right)$, we assume that P is as short as possible. Let P have its ends $u\in V\left(C^{\prime }\right)$ and $v\in V\left(C^{″}\right)$. Consider the path $uxyv$ where $ux$ is an edge of $C^{\prime }$ and $yv$ is an edge of $C^{″}$. If $\psi \left(xy\right)$ does not occur in P, then omitting the (at most one) edge of color $\psi \left(xy\right)$ from $P\cup C^{\prime }\cup C^{″}$ and inserting the edge $xy$, we see that a rainbow subgraph of type $\left(a\right)$ can be found, and the proof is complete. Otherwise, if $\psi \left(xy\right)$ occurs in P, the minimality condition on P implies that P is the single edge $uv$ (as $xy$ alone would also connect $C^{\prime }$ with $C^{″}$), and since $\psi \left(xy\right)=\psi \left(uv\right)$ does not occur in $C^{\prime }\cup C^{″}$, we obtain an odd-colored $C_4$ on $\{u,x,y,v\}$.

It remains to analyze $\left(c\right)$ where both $C^{\prime }$ and $C^{″}$ are odd rainbow cycles. Now, we assume that $|C^{\prime }|+|C^{″}|$ is as small as possible. If $|C^{\prime }|>3$ (i.e., at least 5), let $uxyv$ be a subpath of $C^{\prime }$ disjoint from $V\left(C^{″}\right)$. As in the proof of $\left(d\right)$, we can consider the color $\psi \left(uv\right)$ of edge $e=uv$ and either find that there is a rainbow $C_4$ on $\{u,x,y,v\}$ or obtain the contradiction that $C^{\prime }$ can be shortened to $C^{\prime }\setminus \{x,y\}$ by the insertion of e. The same argument applies to $C^{″}$ as well. As a consequence, $C^{\prime }\cup C^{″}$ is the bow-tie graph $K_1+2K_2$. Let its two 3-cycles be $wux$ and $wvy$; by assumption, all six of their edges have mutually distinct colors. To complete the proof, we consider the edge $uv$ of $K_n$. If $\psi \left(uv\right)\notin \left\{\psi \right(uw),\psi (yv\left)\right\}$, then there is an odd-colored $C_4$ on $\{u,w,y,v\}$. Likewise, if $\psi \left(uv\right)\notin \left\{\psi \right(ux),\psi (wv\left)\right\}$, then there is an odd-colored $C_4$ on $\{u,x,w,v\}$. But at least one of these two cases must hold because $C^{\prime }\cup C^{″}$ is a rainbow graph, implying $\left\{\psi \right(uw),\psi (yv\left)\right\}\cap \left\{\psi \right(ux),\psi (wv\left)\right\}=⌀$.

Thus, an odd-colored $C_4$ is found in every $\psi$. □

5.5. Short Paths

For $n\ge 5$, we have $\mathrm{Ar}(n,P_4)=3$, as proven in [25]. Three colors are not sufficient for $n=4$, as shown by the proper edge 3-coloring of $K_4$. However, three colors suffice for all the other parameters considered in this paper.

Proposition 7.

We have $\mathrm{Sod}(n,P_4)$=$\mathrm{Od}(n,P_4)$ = $\mathrm{Cf}(n,P_4)$ = $\mathrm{Lr}(n,P_4)$ = $\mathrm{Sp}(n,P_4)$ = $\mathrm{Cp}(n,P_4)$= 3 for all $n\ge 4$.

Proof. 

A monochromatic spanning star in color 1 with a monochromatic $K_{n-1}$ in color 2 shows for all but $\mathrm{Lp}(n,P_4)$ that two colors are not sufficient. Due to $\mathrm{Ar}(n,P_4)=3$ for $n\ge 5$, we only have to verify the tightness of the lower bound 3 for $n=4$. If at least three colors are used in $K_4$, consider the two edges $v_1{v}_2$ and $v_3{v}_4$. They are connected by an edge whose color is distinct from both $\psi \left(v_1{v}_2\right)$ and $\psi \left(v_3{v}_4\right)$, so a properly colored $P_4$ is found. □

We also have tight results for paths of length four and five, as follows.

Theorem 14.

We have $\mathrm{Lr}(n,P_5)$ = $\mathrm{Od}(n,P_5)$ = $\mathrm{Sod}(n,P_5)$ = $\mathrm{Cf}(n,P_5)$ = $\mathrm{Sp}(n,P_5)$ = $\mathrm{Cp}(n,P_5)=4$ for every $n\ge 5$.

Proof. 

We have already seen that $\mathrm{Lr}(n,P_5)=\mathrm{Od}(n,P_5)=\mathrm{Sod}(n,P_5)=\mathrm{Cf}(n,P_5)$ and $\mathrm{Lr}(n,P_5)\ge \mathrm{Sp}(n,P_5)\ge \mathrm{Cp}(n,P_5)$. So, it will suffice to prove $\mathrm{Cp}(n,P_5)>3$ and $\mathrm{Lr}(n,P_5)\le 4$.

For the lower bound, let $\psi$ be the edge 3-coloring of $K_n$ where all edges incident with $v_1$ have color 1, all edges incident with $v_2$ except $v_1{v}_2$ have color 2, and all edges not meeting $\{v_1,v_2\}$ have color 3. Consider any copy P of $P_5$. One end of P should be $v_1$; otherwise, P contains a monochromatic $P_3$ (with $v_1$ in its middle), not allowed in class parity coloring, and the proof is complete. If $v_2$ is not the other end of P, then a monochromatic $P_3$ with middle $v_2$ occurs. If the two ends of P are $v_1$ and $v_2$, then the internal three vertices induce a monochromatic $P_3$ in $K_n^{\psi }-v_1-v_2$. Hence, $K_n^{\psi }$ does not contain any class-parity-colored $P_5$.

For the upper bound, let $n\ge 5$, and assume that $\psi$ is an edge coloring of $K_n$ without any proper $P_5$. We begin with two simple observations.

$\left(a\right)$

If P is a proper $P_4$ with an end vertex u whose incident edge in P has color i, then all vertices $w\notin V\left(P\right)$ have $\psi \left(uw\right)=i$.

$\left(b\right)$

$K_n^{\psi }$ does not contain any proper $C_4$.

Here, $\left(a\right)$ simply expresses that P has no extension to a proper $P_5$. To see $\left(b\right)$, let $C=pqru$ be a proper $C_4$, and consider any vertex $w\notin V\left(C\right)$. Since both $P^{\prime }=pqru$ and $P^{\prime \prime }=rqpu$ are proper $P_4$, by $\left(a\right)$, we should have $\psi \left(pu\right)=\psi \left(uw\right)=\psi \left(ru\right)$, contradicting the assumption that C is properly colored at u.

Assume now that $\psi$ uses at least four colors. Since $\mathrm{Ar}\left(P_4\right)=3$, we know that a rainbow $P_4$ occurs; say, the path $P:=vxyz$ has color pattern $(1,2,3)$ (meaning $\psi \left(vx\right)=1$, $\psi \left(xy\right)=2$, $\psi \left(yz\right)=3$). Below we write w (sometimes with a subscript) for vertices not contained in P.

Due to $\left(b\right)$, we can assume $\psi \left(vz\right)=1$. (More precisely $\left(b\right)$ implies color 1 or 3 on $vz$, but 1 can be taken for symmetry reasons.) Then, applying $\left(a\right)$ for the proper paths $zyxv$, $vzyx$, and $vxyz$, we obtain

• $\psi \left(vw\right)=1$, $\psi \left(xw\right)=2$, $\psi \left(zw\right)$ for all $w\notin V\left(P\right)$.

We consider the possible positions of an edge of color 4.

• If $\psi \left(vy\right)=4$, then $wxvyz$ is a proper $P_5$ with color pattern $(2,1,4,3)$ for any w.
• If $\psi \left(xz\right)=4$, then $\left(a\right)$ implies $\psi \left(yw\right)=3$ for all w by the path $vxzy$, and then $wyxzv$ is a proper $P_5$ with color pattern $(3,2,4,1)$ for any w.
• If $\psi \left(yw\right)=4$ for some w, then $vxywz$ is a proper $P_5$ with color pattern $(1,2,4,3)$.
• If $n\ge 6$ and $\psi \left(w_1{w}_2\right)=4$, then $vx{w}_1{w}_{2}z$ is a proper $P_5$ with color pattern $(1,2,4,3)$.

Hence, in all possible cases, a proper (in fact, rainbow) $P_5$ has been found. □

Remark 1.

There is a substantial difference between the behaviors of $P_4$ and $P_5$, as $\mathrm{Ar}(n,P_4)=3$ is a constant, while $\mathrm{Ar}(n,P_5)=n+1$ is linear in n, despite the fact that the other three functions for $P_5$ remain constant 4. Although in the analyzed four positions of an edge of color 4, we always found a rainbow $P_5$; this seeming contradiction arises because $\left(a\right)$ has been applied, which is not valid under the requirements of $\mathrm{Ar}$.

Also, a substantial difference occurs between $P_5$ and $P_6$, demonstrated by Theorem 15 below, as the values are constant for the former and grow linearly for the latter.

Theorem 15.

For every $n\ge 6$, we have $\mathrm{Od}(n,P_6)=\mathrm{Sod}(n,P_6)=\mathrm{Cf}(n,P_6)=\mathrm{Lr}(n,P_6)=\mathrm{Sp}(n,P_6)=\mathrm{Cp}(n,P_6)=n+1$.

Proof. 

We know that all the first four functions are equal and that they provide an upper bound on the last two. The lower bound $n+1$ is verified by the 1-RS coloring, namely a rainbow-spanning star with monochromatic $K_{n-1}$ on its leaf set. Any copy of $P_6$ contains a subpath with more than one edge from the monochromatic $K_{n-1}$, hence not class-parity-colored.

The upper bound is more complicated to prove.

To start, $n=6$, $\mathrm{Lr}(6,P_6)=7$.

Let $\psi$ be a coloring of $K_6$ with at least seven colors. Since $\mathrm{Ar}(6,P_4\cup P_2)=7$ by Proposition 6.3 of [25], we can label the vertices in such a way that $P=vxyz$ is a $P_4$ with color pattern $(1,2,3)$ and $uw$ is an edge of color 4 that joins the other two vertices. Trying to avoid a proper $P_6$ under $\psi$, step by step, we obtain restrictions on the colors of edges in $K_6$, which eventually will force the presence of a proper $P_6$ anyway.

First, we show that

• $\psi \left(vz\right)=1$

can be assumed (or 3, but the two cases are symmetric). Indeed, if $\psi \left(vz\right)\notin \{1,3\}$, then $vxyz$ is a proper $C_4$, so, e.g., viewing the two 4-cycles $yzvx$ and $vzyx$, we would obtain $\psi \left(xu\right)\in \{1,4\}\cap \{2,4\}$, so it should be color 4. By repeating this for all vertices of the 4-cycle, it would follow that all edges incident with u and w should have color 4, but then $uvxyzw$ would be a proper $P_6$.

Next, in a similar way, the three paths $zyxv,vzyx,vxyz$ imply

• $\psi \left(vu\right),\psi \left(vw\right)\in \{1,4\}$,
• $\psi \left(xu\right),\psi \left(xw\right)\in \{2,4\}$,
• $\psi \left(zu\right),\psi \left(zw\right)\in \{3,4\}$.

So far, only four colors have been used, so three new colors must occur, but only four edges are uncolored, namely $xz,yv,yu,yw$; only one of the four can have an old color from $\{1,2,3,4\}$. There must be an old color in both $wuyxzv$ and $uwyxzv$, so the edge of the old color is $\{uy,xz\}\cap \{wy,xz\}=xz$ with color $\psi \left(xz\right)\in \{1,2\}$. The other three colors are new and mutually distinct:

• $\psi \left(yv\right)=5$,
• $\psi \left(yu\right)=6$,
• $\psi \left(yw\right)=7$.

Now, the path $vwyzxu$ takes its color pattern from the alternatives of $\left(\right\{1,4\}$, 7, 3, $\{1,2\}$, $\{2,4\})$, which is a non-proper $P_6$ only if

• $\psi \left(xu\right)=\psi \left(xz\right)=2$.

But then, $vxuwyz$ is a rainbow $P_6$ with a color pattern $(1,2,4,7,3)$.

The induction step:  $n>6$.

Consider now $n\ge 7$, assuming that $\mathrm{Lr}(n-1,P_6)=n$ has been proved. Let $\psi$ be any edge coloring of $K_n$ with some $k>n$ colors, and assume that no properly colored $P_6$ is present. Denoting by s and t the number of critical edge- and critical star-classes, respectively, based on Observation 2, we may assume $2s+t\ge 2n$, or $s+t/2\ge n$.

If $s+t\ge n+2$, then we build a rainbow subgraph F of $K_n$ using one edge from each of the first $n+2$ critical color classes. The sum of degrees in F is equal to $2(n+2)$, so the average degree is $2(n+2)/n<3$ as $n\ge 7>4$. Consequently, there is a vertex in F with degree at most 2, and deleting it from $K_n$, we obtain $K_{n-1}$ with at least n colors, hence containing a properly colored $P_6$.

From now on we can assume $s+t\le n+1$. Together with $s+t/2\ge n$, this yields $s\ge n$ or $s=n-1$, the latter also implying $t=2$.

Assume first that $s\ge n$. We then consider a rainbow F with n critical edges. If there is a $P_4$ in F, then both ends of this $P_4$ can be extended to obtain a properly colored $P_6$. If there is no $P_4$ in F, then we apply the fact that $\mathrm{ex}(n,P_4)\le n$, and equality holds if and only if $3\mid n$ and $F\cong {\displaystyle \frac{n}{3}}{K}_3$. So, for $n\equiv 1,2$ (mod 3), we are done. For $n\equiv 0$ (mod 3) and $n\ge 6$, there are two vertex-disjoint triangles formed by critical edges. Take an edge connecting them. It must be of a distinct color, and a rainbow $P_6$ is obtained.

Finally, it remains to settle $s=n-1$ and $t=2$. We concentrate on the graph F formed by the $n-1$ critical edges. If $P_4\subset F$, and also if $2K_3\subset F$, the proof is completed as shown above. Similarly, if $3P_2\subset F$, then the three disjoint critical edges can be joined by two further edges to form a properly colored $P_6$. In particular, it follows that if no proper $P_6$ is found, then F either is connected or has exactly two components.

If F is connected but contains no $P_4$, then $F\cong K_{1,n-1}$, say, with center v, and $K_n-v$ is colored with at least two colors, all distinct from the star centered at v. Inside $K_n-v$, we take a two-colored $P_3=xyz$ and any two further vertices $u,w$. Then, $xyzvuw$ is a properly colored $P_6$.

If F has two components, then one of them is $K_3$ (two trees would have only $n-2$ edges), and the other one is $K_{1,n-4}$. Then, any edge connecting the triangle with a leaf of the star creates a properly colored $P_6$. □

5.6. Claw with Leaf

Let us introduce the notation $K_{1,3}^{+}$ for the graph obtained by attaching a pendant edge to one leaf of $K_{1,3}$.

Proposition 8.

$\mathrm{Lr}(n,K_{1,3}^{+})=\mathrm{Ar}(n,K_{1,3}^{+})=\lfloor n/2\rfloor +2$ for all $n\ge 6$.

Proof. 

It is proved in [25] that $\lfloor n/2\rfloor +2$ is an upper bound on $\mathrm{Ar}(n,K_{1,3}^{+})$ whenever $n\ge 6$, and hence also for $\mathrm{Lr}(n,K_{1,3}^{+})$. To see that $\mathrm{Lr}(n,K_{1,3}^{+})$ is not smaller, we take a rainbow matching of size $\lfloor n/2\rfloor$ and assign a new color c to all the other edges of $K_n$. Then, in any copy of $K_{1,3}^{+}$, the vertex of degree 2 is incident with at least two edges of color c, so $\lfloor n/2\rfloor +1$ colors are not enough to guarantee a properly colored $K_{1,3}^{+}$. □

Theorem 16.

$\mathrm{Sod}(n,K_{1,3}^{+})=\mathrm{Od}(n,K_{1,3}^{+})=\mathrm{Sp}(n,K_{1,3}^{+})=\mathrm{Cp}(n,K_{1,3}^{+})=2$ for $n\ge 7$.

Proof. 

Clearly, the monochromatic $K_n$ does not satisfy the conditions on $K_{1,3}^{+}$ for any of the four functions, so 2 is a valid lower bound.

Since $\mathrm{Sod}(n,K_{1,3}^{+})$ dominates the other three functions, the proof will be complete if we show the upper bound $\mathrm{Sod}(n,K_{1,3}^{+})\le 2$. Let the vertices of $K_n$ be $v_1,\dots ,v_n$, where $n\ge 7$. Suppose for a contradiction that $\psi$ is a non-monochromatic edge coloring without strong $K_{1,3}^{+}$.

Suppose first that there is a vertex with at least three edges of the same color at a vertex, say, $\psi \left(v_1{v}_2\right)=\psi \left(v_1{v}_3\right)=\psi \left(v_1{v}_4\right)=1$. Then, by the exclusion of a strong $K_{1,3}^{+}$, all edges between $\{v_2,v_3,v_4\}$ and $\{v_5,\dots ,v_n\}$ have color 1. But then, $v_2,v_3,v_4$ have a degree of at least $n-3\ge 4$ in color 1, so they also are adjacent to each other in color 1. Hence, they have a degree of $n-1$ in this color, which implies for a similar reason that the entire $K_n$ is monochromatic.

Otherwise, every color occurs on at most two edges at each vertex. Then, since $n\ge 7$, at least three colors occur at $v_n$. Say $\psi \left(v_1{v}_n\right)=1$, $\psi \left(v_2{v}_n\right)=2$, $\psi \left(v_3{v}_n\right)=3$. Viewing $v_n$ as the possible center of a $K_{1,3}^{+}$, we obtain that $\psi \left(v_1{v}_i\right)=1$ must hold for all $4\le i\le n$. Hence the degree of $v_1$ in color 1 is high, and we are back to the case that has already been settled. □

Remark 2.

Let us note that for $\mathrm{Sod}(n,K_{1,3}^{+})<3$, the condition $n\ge 7$ is necessary. This is shown by the edge coloring of $K_6$ where color 1 induces $K_{3,3}$ and color 2 induces $2K_3$. On the other hand, e.g., $\mathrm{Sod}(n,K_{1,3}^{+})<3$ is easy to prove for all $n\ge 5$. A good start is to take a two-colored $P_3$, say $v_4{v}_1{v}_5$, and then reduce the problem to $n=5$ by picking any $v_2,v_3$; observe that the triangle $v_1{v}_2{v}_3$ should be monochromatic unless a strong-odd-colored $K_{1,3}^{+}$ occurs, and we obtain a further 2-colored $P_3$, then another monochromatic triangle, and so on, until a required copy of $K_{1,3}^{+}$ is found.

Theorem 17.

$\mathrm{Cf}(n,K_{1,3}^{+})=3$.

Proof. 

Assign color 1 to all edges incident with a selected vertex v of $K_n$ and color 2 to all edges of $K_n-v$. Then, no Cf-colored $K_{1,3}^{+}$ occurs, proving $\mathrm{Cf}(n,K_{1,3}^{+})\ge 3$.

On the other hand, if an edge coloring of $K_n$ uses at least three colors, we can find a Cf-colored $P_4=wxyz$. Supplementing it with an edge $vx$, where v is a fifth vertex, we obtain a Cf-colored $K_{1,3}^{+}$. □

5.7. Triangle with Leaf, $K_1+(K_2\cup K_1)$

In order to simplify the notation, let us introduce $K_3^{+}$ for the graph, often called “paw” or “pan” in the literature, obtained from $K_3$ by attaching a pendant edge. We begin with a formula that can easily be deduced from known earlier results.

Theorem 18.

$\mathrm{Lr}(n,K_3^{+})=n$.

Proof. 

Since every triangle has to be rainbow not only under the $\mathrm{Ar}(n,G)$ scenario but also under $\mathrm{Lr}(n,G)$, we obtain

$$n=\mathrm{Ar}(n,K_3)\le \mathrm{Lr}(n,K_3^{+})\le \mathrm{Ar}(n,K_3^{+})=n,$$

so equality holds throughout. □

Theorem 19.

We have $\mathrm{Sod}(n,K_3^{+})=\mathrm{Od}(n,K_3^{+})=\mathrm{Sp}(n,K_3^{+})=\mathrm{Cp}(n,K_3^{+})=2$ for all $n\ge 6$. For smaller n, we have $\mathrm{Sod}(4,K_3^{+})=\mathrm{Sod}(5,K_3^{+})=4$ and $\mathrm{Od}(4,K_3^{+})=\mathrm{Od}(5,K_3^{+})=2$.

Proof. 

One color is not enough, since $K_3^{+}$ contains vertices of degree 2 (against $\mathrm{Od}$ and $\mathrm{Sod}$) and also vertices of opposite parity (against $\mathrm{Cp}$ and $\mathrm{Sp}$). Also, if $n=5$, assigning color 1 and color 2 equally to the four edges incident with a selected vertex and color 3 to the other six edges shows that three colors are not enough to guarantee a strong-odd-colored $K_3^{+}$. If $n=4$, we omit one vertex incident with color 3 from the 5-vertex construction. Hence, the values of $\mathrm{Sod}(n,K_3^{+})$ and $\mathrm{Od}(n,K_3^{+})$ cannot be smaller than claimed.

For upper bounds, note that $\mathrm{Sod}$ dominates all three other functions, so it will suffice to find a strong-odd-colored copy of $K_3^{+}$. We first settle the cases where some vertex is incident with at least three edges of the same color. Let v be a vertex where the number of monochromatic edges is largest. Say $v_0$ has $d\ge 3$ neighbors $v_1,\dots ,v_d$ adjacent to $v_0$ in color 1. Then, $\psi \left(v_i{v}_j\right)=1$ must hold for all $1\le i<j\le d$; otherwise, the triangle $v_0{v}_i{v}_j$ supplemented with any further edge $v_0{v}_k$ is a strong-odd-colored $K_3^{+}$. This yields a $K\cong K_{d+1}$ in color 1. For $n=4$, no more colors would be possible. Note further that, for any large n, there are no edges of color 1 between $V\left(K\right)$ and $V\left(K_n\right)\setminus V\left(K\right)$, since d has been chosen to be the largest degree among all color classes.

Consider a vertex $x\notin V\left(K\right)$, and let $\psi \left(v_{0}x\right)=2$. If two further vertices $v_i,v_j$ have $\psi \left(v_{i}x\right)=\psi \left(v_{j}x\right)=2$, then the triangle $v_i{v}_{j}x$ with the pendant edge $v_{0}x$ forms a desired $K_3^{+}$. The same conclusion holds if two vertices $v_i,v_j$ have $\psi \left(v_{i}x\right)=3$ and $\psi \left(v_{j}x\right)=4$. Thus, it follows that $d+1=4$, and we have $\psi \left(v_{0}x\right)=\psi \left(v_{1}x\right)=2$ and $\psi \left(v_{2}x\right)=\psi \left(v_{3}x\right)=3$.

In particular, if $n=5$, then the assumption $d\ge 3$ restricts the number of colors to 3. If $n\ge 6$, we take a sixth vertex $y\notin V\left(K\right)\cup \left\{x\right\}$. If $\psi \left(xy\right)$ is 2 or 3, then the triangle $v_0{v}_{1}x$ or $v_2{v}_{3}x$ with the pendant edge $xy$ forms a desired $K_3^{+}$; and if $xy$ has another color (1 or 4), then we can take the triangle $v_1{v}_{2}x$ for the same.

Hence, from now on, we can assume that each color has a degree of at most 2 at every vertex. For $n\ge 6$, this yields at least $\lceil (n-1)/2\rceil \ge 3$ colors at each vertex. If a three-colored $K_3$ occurs, we supplement it with a pendant edge whose color is distinct from the colors of the two incident edges of that triangle at the attaching vertex. If none of the triangles has three colors, but some color occurs twice at some vertex, we consider a monochromatic $P_3$. Say, $\psi \left(wx\right)=\psi \left(wy\right)=1$, and a further edge $yz$ has color 2. Repeatedly applying the “degree at most two” and “no rainbow triangle” conditions, we obtain $\psi \left(wz\right)=2$ (for w and $wyz$), $\psi (x,z)=1$ (for z and $wxz$), and choosing a fifth vertex u such that $\psi \left(ux\right)=3$, we derive $\psi \left(ux\right)=3$ (for x and $uwx$). And then the color of $uz$ cannot be defined, because it should be 2 or 3 for the triangle $uwz$, but color 2 already occurs twice at z and color 3 occurs twice at u. Thus, a three-colored triangle is unavoidable, and the proof is complete for $n\ge 6$.

To see $\mathrm{Sod}(4,K_3^{+})\le 4$, consider any coloring of $K_4$ with four or more colors, and select one edge from each of the first four colors. If the missing two edges form $P_3$, then a rainbow $K_3^{+}$ has been obtained. If they form $2K_2$, then we have a rainbow $C_4$. Insert one of its diagonals, and omit the edge of the same color from $C_4$ if it is present there, or otherwise omit any edge of $C_4$. Then, again, a rainbow $K_3^{+}$ is obtained.

Finally, to see $\mathrm{Sod}(5,K_3^{+})\le 4$, consider any coloring of $K_5$ with four colors $1,2,3,4$ or more. If the removal of a vertex v does not destroy any of $1,2,3,4$, then $K_5-v\cong K_4$ is colored with at least four colors, and a rainbow $K_3^{+}$ can be found as above. Otherwise two of the five vertices destroy the same color, say 4, which is then a single edge. Moreover, we know that each color has a degree of at most 2 at each vertex. So, if the removal of $v_1,v_2,v_3$ destroys color $1,2,3$, respectively, then colors $1,2,3,4$ occur on at most seven edges altogether. Hence there are at least five colors, and a three-colored triangle $C_3$ occurs. From the union of the two color classes that do not appear in this $C_3$, at least one edge meets $C_3$, thus yielding a rainbow $K_3^{+}$ and completing the proof. □

Theorem 20.

$\mathrm{Cf}(n,K_3^{+})=3$.

Proof. 

To show that two colors do not suffice, assign all but one edge of $K_n$ with color 1 and one edge colored 2. Then, at least one vertex of $K_3$ in any copy of $K_3^{+}$ will be incident with a monochromatic star, not conflict-free-colored.

Assume that an edge coloring $\psi$ of $K_n$ uses at least three colors. If $n\ge 5$, we apply the fact that $\mathrm{Ar}(n,P_4)=3$ holds for all $n\ge 5$. Consider a rainbow $P_4=wxyz$ where $\psi \left(wx\right)=a$, $\psi \left(xy\right)=b$, $\psi \left(yz\right)=c$. A Cf-colored $K_3^{+}$ is immediately found unless $\psi \left(wy\right)=a$ and $\psi \left(xz\right)=c$. Otherwise, if $\psi \left(wy\right)=a$ and $\psi \left(xz\right)=c$, the color $\psi \left(wz\right)$ differs from at least one of a and c; say, it is not a. Then, the edges $wx,wy,wz,xy$ induce a Cf-colored $K_3^{+}$.

Finally, let $n=4$. If $\psi$ uses more than three colors, we find a rainbow triangle (on applying the fact $\mathrm{Ar}(n,C_3)=n$) and supplement it with any pendant edge. If just three colors are used, pick one edge from each color class. If they form a triangle or a $P_4$, we are finished, as above. If they form the star $K_{1,3}$ with center w and leaves $x,y,z$, then consider $\psi \left(xy\right)$. If it is c, we have found a Cf-colored (in fact $\mathrm{Lr}$-colored) $K_3^{+}$. And if it is a (or b), then $xywz$ (or $yxwz$) is a rainbow $P_4$, and we are finished, as above. □

5.8. The Diamond $K_4-e$

Theorem 21.

$\mathrm{Od}(n,K_4-e)=3$.

Proof. 

An edge coloring of $K_n$ with all but one edges colored 1 and one edge colored 2 shows that at least three colors are needed.

Suppose an edge coloring $\psi$ uses at least three colors.

First, we show that if a rainbow triangle $C_3=xyz$ with colors $\psi \left(xy\right)=a$, $\psi \left(yz\right)=b$, $\psi \left(zx\right)=c$ occurs, then an odd-colored $K_4-e$ can be found. Consider a fourth vertex w outside $C_3$. If it is adjacent to $x,y$ with distinct colors, we are finished. So we may assume $\psi \left(wx\right)=\psi \left(wy\right)=d$, and also $\psi \left(wx\right)=\psi \left(wz\right)=d$ for the same reason. If d is not one of $a,b,c$, then delete any edge from the rainbow $C_3$, and we are finished. Otherwise, assume without loss of generality that $d=a$. Delete the edge colored a from the rainbow $C_3$, and we are finished.

Next, if $n\ge 5$, similarly to the proof of Theorem 20, we consider a rainbow $P_4=wxyz$ where $\psi \left(wx\right)=a$, $\psi \left(xy\right)=b$, $\psi \left(yz\right)=c$. Based on the above, we may assume that there is no rainbow $C_3$ under $\psi$. Then, $\psi \left(wy\right)$ is a or b, and $\psi \left(xz\right)$ is b or c. But then, independently of $\psi \left(wz\right)$, omitting the edge $xy$, we obtain an odd-colored $K_4-e$ on $\{w,x,y,z\}$.

Hence, we are left with the smallest case $n=4$. We next observe that a three-colored $K_{1,3}$ also yields an odd-colored $K_4-e$. Indeed, assume $\psi \left(wx\right)=a$, $\psi \left(wy\right)=b$, $\psi \left(wz\right)=c$. Excluding a rainbow $C_3$, we may assume $\psi \left(xy\right)=a$. Then, an odd-colored $K_4-e$ is found unless $\psi \left(xz\right)=c$. But then, inserting the edge $yz$ and omitting $wx$ yields an odd-colored $K_4-e$, independently of $\psi \left(yz\right)$.

Consider now any $\psi$ on the edges of $K_4$ with at least three colors. Assume $\psi \left(wx\right)=a$, $\psi \left(wy\right)=b$, and consider a third color c. There are three possible positions of a color-c edge: $xy$ or $wz$ or an edge from z to $\{x,y\}$. This yields a rainbow $C_3$, $K_{1,3}$, or $P_4$, respectively. The proof is complete. □

Theorem 22.

For every $n\ge 4$, we have $\mathrm{Sod}(n,K_4-e)=\mathrm{Sp}(n,K_4-e)=n+1$.

Proof. 

Since $\mathrm{Sod}\ge \mathrm{Sp}$ is universally valid, we need to prove $\mathrm{Sp}(n,K_4-e)>n$ and $\mathrm{Sod}(n,K_4-e)\le n+1$. The lower bound is provided by the 1-RS coloring: a rainbow spanning star and monochromatic $K_{n-1}$ in a new color. Then, every copy of $K_4-e$ has at least three vertices in the monochromatic part, and any induced subgraph of $K_4-e$ with more than two vertices contains a vertex of degree 2. But a 2-regular color class is not allowed in a strong parity coloring of $K_4-e$ because at the degree-3 vertices, some color class must have an odd degree.

The proof of the upper bound is by induction on n. The basic case of $\mathrm{Sod}(4,K_4-e)=5$ is obvious because, by using five colors on the edges of $K_4$, only one repetition occurs, and by removing one edge from the duplicated color, we obtain a rainbow $K_4-e$.

Consider now $n\ge 5$, assuming that $\mathrm{Sod}(n-1,K_4-e)=n$ has been proved. Let $\psi$ be any edge coloring of $K=K_n$ with some $k>n$ colors, and assume that no strong $K_4-e$ is present. Denoting by s and t the number of critical edge- and critical-star-classes, respectively, based on Observation 2, we may assume $2s+t\ge 2n$.

We are going to prove that the number of single-edge color classes is at most $2n/3$. More explicitly, each connected component in the graph formed by the single-edge colors is $K_2$ or $P_3$. For this purpose, we need to exclude $P_4$ and $K_3$ from the graph of critical single edges. The exclusion of a $P_4=vxyz$ is immediate because, by the single-edge criticality of the edges in $P_4$, we have $\psi \left(vy\right),\psi \left(xz\right)\notin \left\{\psi \right(vx),\psi (xy),\psi (yz\left)\right\}$, so $P_4$ would yield a strong $K_4-e$. In the case of a $K_3=xyz$ with three critical edges, if $\psi \left(xw\right)\ne \psi \left(yw\right)$ for a $w\notin \{x,y,z\}$, then a strong $K_4-e$ would occur on $\{w,x,y,z\}$. Consequently, we should have $\psi \left(xw\right)=\psi \left(yw\right)=\psi \left(zw\right)$, but then $K_3-e$, together with w, would form a strong $K_4-e$.

As a consequence, we have $s\le \lfloor 2n/3\rfloor$, implying $s+t\ge \lceil 4n/3\rceil :=n^{\ast }$. This also implies $n\ge 6$, because for $n=5$, we would have at most 3 critical edges and then the number of edges should be at least $s+2t=2(s+t)-s\ge 4n-3s\ge 11$, while $K_5$ has just 10 edges.

For $n\ge 6$, we consider $n^{\ast }$ color classes of $\psi$ (any choice) and select one edge from each of them. In this way, a rainbow graph, say F, with a degree sum $2n^{\ast }<3n$ is obtained. Consequently, $\delta \left(F\right)\le 2$. Let v be a vertex of minimum degree in F. Then, $F-v$ is a rainbow graph with at least $n^{*}-2\ge n$ edges. Thus, $\psi$ has more colors in $K-v=K_{n-1}$ than the number of vertices, and a proper $K_4-e$ must occur by the induction hypothesis. This final contradiction completes the proof of the theorem. □

Theorem 23.

For every $n\ge 4$, we have

$$\lfloor (3n-3)/2\rfloor +1\le \mathrm{Lr}(n,K_4-e)\le 2n-3.$$

Proof. 

Lower bound. The construction is a slight modification of the LEX or the 3-LEX coloring, depending on the parity of n.

We can artificially say that $\mathrm{Lr}(2,K_4-e)=2$ and $\mathrm{Lr}(3,K_4-e)=4$, because the trivial 1-coloring of $K_2$ and the rainbow $K_3$ exhibit the largest possible numbers of colors that we can use for $n=2$ and $n=3$ without a proper $K_4-e$.

Having a coloring of $K_{n-2}$ at hand, say on the vertex set Z, we adjoin two new vertices $x,y$ and construct a coloring for $K_n$ on $\{x,y\}\cup Z$. We use three new colors: one for the edge $xy$, one for the star of x–Z edges, and one for the star of y–Z edges.

A proper subgraph $H\cong K_4-e$ should contain at least one vertex outside Z and at least two vertices inside Z. But all H’s in such a position contain at least two x–Z edges or at least two y–Z edges and hence are not properly colored.

Upper bound. We proceed by induction on n. The basic case of $\mathrm{Lr}(4,K_4-e)=5$ is obvious because, using five colors on the edges of $K_4$, only one repetition occurs, and by removing one edge from the duplicated color, we obtain a rainbow $K_4-e$. (This is the same as the basic case for strong odd coloring.)

Let $\psi$ be any edge coloring of $K=K_n$ with some $k\ge 2n-3$ colors, and assume that no strong $K_4-e$ is present. Recall that a color i is critical at a vertex v if all edges of color i are incident with v. As discussed at the beginning of this section, a critical color class is either a single edge or a star.

If a vertex v is incident with at most two critical colors, then $\psi$ uses at least $2n-5$ colors in $K-v=K_{n-1}$, so a strong $K_4-e$ occurs by the induction hypothesis, contradicting the assumptions. It follows that each vertex is incident with at least three critical colors.

Construct a mixed graph $H=(V,E,A)$ as follows.

• $V=V\left(K\right)$.
• $vw\in E$ if $vw$ is a single-edge class in $\psi$.
• $\overrightarrow{vw}\in A$ if $\psi \left(vw\right)$ is a critical color at v, and the color class is a star centered at v with more than one edge.

For each vertex v, we denote by $N_i\left(v\right)$ the set of vertices x such that $vx\in E$ or $\overrightarrow{vx}\in A$, the neighbors for which v is critical in color i, and set ${\displaystyle N^{\ast }\left(v\right):=\left\{v\right\}\cup \bigcup _i{N}_i\left(v\right)}$ for their union together with v itself.

Consider any v. Say the critical colors at v are $1,\dots ,k$. The edges of the complete k-partite graph $\langle N_1\left(v\right),\dots ,N_k\left(v\right)\rangle$ are monochromatic; otherwise, it would contain two incident edges whose other ends are in distinct classes $N_i\left(v\right)$, so a two-colored $P_3=xyz$ would occur, and with v, it would form a rainbow $K_4-e$, contradicting the assumptions. This one “crossing” color is not critical because $k>2$. We denote this color by $c\left(v\right)$.

As a consequence, there can be three types of critical colors at a vertex $x\in N_i\left(v\right)$, namely

$\left(a\right)$

$vx$ is an edge critical for both v and x;

$\left(b\right)$

x is the end or center of a critical edge or star entirely inside $N_i\left(v\right)$;

$\left(c\right)$

There is a color $p>k$ and a vertex $y\in N_p\left(x\right)$ such that $p\ne c\left(v\right)$ and $y\notin N_i\left(v\right)$ for any $1\le i\le k$.

Suppose that case $\left(c\right)$ holds for some $v,x,y$. We then select a vertex $z\in N_2\left(v\right)$. Observe that $c\left(v\right)\notin \{1,2,p\}$ and $\psi \left(vy\right)\notin \{1,p\}$. We have arrived at the contradiction that $\{v,x,y,z\}$ contains a proper $K_4-e$. Hence, the proof will be complete if we show that case $\left(c\right)$ is unavoidable.

Consider the sets $N^{*}$ for all vertices of $K_n^{\psi }$, and let v be a vertex such that $|N^{*}\left(v\right)|$ is as small as possible. Assume that $N^{*}\left(v\right)\supset N_1\left(v\right)\cup N_2\left(v\right)\cup N_3\left(v\right)$. Select now a vertex $x\in N_1\left(v\right)$. The color $c\left(v\right)$ is not critical, so $N_2\left(v\right)\cup N_3\left(v\right)\subset N^{*}\left(v\right)$ is a nonempty set disjoint from $N^{*}\left(x\right)$. However, $|N^{*}\left(x\right)|\ge |N^{*}\left(v\right)|$ holds by assumption, implying the presence of a vertex $y\in N^{*}\left(x\right)\setminus N^{*}\left(v\right)$. This completes the proof. □

The next result dealing with class parity coloring demonstrates a less expected application of the Erdős–Rado Canonical Theorem.

Theorem 24.

$\mathrm{Cp}(n,K_4-e)=5$ if n is large.

Proof. 

The following 4-coloring shows that $\mathrm{Cp}(n,K_4-e)\ge 5$ holds for every n. Select two vertices $v_1,v_2$ in $K_n$, and denote $K^{\prime }=K_n-v_1-v_2$. Assign color 1 to all edges from $v_1$ to $K^{\prime }$ and color 2 to all edges from $v_2$ to $K^{\prime }$. Let $K^{\prime }$ be monochromatic in color 3, and assign color 4 to the edge $v_1{v}_2$.

Consider any copy G of $K_4-e$. If $G\subset K^{\prime }$ is monochromatic, then it contains vertices of degree 2 and 3 in the same color class, not allowed in class parity coloring. If both $v_1,v_2\in V\left(G\right)$, then at least one of colors 1 and 2 induces a $P_3$ color class, and neither is allowed. Finally, if exactly one of $v_1,v_2$ is in G, say $v_1$, it can have a degree 2 or 3 in G. A degree of 2 yields a monochromatic $P_3$ color class as above. A degree of 3 yields the odd graph $K_{1,3}$ in color 1. But then, $G-v_1\cong P_3$ is monochromatic in color 3, which is not allowed.

The proof of the opposite inequality $\mathrm{Cp}(n,K_4-e)\le 5$ requires more work. Let $\psi$ be any edge coloring of $K_n$ with at least five colors. We assume that n is sufficiently large to guarantee a $K_4$ with rainbow or LEX-colored or monochromatic coloring via Theorem 1. If this $K_4$ is a rainbow, it contains a rainbow $K_4-e$ and we are finished. If it is LEX-colored, we take a vertex order of $K_4-e$ where the two vertices of degree 2 are in the middle, and the two degree-3 vertices have the lowest and highest indices. Then LEX generates a color class $K_{1,3}$ at the highest vertex, and two single-edge color classes, and hence a strong odd coloring, and we are also finished in this case.

From now on, we may assume that there is no rainbow $K_4$ and no LEX-colored $K_4$ under $\psi$. Let K be a largest monochromatic complete subgraph in $K_n$, say in the highest color $k\ge 5$. The choice of n guarantees $\left|K\right|\ge 4$.

We next analyze the colors from the external vertices $v_i\in V\left(K_n\right)\setminus V\left(K\right)$ to K. There must be at least one edge of some color $c_i\ne k$ from $v_i$ to K, because K is not extendable to a larger monochromatic complete graph. If there are two such edges of distinct colors $c_i\ne c_i^{\prime }\ne k$, then we complete them as a copy of $K_4-e$ with a further vertex in K. Indeed, this $K_4-e$ has a monochromatic $K_3$ (an even graph) and two single edges as color classes, so a class parity coloring is obtained. So we may assume that each $v_i$ is adjacent to K with edges either colored k or colored with the same color $c_i$ other than k. This also implies that at least three vertices $v_1,v_2,v_3$ exist outside K, because $\psi$ uses at least five colors.

Next, we observe that there is at most one edge of color k from $v_i$ to K. Otherwise, we find a $C_4$ of color k with a diagonal of color $c_i$ and hence a class-parity-colored $K_4-e$. So, we may assume that each $v_i$ is adjacent to K with at least $\left|K\right|-1$ edges in color $c_i$.

If $c_i=c_j$ for some $i\ne j$, then the neighborhoods of $v_i$ and $v_j$ in color $c_i$ share at least $\left|K\right|-2$ vertices, that is, at least two. In this case, we find a $C_4$ of color $c_i$ with a diagonal of color k; hence, a class-parity-colored $K_4-e$ occurs again. So, we may assume without loss of generality that $c_i=i$ for $i=1,2,3$.

If $\psi \left(v_1{v}_2\right)=1$ (or likewise an edge of color 2 or 3 is assigned to an edge incident with $v_2$ or $v_3$, respectively, inside $\{v_1,v_2,v_3\}$), then we pick two vertices $w_1,w_2$ from K such that $\psi \left(v_i{w}_j\right)=i$ for all $i,j\in \{1,2\}$. Then, the sequence $(w_1,w_2,v_2,v_1)$ generates a LEX-colored $K_4$, a contradiction. And if none of the above occurs but color 1 is present as $\psi \left(v_2{v}_3\right)=1$, then we pick a w from K such that $\psi \left(v_{i}w\right)=i$ for $i=1,2,3$. (There are at least $\left|K\right|-3\ge 1$ possible choices for w.) Then, $\{w,v_1,v_2,v_3\}$ produces a properly colored $K_4-e$, as only $v_1{v}_2$ and $v_1{v}_3$ may possibly have the same color among incident edges.

We are left with the case where none of the three edges inside $\{v_1,v_2,v_3\}$ obtain any colors from $1,2,3$. If at least two colors are used there, then suitably omitting an edge, we obtain a rainbow $K_4-e$. If the triangle is monochromatic, then we supplement it with two edges incident with w and obtain a parity-class-colored copy of $K_4-e$. □

5.9. The Complete Graph $K_4$

Our last result on conflict-free colorings is valid for both $K_4-e$ and $K_4$, and the two can be handled together.

Theorem 25.

We have $\mathrm{Cf}(n,K_4-e)=\mathrm{Cf}(n,K_4)=n+1$.

Proof. 

The lower bound is provided by 3-LEX using n colors. It begins with a rainbow triangle, and each later vertex has a monochromatic star backward. Hence, the last vertex of any $K_4-e$ or $K_4$ does not have a local singleton color.

The upper bound follows by finding a properly colored $C_4$ in any edge coloring that uses more than n colors in $K_n$ via Theorem 13 and extending it to a conflict-free-colored $K_4-e$ or $K_4$, on applying Proposition 2(iii). □

Now, we turn to the other functions on $K_4$. Since $K_4$ is an odd graph, we have $\mathrm{Od}(n,K_4)=\mathrm{Lp}(n,K_4)=\mathrm{Sp}(n,K_4)=1$ for all n, and $\mathrm{Cf}(n,K_4)$ has been determined together with $\mathrm{Cf}(n,K_4-e)$. Below, we determine the growth order of $\mathrm{Lr}(n,K_4)$, and give a lower bound on $\mathrm{Sod}(n,K_4)$.

Theorem 26.

We have $\mathrm{Lr}(n,K_4)=\mathrm{\Theta }\left(n^{3/2}\right)$ as $n\to \infty$. More explicitly, for every $n\ge 4$,

$${\displaystyle (1/2-o\left(1\right))n^{3/2}=\mathrm{ex}(n,C_4)+2\le \mathrm{Lr}(n,K_4)\le n⌈\sqrt{2n}⌉}$$

Proof. 

For the lower bound, let G be any $C_4$-free graph of order n. Assign mutually distinct colors to the edges of G, and extend this to $K_n$ by assigning a fresh new color to all edges of $\overline{G}$. A $K_4\subset K_n$ cannot be proper, because, from the new edges, it may only contain a matching (either just one edge or a $2K_2$), but then a $C_4$ would be composed from edges of the rainbow G, which cannot be the case.

The upper bound is obvious if $n=4$, because then, six colors make $K_4$ rainbow, and 6 is much smaller than $4·⌈\sqrt{2·4}⌉$. For larger n we apply induction, assuming that the upper bound is valid for $n-1$.

Let $\psi$ be any coloring of $K_n$ with $f\left(n\right):=n⌈\sqrt{2n}⌉$ colors. Then,

$$f\left(n\right)/n=⌈\sqrt{2n}⌉\le ⌈\sqrt{2n}⌉+(n-1)(⌈\sqrt{2n}⌉-⌈\sqrt{2n-2}⌉)=f\left(n\right)-f(n-1)$$

holds for every n. Consequently, we can assume that there are at least $\sqrt{2n}+1$ critical colors each vertex, because otherwise, an obvious induction applies.

We now define a digraph $D=(V,A)$ with a vertex set $V=V\left(K_n\right)$ and arc set A in the following way. First, select one edge from each critical color. Those edges form a rainbow undirected graph $G=(V,E)$. Second, if an edge $e=uv\in E$ is a color class itself, take two arcs $\overrightarrow{uv},\overrightarrow{vu}\in A$ for e. Third, if an edge $e=uv\in E$ represents a star color class, orient e toward the center of the star as an arc in A. In this way, D has at least $n\sqrt{2n}+n$ arcs. The in-degree of each vertex is at least $\sqrt{2n}+1$; but we now concentrate on the out-degrees $d_1,\dots ,d_n$.

We say that an unordered vertex pair $\{u,v\}$ is assigned to a vertex w if both $\overrightarrow{wu},\overrightarrow{wv}\in A$. The number of vertex pairs assigned to the $i^{\mathrm{th}}$ vertex is equal to $\left({\displaystyle \genfrac{}{}{0pt}{}{d_i}{2}}\right)$. Since ${\sum }_{i=1}^n{d}_i=\left|A\right|\ge n\sqrt{2n}+n$, applying Jensen’s inequality, we obtain

$$\sum _{i=1}^n\left({\displaystyle \genfrac{}{}{0pt}{}{d_i}{2}}\right)\ge n·\left({\displaystyle \genfrac{}{}{0pt}{}{\left|A\right|/n}{2}}\right)\ge n·{\displaystyle \frac{(\sqrt{2n}+1)\sqrt{2n}}{2}}>n^2>2\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2}}\right).$$

Thus, there exists a pair $\{u,v\}$ assigned to at least three vertices, say $x,y,z$.

The six edges between $\{u,v\}$ and $\{x,y,z\}$ have mutually distinct colors as they originate from the rainbow graph G, and each of their color classes has its center in $\{u,v\}$, so none of them occur on the three edges inside $\{x,y,z\}$. The color $\psi \left(uv\right)$ may occur as one of those six colors connecting $\{u,v\}$ with $\{x,y,z\}$, so its one end is z. Then, $\{u,v,x,y\}$ induces $K_4$, which is either rainbow or 5-colored, where the only one-color coincidence is $\psi \left(uv\right)=\psi \left(xy\right)$. In either case, a proper $K_4$ is found. □

Currently, we do not have a strong upper bound on $\mathrm{Sod}(n,K_4)$; the lower bound is linear in n, while the upper bound grows with $n^{3/2}$.

Theorem 27.

For every $n\ge 4$, we have $\mathrm{Lr}(n,K_4)\ge \mathrm{Sod}(n,K_4)=\mathrm{Sp}(n,K_4)=\mathrm{Lp}(n,K_4)\ge 2n-2$, and also $\mathrm{Sp}(n,K_4)\ge \mathrm{Cp}(n,K_4)\ge 2n-2$.

Proof. 

We have seen that the upper bound $\mathrm{Lr}(n,K_4)$ and also the inequalities are valid by the hierarchy of criteria defining the corresponding anti-Ramsey functions. Moreover, the claimed equalities follow from Proposition 1(2), as $K_4$ is an odd graph.

For the lower bound $2n-2$, consider a coloring of $K_n$ with a rainbow star at $v_n$, and take a LEX coloring of $K:=K_n-v_n$. The total number of colors used is $2n-3$. If a copy of $K_4$ contains the center of the rainbow star, then the vertex of the largest index under LEX in K has exactly two edges of the same color (forming a monochromatic $P_3$) and an edge of another color to $v_n$, so this $K_4$ is neither local-parity-colored nor class-parity-colored. Otherwise, the copy is a $K_4$ under LEX on $n-1$ vertices, and the vertex of the second-highest index violates the condition. □

6. Concluding Remarks and Open Problems

In this concluding section, we collect many representative problems concerning the functions considered in this paper. Evidently, our choice is subjective, yet we hope that the enclosed list below opens a wide area of research with many more interesting results and problems to follow.

Table 5 summarizes the main results of Section 5 and can serve as the benchmark for further research and also as the start of induction steps in the case of generalizing some graphs into wider families of graphs.

Our list of problems is organized into subsections concentrating on

1.

The completion of results concerning specific graphs and small graphs;

2.

A further understanding of the hierarchy of the parameters;

3.

Algorithmic complexity problems concerning Odd Majority Ordering;

4.

Problems concerning the effect of graph operations;

5.

General host graphs, instead of complete graphs, and hypergraph versions.

6.1. Problems with Specific Graphs

Problem 1.

Determine tight asymptotics for $\mathrm{Lr}$, $\mathrm{Sod}$, $\mathrm{Od}$, $\mathrm{Cf}$, $\mathrm{Sp}$, and $\mathrm{Cp}$ for paths and cycles. In particular, find reasonable lower and upper bounds on $\mathrm{Sp}(n,C_k)$ and $\mathrm{Cp}(n,C_k)$. (See Theorem 12).

Problem 2.

Improve the linear lower bound $\mathrm{Cf}(n,K_k)\ge n+c_k$, provided by the$(k-1)$-LEX coloring of $K_n$.

Problem 3.

Determine all the parameters for $K_4-e$ and $K_4$ to complete the table of small graphs (Table 5).

Problem 4.

Find sharper—or even exact—bounds for $\mathrm{Sod}(n,K_k)$ and $\mathrm{Lr}(n,K_k)$, whose order is asymptotically determined.

Problem 5.

Determine $\varphi \left(\right|G|,G)$ for arbitrary graphs G and for any $\varphi \in \{\mathrm{Ar}$, $\mathrm{Lr}$, $\mathrm{Sod}$, $\mathrm{Od}$, $\mathrm{Cf}$, $\mathrm{Sp}$, $\mathrm{Cp}$, $\mathrm{Lp}\}$.

Problem 6.

Compute the missing parameters of small graphs for small n.

Concerning Theorem 5, we raise the following problem.

Problem 7.

Is it true that for every q, the spider $S=S_{q\ast 2,r\ast 1}$ with q legs $P_3$ and r legs $P_2$ (pendant edges) satisfies $\mathrm{Lr}(n,S)=\mathrm{Ar}(n,K_{1,q+r})$ whenever r is sufficiently large with respect to q ?

6.2. Problems on the Hierarchy of Constraints

Table 1 presents the hierarchy between the eight coloring requirements as implied by the definitions and proveb in Observation 1 and Proposition 1. For instance, a rainbow coloring (AR) satisfies all the other conditions as well, whereas an odd coloring (OD) or a local parity coloring (LP) is not guaranteed to fulfill any of the other seven. In particular, (OD, LP) is a simple example of an incomparable pair. Interesting questions arise both concerning comparable and concerning incomparable pairs.

6.2.1. Comparable Classes

Being positioned higher in the hierarchy implies that the corresponding parameter is not smaller. For two types of coloring constraints ${\mathcal{F}}_1,{\mathcal{F}}_2$ and a graph G, let us write

$$f(n,G|{\mathcal{F}}_1)\Rightarrow f(n,G|{\mathcal{F}}_2) \mathrm{if} (n,G|{\mathcal{F}}_1)\ge f(n,G|F_2) \mathrm{holds}\mathrm{for}\mathrm{all} n\ge n_0=n_0\left(G\right)$$

Problem 8.

If $f(n,G|{\mathcal{F}}_1)\ge f(n,G|{\mathcal{F}}_2)$ for all graphs G, then does there exist a $G^{\prime }$ and $n_0$ = $n_0\left(G^{\prime }\right)$ such that $f(n,G^{\prime }|{\mathcal{F}}_1)>f(n,G^{\prime }|{\mathcal{F}}_2)$ holds for all $n\ge n_0$?

Some positive cases are immediately read out from Table 5, but not all. Concerning $\mathrm{Sod}(n,G)\ge \mathrm{Sp}(n,G)$ we know of no graphs for which $\mathrm{Sod}(n,G)>\mathrm{Sp}(n,G)$, at least for all large n. Such a strict inequality can hold only if G is an even graph, as otherwise, by Proposition 1 (2), $\mathrm{Sod}(n,G)=\mathrm{Sp}(n,G)$. Furthermore if $\mathrm{Sp}(n,G)$ is realized by odd color classes, then equality still holds. This fact leads to the following problem.

Problem 9.

Does there exist an even graph G and an edge coloring $\psi =\psi \left(n\right)$ of $K_n$ with $\mathrm{Sp}(n,G)$ or more colors for every large n in which a copy of G occurs with even color classes but not with odd color classes?

For such a graph, $\mathrm{Sod}(n,G)>\mathrm{Sp}(n,G)$ would hold. With reference to Observation 1(3), let us note that even the following more restricted case remains open.

Problem 10.

Prove or disprove the following. If G has maximum degree at most 2, then $\mathrm{Sp}(n,G)=\mathrm{Sod}(n,G)$, or even $\mathrm{Cp}(n,G)=\mathrm{Sod}(n,G)$.

We mention that for $G=K_4-e$, the values satisfy the inequalities $\mathrm{Sod}(n,G)=\mathrm{Sp}(n,G)=n+1>\mathrm{Cp}(n,G)=5>\mathrm{Lp}(n,G)=1$; these resolve the other relations.

We also have $\mathrm{Sod}(n,K_4-e)=n+1>\mathrm{Od}(n,K_4-e)=3>\mathrm{Lp}(n.K_4-e)=1$ while $\mathrm{Od}(n,K_4)=1$ and $\mathrm{Lp}(n,K_4)\ge 2n-2$, showing that OD and LP are incomparable.

6.2.2. Incomparable Classes

The diagram in Table 1 indicates that the defining properties of the pairs (CF, SOD), (CF, SP), (CF,CP), (CF, LP), (OD, SP), (OD,CP), (OD, LP), and (CP, LP) are incomparable. Numerically, we also know that SOD, SP, CP, and LP can have a quadratic growth, while CF and OD have a linear upper bound, so a quadratic gap occurs, established, e.g., by $K_5$.

In the other direction, the table contains several graphs with $\mathrm{Cf}(n,G)>\mathrm{Sod}(n,G)$. So it remains to settle the status of (CP, LP) and of the pairs involving OD. Concerning the former, there are lots of examples satisfying $\mathrm{Cp}(n,G)>\mathrm{Lp}(n,G)$ and $\mathrm{Od}(n,G)>\mathrm{Lp}(n,G)$, since $\mathrm{\Delta }\left(G\right)\le 2$ implies $\mathrm{Lp}(n,G)=1$ by Proposition 1 (4). In fact, $\mathrm{Cp}(n,G)-\mathrm{Lp}(n,G)>cn$ and $\mathrm{Od}(n,G)-\mathrm{Lp}(n,G)>cn$ can hold for arbitrarily large c, establishing any large linear gap, as proven for long paths in Theorem 12$\left(ii\right)$. However, the following three cases remain open.

Problem 11.

Prove or disprove the following. There exist graphs $G_1,G_2,G_3$ such that

$\left(i\right)$

$\mathrm{Od}(n,G_1)>\mathrm{Sp}(n,G_1)$,

$\left(ii\right)$

$\mathrm{Od}(n,G_2)>\mathrm{Cp}(n,G_2)$,

$\left(iii\right)$

$\mathrm{Lp}(n,G_3)>\mathrm{Cp}(n,G_3)$.

We do not even have a single example of such $G_1,G_2,G_3$, nor a proof that such graphs do not exist. (Certainly, a $G_1$, if exists, would also serve as $G_2$.) Clarification of these three cases would settle whether the hierarchy exhibited in Table 1 coincides with the Hasse diagram of the partial order among the eight parameter classes under study.

6.3. Problems on Parity-Driven Vertex Orders

Problem 12.

Determine the complexity of the following decision problem:

• Odd-Majority Orientation (OMO):
• Input:  An undirected graph $G=(V,E)$.
• Question:  Does G admit an odd-majority orientation?

Also, if the answer is affirmative on G, how much time does it take to find an odd-majority orientation? How many permutations of V and how many orientations of E correspond to odd-majority orientations of G ?

Membership of OMO in $\mathcal{NP}$ is clear. The problem is of interest not only in general but also for special classes of graphs. According to Theorem 10$\left(ii\right)$, the answer is affirmative whenever G is a bipartite odd graph. Such graphs can be recongnized in $O\left(\right|V|+|E\left|\right)$ time, which is linear in the input size. The proof of the proposition shows that a suitable permutation can also be found in linear time, as it only needs to obtain the bipartition of G.

Problem 13.

Solve the analogous questions of algorithmic and enumerative nature on odd-even orderings:

• Odd–even Ordering (OEO).
• Input:  An undirected graph $G=(V,E)$.
• Question:  Does G admit an odd-even ordering?

In Theorem 10 we observed that in a bipartite graph, it is sufficient for the existence of an odd-majority orientation that all vertices of even degree belong to the same vertex class. The following question arises as a possible natural extension.

Problem 14.

Let G be a bipartite graph, in which the set of even-degree vertices is independent. Does G admit an odd-majority orientation?

6.4. Problems with the Effect of Graph Operations

Motivated by the Adding Edge Lemma (Proposition 2) and the observations in Section 2.6, we raise the following problem.

Problem 15.

Concerning all eight parameters $\varphi (n,G)$, where $\varphi \in \{\mathrm{Ar}$, $\mathrm{Lr}$, $\mathrm{Sod}$, $\mathrm{Od}$, $\mathrm{Cf}$, $\mathrm{Sp}$, $\mathrm{Cp}$, $\mathrm{Lp}\}$, taken over all graphs G with $\left|G\right|\le n$, determine

$\left(i\right)$

The maximum of $\varphi (G+e)-\varphi \left(G\right)$ where $e\notin E\left(G\right)$ is any new edge, if ϕ allows this difference to be positive;

$\left(ii\right)$

The maximum of $\varphi \left(G\right)-\varphi (G+e)$ where $e\notin E\left(G\right)$ is any new edge, if ϕ allows this difference to be positive;

$\left(iii\right)$

The above two values under the restriction that e joins two vertices of degree 2 in G, as a function of n.

As we have seen in Proposition 2, in some cases, the considered parameters cannot increase, and $\mathrm{Ar}(n,G)$ is an obvious example where it cannot decrease by edge insertion. A large jump can also occur in $\mathrm{Cp}(n,G)$ by joining two vertices of degree 2, as shown by $\mathrm{Cp}(n,K_4-e)=5$ and $\mathrm{Cp}(n,K_4)\ge 2n-2$.

More generally, we ask

Problem 16.

Study the effect of further graph operations on the functions $\varphi (n,G)$.

6.5. Other Host Graphs and Hypergraphs

One branch of anti-Ramsey theory deals with the so-called rainbow number. Given two graphs, G and H, where H serves as a host graph, the goal is to determine the smallest number $k=k(G,H)$ of colors such that every edge k-coloring of H contains a rainbow subgraph isomorphic to G. Analogous problems can be raised concerning the seven functions introduced here.

Problem 17.

Given two graphs G and H and a coloring type $\Phi \in \{\mathrm{LR}$, $\mathrm{SOD}$, $\mathrm{OD}$, $\mathrm{CF}$, $\mathrm{SP}$, $\mathrm{CP}$, $\mathrm{LP}\}$, determine the smallest integer $k=k(G,H;\Phi )$ such that every edge coloring of H with at least k colors contains a copy of G whose induced coloring is of type Φ.

Moreover, it is very natural to seek hypergraph analogs of interesting graph problems. Recall that a hypergraph (finite set system) is r-uniform if all its edges have exactly r elements. Beyond the edge colorings of $K_n$, one may consider edge colorings of the complete r-uniform hypergraph ${\mathcal{K}}_n^{\left(r\right)}$, whose edge set consists of all r-element subsets of an n-element vertex set. Given a fixed r-uniform hypergraph $\mathcal{H}$ and a property $\mathcal{P}$ of edge colorings, one can ask for the minimum number ${\varphi }_{\mathcal{P}}(n,\mathcal{H})$ of colors such that every edge coloring of ${\mathcal{K}}_n^{\left(r\right)}$ with at least ${\varphi }_{\mathcal{P}}(n,\mathcal{H})$ colors contains a copy of $\mathcal{H}$ that satisfies property $\mathcal{P}$. Similarly, if ${\mathcal{H}}_0$ is an r-uniform host hypergraph that contains at least one copy of $\mathcal{H}$, one can define ${\varphi }_{\mathcal{P}}({\mathcal{H}}_0,\mathcal{H})$ as the smallest integer such that every edge coloring of ${\mathcal{H}}_0$ with at least ${\varphi }_{\mathcal{P}}({\mathcal{H}}_0,\mathcal{H})$ colors contains a copy of $\mathcal{H}$ that satisfies property $\mathcal{P}$.

Problem 18.

Study the problems analogous to those investigated above on the more general class of uniform hypergraphs.