Search

In a fractional coloring, vertices of a graph are assigned measurable subsets of the real line and adjacent vertices receive disjoint subsets; the fractional chromatic number of a graph is at most k if it has a fractional coloring in which each vertex receives a subset of [ 0 , 1 ] of measure at least 1 / k. We introduce and develop the theory of "fractional colorings with local demands" wherein each vertex "demands" a certain amount of color that is determined by local parameters such as its degree or the clique number of its neighborhood. This framework provides the natural setting in which to generalize degree-sequence type bounds on the independence number. Indeed, by Linear Programming Duality, all of the problems we study have an equivalent formulation as a problem concerning weighted independence numbers, and they often imply new bounds on the independence number. Our results and conjectures are inspired by many of the most classical results and important open problems concerning the independence number and the chromatic number, often simultaneously. We conjecture a local strengthening of both Shearer's bound on the independence number of triangle-free graphs and the fractional relaxation of Molloy's recent bound on their chromatic number, as well as a longstanding problem of Ajtai et al. on the independence number of K r -free graphs and the fractional relaxations of Reed's ω , Δ , χ Conjecture and the Total Coloring Conjecture. We prove an approximate version of the first two, and we prove "local demands" versions of Vizing's Theorem and of some χ -boundedness results. [ABSTRACT FROM AUTHOR]

An edge coloring of hypergraph H is a color assignment to all edges in E(H) such that any pair of intersecting edges receive different colors. Let χ′(H) denote the minimum number of colors among all edge colorings of H. In 1985, Berge and Meyniel, independently, conjectured that each loopless linear hypergraph H has χ′(H) ≤ Δs(H) + 1, where Δs(H) =max v∈V (H)∑e∋v,e∈E(H)(|e|− 1). In this paper, a description of chromatic critical hypergraphs is given. Furthermore, we show χ′(H) ≤ Δs(H) − h + 1 for h-vertex-restricted hypergraphs and χ′(H) ≤ Δs(H) for edge-restricted hypergraphs. Since either of the class of 1-vertex-restricted hypergraphs and the class of edge-restricted hypergraphs contains well-ordered hypergraphs as a subclass, our results strictly extend the one on well-ordered hypergraphs due to Bretto et al. in 2020. [ABSTRACT FROM AUTHOR]

The edge DP-chromatic number of G, denoted by χ D P ′ (G) , is the minimum k such that G is edge DP-k-colorable. In 1999, Juvan, Mohar, and Thomas proved that the edge list chromatic number of K 4 -minor free graph G with Δ ≥ 3 is Δ. In this paper, we prove that if G is a K 4 -minor free graph, then χ D P ′ (G) ∈ { Δ , Δ + 1 } , and equality χ D P ′ (G) = Δ + 1 holds for some K 4 -minor free graph G with Δ = 3 . Moreover, if G is a planar graph with Δ ≥ 9 and with no intersecting triangles, then χ D P ′ (G) = Δ . [ABSTRACT FROM AUTHOR]

Completing partial latin squares is NP-complete. Motivated by Ryser's theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order m can be embedded in a symmetric latin square of order n. Loosely speaking, this results asserts that an n-coloring of the edges of the complete m-vertex graph K_m can be embedded in a one-factorization of K_n if and only if n is even and the number of edges of each color is at least m-n/2. We establish necessary and sufficient conditions under which an edge-coloring of the complete \lambda-fold m-vertex 3-graph \lambda K_m^3 can be embedded in a one-factorization of \lambda K_n^3. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if n\equiv 0\ (\mathrm {mod}\ 3), any edge-coloring of \lambda K_m^3 where the number of triples of each color is at least m/2-n/6, can be embedded in a one-factorization of \lambda K_n^3. Finally we prove an Evans type result by showing that if n\equiv 0\ (\mathrm {mod}\ 3) and n\geq 3m, then any q-coloring of the edges of any F\subseteq \lambda K_m^3 can be embedded in a one-factorization of \lambda K_n^3 as long as q\leq \lambda \binom {n-1}{2}-\lambda \binom {m}{3}/\left \lfloor m/3\right \rfloor. [ABSTRACT FROM AUTHOR]

