Compact cyclic edge-colorings of graphs

The paper is devoted to a model of compact cyclic edge-coloring of graphs. This variant of edge-coloring finds its applications in modeling schedules in production systems, in which production proceeds in a cyclic way. We point out optimal colorings for some graph classes and we construct graphs which cannot be colored in a compact cyclic manner. Moreover, we prove some theoretical properties of considered coloring model such as upper bounds on the number of colors in optimal compact cyclic coloring.     

关于K-tn的点可区别正常边染色

一个图的边染色称为是点可区别的,如果任意两个不同的顶点的关联边的颜色的集合不同. 设K-tn表示从n阶完全图中删去t条彼此不相邻的边后所得到的图. 本文对K-tn的点可区别正常边染色进行了讨论.     

关于(K_n~-)~t 的点可区别正常边染色(英文)

一个图的边染色称为是点可区别的 ,如果任意两个不同的顶点的关联边的颜色的集合不同 .设K-tn 表示从 n阶完全图中删去 t条彼此不相邻的边后所得到的图 .本文对 K-tn 的点可区别正常边染色进行了讨论 .     

重图的均匀边染色

图G的一个边染色称为是均匀的,如果对G的每个顶点v,与v关联的染任意两种颜色的边数至多相差一,我们给出了重图均匀边染色的一个充分条件。     

A note on the strong chromatic index of bipartite graphs

The strong chromatic index s^′(G) is the minimum integer t such that there is an edge-coloring of G with t colors in which every color class is an induced matching. Brualdi and Quinn conjecture that for every bipartite graph G, s^′(G) is bounded by Δ₁Δ₂, where Δ₁ and Δ₂ are the maximum degrees among vertices in the two partite sets. We give the affirmative answer for Δ₁=2.     

Strong edge-coloring of graphs with maximum degree 4 using 22 colors

In 1985, Erd?s and Ne?etril conjectured that the strong edge-coloring number of a graph is bounded above by when Δ is even and when Δ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for Δ?3. For Δ=4, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c：E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'_(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'_(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'_(1,0)(G)≤3Δ-1。     

关于平面图的边着色猜想（英文）

在最大度为△的图G中，设γ表示能够△一边着色的边的最大部分，Albertson和Hass猜想：如果G是无桥平面图，且△=3和，则γ=1．我们对于n2=2证明了这个猜想为真．     

Star 5-edge-colorings of subcubic multigraphs

The star chromatic index of a mulitigraph $G$, denoted ${\chi }_s^{\prime }\left(G\right)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star$k$-edge-colorable if ${\chi }_s^{\prime }\left(G\right)\le k$. Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than $7∕3$ is star list-5-edge-colorable. It is known that a graph with maximum average degree $14∕5$ is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than $12∕5$ is star 5-edge-colorable.     

若干圈限制平面图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’_st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’_st(G)≤[1.5Δ」+10;(3)若g=7,则χ’_st(G)≤[1.5Δ」+6.     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)geq5$, $Delta(G)geq6$且$5$-圈不相交的平面图的强边色数至多是$4Delta(G)-1$。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)geq5$, $Delta(G)geq6$且$5$-圈不相交的平面图的强边色数至多是$4Delta(G)-1$。