Star Chromatic Index

The star chromatic index of a graph G is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi‐colored. We obtain a near‐linear upper bound in terms of the maximum degree . Our best lower bound on in terms of Δ is valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.     

List star edge coloring of k-degenerate graphs

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree $\Delta$ is at most $?\frac{3\Delta }{2}?$, which is tight. In this paper, we study the list star edge coloring of $k$-degenerate graphs. Let $c{h}_{st}^{\prime }\left(G\right)$ be the list star chromatic index of $G$: the minimum $s$ such that for every $s$-list assignment $L$ for the edges, $G$ has a star edge coloring from $L$. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. $c{h}_{st}^{\prime }\left(T\right)\le ?\frac{3\Delta }{2}?$ for any tree $T$ with maximum degree $\Delta$. And then by applying some orientation technique we present two upper bounds for list star chromatic index of $k$-degenerate graphs.     

一些积图的点可区别均匀边色数

本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC).     

Star Edge Coloring of Some Classes of Graphs

A star edge coloring of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this article, we establish tight upper bounds for trees and subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs.     

Proof of a conjecture of Alan Hartman

A tree T is said to be bad, if it is the vertex‐disjoint union of two stars plus an edge joining the center of the first star to an end‐vertex of the second star. A tree T is good, if it is not bad. In this article, we prove a conjecture of Alan Hartman that, for any spanning tree T of K_2m, where m ≥ 4, there exists a (2m − 1)‐edge‐coloring of K_2m such that all the edges of T receive distinct colors if and only if T is good. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 7–17, 1999     

一些倍图的点可区别均匀边色数

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色,其所用最少染色数称为点可区别均匀边色数.本文得到了星、扇和轮的倍图的点可区别均匀边色数.     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

若干图的倍图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数．本文得到了星、扇和轮的倍图的均匀邻强边色数．     

一些图的Mycielski图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到了路、圈、星和扇的Mycielski图的均匀邻强边色数.     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010     

关于图的星色数的一点注记

A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored.The star chromatic number of an undirected graph G,denoted by χs(G),is the smallest integer k for which G admits a star coloring with k colors.In this paper,we show that if G is a graph with maximum degree △,then χs(G) ≤ [7△3/2],which gets better bound than those of Fertin,Raspaud and Reed.     

Star chromatic index of subcubic multigraphs

The star chromatic index of a multigraph G, denoted , is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k‐edge‐colorable if . Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7‐edge‐colorable. They conjectured in the same article that every subcubic multigraph should be star 6‐edge‐colorable. In this article, we first prove that it is NP‐complete to determine whether for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6‐edge‐colorable if , and star 5‐edge‐colorable if , respectively, where is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.     

Star coloring bipartite planar graphs

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

Colored Saturation Parameters for Rainbow Subgraphs

Inspired by a 1987 result of Hanson and Toft [Edge‐colored saturated graphs, J Graph Theory 11 (1987), 191–196] and several recent results, we consider the following saturation problem for edge‐colored graphs. An edge‐coloring of a graph F is rainbow if every edge of F receives a different color. Let denote the set of rainbow‐colored copies of F. A t‐edge‐colored graph G is ‐saturated if G does not contain a rainbow copy of F but for any edge and any color , the addition of e to G in color i creates a rainbow copy of F. Let denote the minimum number of edges in an ‐saturated graph of order n. We call this the rainbow saturation number of F. In this article, we prove several results about rainbow saturation numbers of graphs. In stark contrast with the related problem for monochromatic subgraphs, wherein the saturation is always linear in n, we prove that rainbow saturation numbers have a variety of different orders of growth. For instance, the rainbow saturation number of the complete graph lies between and , the rainbow saturation number of an n‐vertex star is quadratic in n, and the rainbow saturation number of any tree that is not a star is at most linear.     

Acyclic and star colorings of cographs

An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of star coloring requires that the union of any two color classes induces a disjoint collection of stars. We prove that every acyclic coloring of a cograph is also a star coloring and give a linear-time algorithm for finding an optimal acyclic and star coloring of a cograph. If the graph is given in the form of a cotree, the algorithm runs in O(n) time. We also show that the acyclic chromatic number, the star chromatic number, the treewidth plus 1, and the pathwidth plus 1 are all equal for cographs.     

Vertex-distinguishing proper edge-colorings

An edge-coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge-coloring of a simple graph G is denoted by . A simple count shows that where n_i denotes the number of vertices of degree i in G. We prove that where C is a constant depending only on Δ. Some results for special classes of graphs, notably trees, are also presented. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 73–82, 1997     

A Note on Adjacent Strong Edge Coloring of K（n,m）

In this paper, we prove that the adjacent strong edge chromatic number of a graph K（n,m） is n ＋ 1, with n ≥ 2, m ≥ 1.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.