An edge coloring of a graph G results in G being rainbow connected when every pair of vertices is linked by a rainbow path. Such a path is defined as one where each edge possesses a distinct color. A rainbow coloring refers to an edge coloring that guarantees the rainbow connectedness of G. The rainbow connection number of G represents the smallest quantity of colors required to achieve rainbow connectedness under a rainbow coloring scheme. Wang and Hsu (ICICM 2019: 75–79) provided upper bounds on the size of the rainbow connection numbers in WK-recursive networks WK d , t and WK-recursive pyramids WKP d , n . In this paper, we revise their results and determine the exact values of the rainbow connection numbers of WK d , 2 for d = 3 and 4. The rainbow connection numbers of WK d , 2 are bounded between 4 and ⌊ d 2 ⌋ + 2 for d > 4 . In addition to our previous findings, we further investigate and determine upper bounds for the size of the rainbow connection numbers of WKP d , n . This involves analyzing various aspects of the graph structure and exploring potential limitations on the rainbow connection numbers. By establishing these upper bounds, we gain deeper insights into the potential range and constraints of the rainbow connection numbers within the given context. [ABSTRACT FROM AUTHOR]

Let G be a finite, undirected and simple graph. A bijection f : V (G) → [1, |V (G)|] is called a local edge antimagic labeling if for any two adjacent edges uv, vx ∈ E(G), w(uv) ≠ w(vx) with w(uv) = f(u) + f(v). By giving every edges uv ∈ E(G) a coloring with w(uv), then the local edge antimagic labeling of G induces an edge coloring of G. The local edge antimagic chromatic number χlea'(G) is the minimum number of colors taken over all edge colorings induced by local edge antimagic labeling of G. In this paper, we investigate characterization of graphs G with small number χlea'(G), relationship between local edge antimagic chromatic number χlea'(G) and edge independence number α'(G), and bounds of χlea'(G) for any graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of extending partial edge colorings of iterated cartesian products of even cycles and paths, focusing on the case when the precolored edges satisfy either an Evans-type condition or is a matching. In particular, we prove that if G = C d 2k is the dth power of the cartesian product of the even cycle C2k with itself, and at most 2d−1 edges of G are precolored, then there is a proper 2d-edge coloring of G that agrees with the partial coloring. We show that the same conclusion holds, without restrictions on the number of precolored edges, if any two precolored edges are at distance at least 4 from each other. For odd cycles of length at least 5, we prove that if G = C d 2k+1 is the dth power of the cartesian product of the odd cycle C2k+1 with itself (k ≥ 2), and at most 2d edges of G are precolored, then there is a proper (2d+1)-edge coloring of G that agrees with the partial coloring. Our results generalize previous ones on precoloring extension of hypercubes [Journal of Graph Theory 95 (2020) 410–444]. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We give an online algorithm that with high probability computes a ( e e-1 + o(1)) Δ edge coloring on a graph G with maximum degree Δ = ω (log n) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay. [ABSTRACT FROM AUTHOR]

The edge DP-chromatic number of G, denoted by χDP′(G), is the minimum k such that G is edge DP-k-colorable. In 1999, Juvan, Mohar, and Thomas proved that the edge list chromatic number of K4-minor free graph G with Δ≥3 is Δ. In this paper, we prove that if G is a K4-minor free graph, then χDP′(G)∈{Δ,Δ+1}, and equality χDP′(G)=Δ+1 holds for some K4-minor free graph G with Δ=3. Moreover, if G is a planar graph with Δ≥9 and with no intersecting triangles, then χDP′(G)=Δ.

An edge coloring of a graph G results in G being rainbow connected when every pair of vertices is linked by a rainbow path. Such a path is defined as one where each edge possesses a distinct color. A rainbow coloring refers to an edge coloring that guarantees the rainbow connectedness of G. The rainbow connection number of G represents the smallest quantity of colors required to achieve rainbow connectedness under a rainbow coloring scheme. Wang and Hsu (ICICM 2019: 75–79) provided upper bounds on the size of the rainbow connection numbers in WK-recursive networks WKd,t and WK-recursive pyramids WKPd,n. In this paper, we revise their results and determine the exact values of the rainbow connection numbers of WKd,2 for d=3 and 4. The rainbow connection numbers of WKd,2 are bounded between 4 and ⌊d2⌋+2 for d>4. In addition to our previous findings, we further investigate and determine upper bounds for the size of the rainbow connection numbers of WKPd,n. This involves analyzing various aspects of the graph structure and exploring potential limitations on the rainbow connection numbers. By establishing these upper bounds, we gain deeper insights into the potential range and constraints of the rainbow connection numbers within the given context.

