图的星边染色综述

重图G的星色指数是指对G的边进行正常染色使得没有长为4的路或圈是双色的所需的最小颜色数,记作x'st(G).本文对图的星色指数的结果做了一个总结,给出了一些有趣的证明和技巧,并收集了一些公开问题和猜想.     

Bipartite density of triangle-free subcubic graphs

A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is defined as b(G)=max{|E(B)|/|E(G)|:B is a bipartite subgraph of G}. It was conjectured by Bondy and Locke that if G is a triangle-free subcubic graph, then and equality holds only if G is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result.     

Strong list-chromatic index of subcubic graphs

A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by ${\chi }_s^{\prime }\left(G\right)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that ${\chi }_s^{\prime }\left(G\right)\le \frac{5}{4}\Delta {\left(G\right)}^2$, where $\Delta \left(G\right)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.     

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$).     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

Injective choosability of subcubic planar graphs with girth 6

An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ so that any two vertices with a common neighbor have distinct colors. A graph $G$ is injectively $k$-choosable if for any list assignment $L$, where $\left|L\left(v\right)\right|\ge k$ for all $v\in V\left(G\right)$, $G$ has an injective $L$-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.     

List neighbor sum distinguishing edge coloring of subcubic graphs

A proper $k$-edge-coloring of a graph with colors in $\{1,2,\dots ,k\}$ is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least $6$ vertices has an NSD edge coloring with at most $\Delta +2$ colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD $6$-edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vu?kovi?, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD $6$-edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD $6$-edge-coloring.     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

Adjacent Vertex Distinguishing Edge Coloring of Planar Graphs with Girth at Least 5北大核心CSCD

An adjacent vertex distinguishing edge-colorings of a graph G is a proper edge coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of color required for an adjacent vertex distinguishing edge-coloring of G is denoted by χa'(G). In this paper, we prove that if G is a planar graph with girth at least 5 and without isolated edges, then χa'(G)≤ max{8,Δ(G)+1}. © 2022, Chinese Academy of Sciences. All right reserved.     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

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

给定两个非负整数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。     

Colouring triangle-free intersection graphs of boxes on the plane

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3- and 2-degenerate, respectively. This implies that these graphs are 4- and 3-list-colourable, respectively.     

Injective colorings of sparse graphs

Let denote the maximum average degree (over all subgraphs) of G and let χ_i(G) denote the injective chromatic number of G. We prove that if , then χ_i(G)≤Δ(G)+1; and if , then χ_i(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χ_i(G)≤Δ(G)+1; similarly, if g(G)≥13, then χ_i(G)=Δ(G).