key: cord-0555694-iouprvoa authors: Bock, Felix; Kalinowski, Rafal; Pardey, Johannes; Pil'sniak, Monika; Rautenbach, Dieter; Wo'zniak, Mariusz title: Majority Edge-Colorings of Graphs date: 2022-05-23 journal: nan DOI: nan sha: c363b369589ad709d460c880b1ea05e3f727f5c9 doc_id: 555694 cord_uid: iouprvoa We propose the notion of a majority $k$-edge-coloring of a graph $G$, which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$, at most half the edges of $G$ incident with $u$ have the same color. We show the best possible results that every graph of minimum degree at least $2$ has a majority $4$-edge-coloring, and that every graph of minimum degree at least $4$ has a majority $3$-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems. Theorem 1. Let G be a connected graph. (i) If G has an even number of edges or G contains vertices of odd degree, then G has a 2-edge-coloring such that, for every vertex u of G, at most d G (u) 2 of the edges incident with u have the same color. (ii) If G has an odd number of edges, all vertices of G have even degree, and u G is any vertex of G, then G has a 2-edge-coloring such that, for every vertex u of G distinct from u G , exactly d G (u) 2 of the edges incident with u have the same color, and exactly d G (u G ) 2 + 1 of the edges incident with u G have the same color. Using Vizing's bound [13] on the chromatic index leads to our second result. Theorem 2. Every graph of minimum degree at least 2 has a majority 4-edge-coloring. Clearly, a graph containing a vertex of degree 1 does not have a majority edge-coloring, which motivates the minimum degree condition in Theorem 2. Furthermore, since class 2 graphs of minimum degree at least 2 and maximum degree 3 have no majority 3-edge-coloring, the number of colors in Theorem 2 is best possible under this minimum degree condition. In fact, if a graph G of minimum degree at least 2 has an induced subgraph H such that H is a class 2 graph of maximum degree 3, and all vertices of H have degree 2 or 3 in G, then G has no majority 3-edge-coloring. We conjecture that these are all graphs for which 4 colors are needed. Our third result supports this conjecture. Theorem 3. Every graph of minimum degree at least 4 has a majority 3-edge-coloring. Since a graph containing a vertex of odd degree at least 3 does not have a majority 2edge-coloring, the number of colors in Theorem 3 is best possible under the minimum degree condition in that result. In Section 2 we prove our results, and in a conclusion we discuss a variation of majority edge-colorings. Theorem 1 is a consequence of Euler's Theorem [7] . Proof of Theorem 1. (i) Let the multigraph G ′ arise from G by adding the edges of a perfect matching M on the possibly empty set of vertices of odd degree. Clearly, the multigraph G ′ is connected and every vertex has even degree in G ′ . Let e 0 e 1 . . . e m−1 be an Euler tour of G ′ , where, provided that M is not empty, we may assume that e m−1 ∈ M. Setting c(e i ) = (i mod 2) + 1 for every index i such that e i belongs to G, yields the desired 2-edge-coloring of G. (ii) Let e 0 e 1 . . . e m−1 be an Euler tour of G such that e 0 is incident with u G . Now, setting c(e i ) = (i mod 2) + 1 for every index i, yields the desired 2-edge-coloring of G. Theorem 2 is a consequence of Vizing's Theorem [13] . Proof of Theorem 2. Let G be a graph of minimum degree at least 2. If u is a vertex of degree d, and d = d 1 + · · ·+ d k is a partition of d into positive integers d i , then the graph H arises from G by splitting u into vertices of degrees Figure 1 for an illustration. Figure 1 : Splitting a vertex u of degree 7 into vertices of degrees 2, 2, and 3. Now, let G * arise from G by splitting every vertex of degree d > 3 into vertices of degrees Note that there is a natural bijection between the edges of G and those of G * . By Vizing's Theorem [13] , the graph G * has a proper 4-edge-coloring, which yields a majority 4-edgecoloring of G. In fact, we obtain an edge-coloring of G such that, for every vertex of degree d at least 4, at most (d + 2)/3 of the incident edges have the same color. We proceed to the proof of Theorem 3. Proof of Theorem 3. Let G be a graph of minimum degree δ at least 4. Let V (G) = D ∪ A ∪ C be the Gallai-Edmonds decomposition of G, that is, D is the set of all vertices of G that are missed by some maximum matching, A is the set of all vertices of G outside of D that have a neighbor of D, and C contains the remaining vertices, cf. [11] . Let D ′ be the set of isolated vertices in G[D]. Proof of Claim 1. Let the network N arise from the bipartite subgraph of G with partite sets D ′ and A that contains all edges of G incident with the vertices in D ′ by • adding a source vertex s, and connecting s to each vertex in D ′ by an arc of capacity 1, • adding a sink vertex t, and connecting each vertex v in A to t by an arc of capacity • orienting all edges of G between D ′ and A towards A, and assigning capacity 1 to these arcs. By the Max-Flow-Min-Cut Theorem [6] and the Integral Flow Theorem [5] , the claimed statement is equivalent to the statement that a maximum flow in N has value |D ′ |. Hence, in order to complete the proof, we suppose, for a contradiction, that f is an integral maximum flow in N of value less than |D ′ |. Let X be the set of all vertices of N that are reachable from s on a directed f -augmenting path, that is, the set X defines an s-t-cut of minimum capacity, for all arcs leaving X, the flow value is the capacity, and for all arcs entering X, the flow value is 0. Let X D = X ∩ D ′ and X A = X ∩ A. Let D 0 ∪ D 1 ∪ D 2 be a partition of X D such that • D 0 contains the vertices u from X D with f ((s, u)) = 0, • D 1 contains the vertices u from X D with f ((s, u)) = 1 and f ((u, v)) = 1 for some vertex v in X A , • D 2 contains the vertices u from X D with f ((s, u)) = 1 and f ((u, v)) = 0 for every vertex v in X A . Since the value of f is less than |D ′ |, we have D 0 = ∅. By the definition and properties of X, For every vertex u in D 2 , the unique vertex v from A \ X A with f ((u, v)) = 1 is the only neighbor of u in A \ X A . Therefore, the number m of edges of G between X D and X A is at least δ(|D 0 | + |D 1 |) + (δ − 1)|D 2 |, and at most For integers δ and d with 3 ≤ δ ≤ d, it is easy to verify that δ d 2 ≥ d, which yields a contradiction to (2) . This completes the proof of Claim 1. The properties of the Gallai-Edmonds decomposition imply that G[C] has a perfect matching M C , that there is a matching M A using edges between A and D that connects each vertex from A to a distinct component of G [D] , and that every component of G[D] is factor-critical. We now construct a subset E 1 of the edge set E(G) of G as follows starting with the empty set: • We add to E 1 all |D ′ | selected edges as in Claim 1. • We add M C to E 1 . • For every vertex v from A that is not incident with a selected edge, we add to E 1 the unique edge from M A incident with v. Let M ′ A be the subset of M A added to E 1 . • For every component K of G[D] of order at least 3 such that some vertex x of K is incident with an edge from M ′ A , we add to E 1 a perfect matching of K − x. • For every component K of G[D] of order at least 3 such that no vertex of K is incident with an edge from M ′ A , we add to E 1 a perfect matching of K − x for some vertex x of K as well as one further edge of K incident with x. Up to some small modifications explained below, this completes the description of E 1 . By construction, the spanning subgraph G 1 of G with edge set E 1 satisfies Let G 2 be the spanning subgraph of G with edge set E(G) \ E 1 . For every component K of G 2 such that all vertices of K have even degree in G 2 , K has an odd number of edges, and all vertices from V (K) have degree 1 in G 1 , we select any edge e K from K and move it from G 2 to G 1 . Note that K − e K contains exactly two vertices of odd degree, and, hence, is still connected. Furthermore, since G has minimum degree at least 4, it follows that (3) still holds after each such modification. Having performed these modifications for each such component of G 2 , every component K of (the modified) G 2 now • either contains at least one vertex of odd degree in K, • or all vertices of K have even degrees in K, and the number of edges of K is even, • or all vertices of K have even degrees in K, the number of edges of K is odd, and K contains a vertex u K such that the degree of u K in G 1 is at least 2. The components of G 2 as in the final point are called type 2 components, and the remaining components of G 2 are called type 1 components. We are now in a position to describe a majority 3-edge-coloring c : E(G) → [3] . • For all edges e of G 1 , let c(e) = 3. • For every component K of G 2 that is of type 1, let c : E(K) → [2] be as in Theorem 1(i) (applied to K as G). • For every component K of G 2 that is of type 2, let c : E(K) → [2] be as in Theorem 1(ii) (applied to K and u K as G and u G ). It is now easy to verify that c is a majority 3-edge-coloring of G, which completes the proof. The most natural question motivated by our results is which graphs of minimum degree at least 2 do not have a majority 3-edge-coloring. As a variation of majority edge-colorings, we propose to study α-majority edge-colorings for α ∈ (0, 1), where at most an α-fraction of the edges incident with each vertex are allowed to have the same color. If k is a positive integer at least 2, then every positive integer at least k(k − 1) can be written as a non-negative integral linear combination of k and k + 1. Using this fact, a straightforward adaptation of the proof of Theorem 2 yields the following statement: If a graph G has minimum degree at least k(k − 1), then G has a 1 k -majority (k + 2)-edge-coloring. A probabilistic argument implies that, for a sufficiently large minimum degree, one color less suffices. Theorem 4. For every integer k at least 2, there is a positive integer δ k such that every graph of minimum degree at least δ k has a 1 k -majority (k + 1)-edge-coloring. Proof. Let G be a graph of minimum degree δ at least δ k , where we specify δ k later. Let c : E(G) → [k + 1] be a random (k + 1)-edge-coloring, where we choose the color of each edge uniformly and independently at random. For every vertex u of G, we consider the bad event A u that more than 1 k d G (u) of the edges incident with u have the same color. For d = d G (u), the union bound and the Chernoff inequality, cf. [12] , imply Vizing's and Shannon's Theorems for defective edge colouring Unfriendly partitions of a graph Frugal Colouring of Graphs Majority choosability of digraphs On the max-flow min-cut theorem of networks Maximal flow through a network Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren Aspects of edge list-olourings Majority colourings of digraphs On decomposition of graphs Matching theory Graph colouring and the probabilistic method On an estimate of the chromatic class of a p-graph Bounded degree acyclic decompositions of digraphs Acknowledgement. The research reported in this paper was carried out at the 25th C5 Graph Theory Workshop organized by Ingo Schiermeyer in Rathen, May 2022. After a pause due to the COVID-19 pandemic, we very strongly felt the value of the creative, collaborative, and enjoyable atmosphere and the direct personal exchange at that workshop. We express our gratitude to Ingo, not just for this year but also for the long tradition of this wonderful meeting. (Chernoff inequality)In order to complete the proof, we use the weighted Lovász Local Lemma, cf. [12] , to show that with positive probability none of the bad events A u occurs. Let p = (k + 1)e − δ 3k 2 (k+1) and,δ . Choosing δ α sufficiently large, we may assume that p ≤ 1 4 , and, hence,Since, for every vertex u of G, the event A u is determined only by the colors of the edges incident with u, which are chosen uniformly and independently at random, the event A u is mutually independent of all events A v except for those for which v is a neighbor of u. We obtainwhich is at most t u /2 for δ k sufficiently large. Now, by the weighted Lovász Local Lemma, the edge-coloring c is a 1 k -majority (k + 1)-edge-coloring with positive probability, which completes the proof.Our Theorem 3 implies that 4 is the smallest possible value for δ 2 .