A graph G is called interval colorable if it has a proper edge coloring with colors 1 , 2 , 3 , ... such that the colors of the edges incident to every vertex of G form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph G , denoted θ int (G) , which is the minimum number of interval colorable edge-disjoint subgraphs of G whose union is G. Our investigation is motivated by scheduling problems with compactness requirements, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly 3-edge colorable graph with maximum degree 3 is interval colorable, and using this result, we deduce an upper bound on θ int (G) for general graphs G. We demonstrate that this upper bound can be improved in the case when G is bipartite, planar or complete multipartite and consider some applications in timetabling. [ABSTRACT FROM AUTHOR]

The modk $k$chromatic index of a graph G $G$ is the minimum number of colors needed to color the edges of G $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to 1(modk) $1\,(\mathrm{mod}\,k)$. Recently, the authors proved that the mod k $k$ chromatic index of every graph is at most 198k−101 $198k-101$, improving, for large k $k$, a result of Scott. Here we study the mod k $k$ chromatic index of random graphs. We prove that for every integer k≥2 $k\ge 2$, there is Ck>0 ${C}_{k}\gt 0$ such that if p≥Ckn−1log n $p\ge {C}_{k}{n}^{-1}\mathrm{log}\unicode{x0200A}n$ and n(1−p)→∞ $n(1-p)\to \infty $ as n→∞ $n\to \infty $, then the following holds: if k $k$ is odd, then the mod k $k$ chromatic index of G(n,p) $G(n,p)$ is asymptotically almost surely (a.a.s.) equal to k $k$, while if k $k$ is even, then the mod k $k$ chromatic index of G(2n,p) $G(2n,p)$ (respectively, G(2n+1,p) $G(2n+1,p)$) is a.a.s. equal to k $k$ (respectively, k+1 $k+1$). [ABSTRACT FROM AUTHOR]

In this paper, by developing several new adjacency lemmas about a path on four or five vertices, we show that the average degree of 7‐critical graphs is at least 6. It implies Vizing's planar graph conjecture for planar graphs with maximum degree 7 and its extension to graphs embeddable in a surface with nonnegative Euler characteristic due to Sanders and Zhao, and Zhang. [ABSTRACT FROM AUTHOR]

An edge coloring of a simple graph G is said to be proper rainbow-cycle-forbidding (PRCF, for short) if no two incident edges receive the same color and for any cycle in G, at least two edges of that cycle receive the same color. A graph G is defined to be PRCF-good if it admits a PRCF edge coloring, and G is deemed PRCF-bad otherwise. In recent work, Hoffman, et al. study PRCF edge colorings and find many examples of PRCF-bad graphs having girth less than or equal to 4. They then ask whether such graphs exist having girth greater than 4. In our work, we give a straightforward counting argument showing that the Hoffman-Singleton graph answers this question in the affirmative for the case of girth 5. It is then shown that certain generalized polygons, constructed of sufficiently large order, are also PRCF-bad, thus proving the existence of PRCF-bad graphs of girth 6, 8, 12, and 16.

An edge coloring φ of a graph G is called an Mf-edge coloring if | φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let 𝒦f (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on 𝒦f(G), present some graphs achieving the bounds and determine exact values of 𝒦f(G) for some special classes of graphs.

Let G be a simple graph and χ′(G) be the chromatic index of G. We call G a Δ‐critical graph if χ′(G − e ) = χ′( ) G − 1 = Δ for every edge e of G, where Δ is maximum degree of G. Let e x = y be an edge of Δ‐critical graph G and φ be an (proper) edge Δ‐coloring of G − e . An e‐fan is a sequence F x, e, y, e1, z1, ..., ep, zp of alternating vertices and distinct edges such that edge ei is incident with x or y, zi is another endvertex of ei and φ(ei ) is missing at a vertex before zi for each i with 1 ≤ i ≤ p. In this paper, we prove that if min, { ( dx) d(y)} ≤ Δ − 1, where d (x) and d ( y ) denote the degrees of vertices x and y, respectively, then colors missing at different vertices of V ( Fe ) are distinct. Clearly, a Vizing fan is an e‐fan with the restricting that all edges ei being incident with one fixed end vertex of edge e. This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced C‐fan. In this paper, we also generalize the C‐fan from centered at one vertex to one edge. [ABSTRACT FROM AUTHOR]

In the study of edge colorings of ordinary graphs, Vizing's adjacency lemma plays a crucial role. In this paper, we extend Vizing's adjacency lemma to critical signed graphs with even maximum degrees. As an application, we show that the signed planar graph conjecture is true for signed planar graphs with maximum degree at least 8, and that every k -degenerate signed graph with maximum degree at least 2 k is class one. [ABSTRACT FROM AUTHOR]

We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg–Seymour and list‐coloring conjectures for (list‐)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non‐constructive. Our key insight is that we can combine sophisticated techniques due to Achlioptas, Iliopoulos, and Kolmogorov for the analysis of local search algorithms with correlation decay properties of the probability spaces on matchings used by Kahn in order to construct efficient edge‐coloring algorithms. [ABSTRACT FROM AUTHOR]

The union vertex-distinguishing chromatic index χ ∪ ′ (G) of a graph G is the smallest natural number k such that the edges of G can be assigned nonempty subsets of [ k ] so that the union of the subsets assigned to the edges incident to each vertex is different. We prove that χ ∪ ′ (G) ∈ { ⌈ log 2 ⁡ (n + 1) ⌉ , ⌈ log 2 ⁡ (n + 1) ⌉ + 1 } for any graph G on n vertices without a component of order at most 2. This answers a question posed by Bousquet, Dailly, Duchêne, Kheddouci and Parreau, and independently by Chartrand, Hallas and Zhang. [ABSTRACT FROM AUTHOR]

The two-distance vertex-distinguishing index χd2′(G){\chi }_{d2}^{^{\prime} }\left(G) of graph GG is defined as the smallest integer kk, for which the edges of GG can be properly colored using kk colors. In this way, any pair of vertices at distance of two have distinct sets of colors. The two-distance vertex-distinguishing edge coloring of graphs can be used to solve some network problems. In this article, we used the method of discharging to prove that if GG is a graph with mad(G)

For an arbitrary invariant ρ(G) of a graph G the ρ-edge stability number esρ(G) is the minimum number of edges of G whose removal results in a graph H ⊆ G with ρ(H) ≠ ρ(G) or with E(H) = ∅.

Given a proper edge coloring α of a graph G, we define the palette SG(ν, α) of a vertex ν ∈ V (G) as the set of all colors appearing on edges incident to ν. The palette index š(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. The windmill graph Wd(n, k) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex. In this paper, we determine the bound on the palette index of Cartesian products of complete graphs and simple paths. We also consider the problem of determining the palette index of windmill graphs. In particular, we show that for any positive integers n, k ≥ 2, š(Wd(n, 2k)) = n + 1.

An edge coloring φ of a graph G is called an Mf-edge coloring if |φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let Kf(G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on Kf(G), present some graphs achieving the bounds and determine exact values of Kf(G) for some special classes of graphs. [ABSTRACT FROM AUTHOR]

This paper explores a new direction in the well studied area of graph saturation—we introduce the notion of rainbow saturation. A graph G is rainbow H-saturated if there is some proper edge coloring of G which is rainbow H-free (that is, it has no copy of H whose edges are all colored distinctly), but where the addition of any edge makes such a rainbow H-free coloring impossible. Taking the maximum number of edges in a rainbow H-saturated graph recovers the rainbow Turán numbers whose systematic study was begun by Keevash, Mubayi, Sudakov, and Verstraëte. In this paper, we initiate the study of corresponding rainbow saturation number—the minimum number of edges among all rainbow H-saturated graphs. We give examples of graphs for which the rainbow saturation number is bounded away from the traditional saturation number (including all complete graphs K n for n ≥ 4 and several bipartite graphs). It is notable that there are non-bipartite graphs for which this is the case, as this does not happen when it comes to the rainbow Turán number versus the traditional Turán number. We also show that saturation numbers are at most linear for a large class of graphs, providing a partial rainbow analogue of a well known theorem of Kászonyi and Tuza. We conclude this paper with a number of related open questions and conjectures. [ABSTRACT FROM AUTHOR]

A graph H is p-edge colorable if there is a coloring ψ : E (H) → { 1 , 2 , ⋯ , p } , such that for distinct u v , v w ∈ E (H) , we have ψ (u v) ≠ ψ (v w) . The Maximum Edge-Colorable Subgraph problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that | E (H) | ≥ l . We study the above problem from the viewpoint of Parameterized Complexity. We obtain FPT algorithms when parameterized by: (1) the vertex cover number of G, by using Integer Linear Programming, and (2) l, a randomized algorithm via a reduction to Rainbow Matching, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p + k , where k is one of the following: (1) the solution size, l, (2) the vertex cover number of G, and (3) l - mm (G) , where mm (G) is the size of a maximum matching in G; we show that the (decision version of the) problem admits a kernel with O (k · p) vertices. Furthermore, we show that there is no kernel of size O (k 1 - ϵ · f (p)) , for any ϵ > 0 and computable function f, unless NP ⊆ coNP / poly . [ABSTRACT FROM AUTHOR]

Copyright of Proceedings of the YSU A: Physical & Mathematical Sciences is the property of Publishing House of Yerevan State University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this work, we investigate the total and edge colorings of the Kneser graphs K(n, s). We prove that the sparse case of Kneser graphs, the odd graphs O k = K (2 k - 1 , k - 1) , have total chromatic number equal to Δ (O k) + 1 . We prove that Kneser graphs K(n, 2) verify the Total Coloring Conjecture when n is even, or when n is odd not divisible by 3. For the remaining cases when n is odd and divisible by 3, we obtain a total coloring of K(n, 2) with Δ (K (n , 2)) + 3 colors when n ≡ 3 mod 4 , and with Δ (K (n , 2)) + 4 colors when n ≡ 1 mod 4 . Furthermore, we present an infinite family of Kneser graphs K(n, 2) that have chromatic index equal to Δ (K (n , 2)) . [ABSTRACT FROM AUTHOR]

For r : = (r 1 , ... , r q) , an r -factorization of the complete λ -fold h -uniform m -vertex hypergraph λ K m h is a partition of the edges of λ K m h into F 1 , ... , F q such that each color class F i is r i -regular and spanning. We prove two results on embedding factorizations. Previously, these results were only known for a few small values of h , and even then only partially. We show that for n ⩾ h m and s : = (s 1 , ... , s k) , the obvious necessary conditions that ensure that an r -factorization of λ K m h can be embedded into an s -factorization of λ K n h are also sufficient. This extends Cruse's theorem, Baranyai's theorem, and Häggkvist-Hellgren's theorem. A connected r -factorization is an r -factorization in which each color class is connected. For n ⩾ h m , we establish the necessary and sufficient conditions under which an r -factorization of λ K m h can be embedded into a connected s -factorization of λ K n h. This extends Walecki's theorem, and Hilton's theorem on embedding Hamiltonian decompositions (take λ = r 1 = ... = r q = 1 , h = s 1 = ... = s k = 2). [ABSTRACT FROM AUTHOR]

In this article vertex, edge and total colorings of graphs are formalized in the Mizar system [4] and [1], based on the formalization of graphs in [5]. [ABSTRACT FROM AUTHOR]

A recent question in generalized Ramsey theory is that for fixed positive integers s ≤ t, at least how many vertices can be covered by the vertices of no more than s monochromatic members of the family F in every edge coloring of Kn with t colors. This is related to an old problem of Chung and Liu: for graph G and integers 1 ≤ s < t what is the smallest positive integer n = Rs,t(G) such that every coloring of the edges of Kn with t colors contains a copy of G with at most s colors. We answer this question when G is a star and s is either t - 1 or t - 2 generalizing the well-known result of Burr and Roberts. [ABSTRACT FROM AUTHOR]

For a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D (F) is the supremum of densities of graphs in F . A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1 , ... , k . A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F ) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H . Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω (k D (F)) and O (k D (F)) . In this paper we close the gap by improving the upper bound to O (k D (F)) for any rational D (F) . [ABSTRACT FROM AUTHOR]

We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Q d , we are interested in whether there is a proper d-edge coloring of Q d that agrees with the coloring φ on every edge that is colored under φ ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ . In particular, we prove that for any d ≥ 1 , if φ is a partial d-edge coloring of Q d , then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d - 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k ≤ d , we characterize for which configurations consisting of a partial coloring φ of d - k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ . [ABSTRACT FROM AUTHOR]

In this paper, we introduce the category and the homotopy category of edge-colored digraphs and construct the functorial homology theory on the foundation of the path homology theory provided by Grigoryan, Muranov, and Shing-Tung Yau. We give the construction of the path homology theory for edge-colored graphs that follows immediately from the consideration of natural functor from the category of graphs to the subcategory of symmetrical digraphs. We describe the natural filtration of path homology groups of any digraph equipped with edge coloring, provide the definition of the corresponding spectral sequence, and obtain commutative diagrams and braids of exact sequences.

An edge-colored rooted directed tree (aka arborescence) is path-monochromatic if every path in it is monochromatic. Let k , ℓ be positive integers. For a tournament T , let f T (k) be the largest integer such that every k -edge coloring of T has a path-monochromatic subtree with at least f T (k) vertices and let f T (k , ℓ) be the restriction to subtrees of depth at most ℓ. It was proved by Landau that f T (1 , 2) = n and proved by Sands et al. that f T (2) = n where | V (T) | = n. Here we consider f T (k) and f T (k , ℓ) in more generality, determine their extremal values in most cases, and in fact in all cases assuming the Caccetta-Häggkvist Conjecture. We also study the typical value of f T (k) and f T (k , ℓ) , i.e., when T is a random tournament. [ABSTRACT FROM AUTHOR]

Vizing's planar graph conjecture remains open for planar graphs with maximum degree 6. In this note, we prove that if each triangle of a planar graph G with maximum degree 6 has a vertex incident with only one triangle, then the chromatic index of G is 6 which means that G is of class one. [ABSTRACT FROM AUTHOR]

For a proper k -edge coloring ϕ : E (G) → { 1 , 2 , ... , k } of a graph G , let w (v) denote the sum of the colors taken on the edges incident to the vertex v. Given a positive integer p , the Σ p -neighbor sum distinguishing k -edge coloring of G is ϕ such that for each edge u v ∈ E (G) , | w (v) − w (u) | ≥ p. We denote the smallest integer k in such coloring of G by χ Σ p ′ (G). For p = 1 , Wang et al. proved that χ Σ 1 ′ (G) ≤ max { Δ (G) + 1 0 , 2 5 }. In this paper, we show that if G is a planar graph without isolated edges, then χ Σ p ′ (G) ≤ max { Δ (G) + (1 6 p − 6) , f (p) } , where f (p) = max { 2 2 p + 3 , 8 p 2 + 2 6 p + 1 + (2 p + 1) 1 6 p 2 + 9 6 p − 1 5 4 }. [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4. [ABSTRACT FROM AUTHOR]

Large-scale sparse precision matrix estimation has attracted wide interest from the statistics community. The convex partial correlation selection method (CONCORD) developed by Khare et al. (J R Stat Soc Ser B (Stat Methodol) 77(4):803–825, 2015) has recently been credited with some theoretical properties for estimating sparse precision matrices. The CONCORD obtains its solution by a coordinate descent algorithm (CONCORD-CD) based on the convexity of the objective function. However, since a coordinate-wise update in CONCORD-CD is inherently serial, a scale-up is nontrivial. In this paper, we propose a novel parallelization of CONCORD-CD, namely, CONCORD-PCD. CONCORD-PCD partitions the off-diagonal elements into several groups and updates each group simultaneously without harming the computational convergence of CONCORD-CD. We guarantee this by employing the notion of edge coloring in graph theory. Specifically, we establish a nontrivial correspondence between scheduling the updates of the off-diagonal elements in CONCORD-CD and coloring the edges of a complete graph. It turns out that CONCORD-PCD simultanoeusly updates off-diagonal elements in which the associated edges are colorable with the same color. As a result, the number of steps required for updating off-diagonal elements reduces from p (p - 1) / 2 to p - 1 (for even p) or p (for odd p), where p denotes the number of variables. We prove that the number of such steps is irreducible In addition, CONCORD-PCD is tailored to single-instruction multiple-data (SIMD) parallelism. A numerical study shows that the SIMD-parallelized PCD algorithm implemented in graphics processing units boosts the CONCORD-CD algorithm multiple times. The method is available in the R package pcdconcord. [ABSTRACT FROM AUTHOR]

Let ϕc(G) be the circular flow number of a bridgeless graph G. By Steffen it was proved that, for a bridgeless (2t+1)‐regular graph G, where t≥1 is a positive integer, ϕc(G)∈{2+1t,2+22t−1} if and only if G has a perfect matching M such that G−M is bipartite. This implies that G is a class 1 graph. For t=1, all graphs with circular flow number bigger than 4 are class 2 graphs. We show that, for all t≥1, 2+22t−1=inf{ϕc(G):G is a (2t+1)‐regular class 2 graph}. This was conjectured to be true by Steffen. Moreover we prove that, for all t≥1, inf{ϕc(G):G is a (2t+1)‐regular class 1 graph with no perfect matching whose removal leaves a bipartite graph=2+22t−1. We further disprove the conjecture that every (2t+1)‐regular class 1 graph has circular flow number at most 2+2t. [ABSTRACT FROM AUTHOR]