Equitable list coloring and treewidth

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most ?|V(G)|/k? vertices. A graph is equitably k ‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k>Δ(G). We prove this for graphs of treewidth w≤5 if also k≥3w?1. We also show that if G has treewidth w≥5, then G is equitably k‐choosable for k≥max{Δ(G)+w?4, 3w?1}. As a corollary, if G is chordal, then G is equitably k‐choosable for k≥3Δ(G)?4 when Δ(G)>2. © 2009 Wiley Periodicals, Inc. J Graph Theory     

On defected colourings of graphs

Abstract A k-edge-coloring f of a connected graph G is a （A1, A2, , A）-defected k-edge-coloring if there is a smallest integer/ with 1 _ /3 _〈 k - i such that the multiplicity of each color j E {1,2,... ,/3} appearing at a vertex is equal to Aj _〉 2, and each color of {/3 -}- 1,/3 - 2, - , k} appears at some vertices at most one time. The （A1, A2,, A/）-defected chromatic index of G, denoted as X （A1, A2,, A/; G）, is the smallest number such that every （A1,A2,-.., A/）-defected t-edge-coloring of G holds t _〉 X（A1, A2 A;; G）. We obtain A（G） X（A1, ）2, , A/; G） ＋ -- （Ai - 1） _〈 /k（G） 1, and introduce two new chromatic indices of G i=1 as： the vertex pan-biuniform chromatic index X pb （G）, and the neighbour vertex pan-biuniform chromatic index Xnpb（G）, and furthermore find the structure of a tree T having X pb （T） =1.     

The Adaptable Chromatic Number and the Chromatic Number

We prove that the adaptable chromatic number of a graph is at least asymptotic to the square root of the chromatic number. This is best possible.     

Coloring graphs from lists with bounded size of their union

A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 2^4k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The adaptable choosability number grows with the choosability number

The adaptable choosability number of a multigraph G, denoted ch_a(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that ch_a grows with ch, i.e. there is a function f tending to infinity such that ch_a(G)≥f(ch(G)).     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

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.     

最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

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

一些图的邻点可区别关联着色

在图的关联着色概念的基础上定义了图的邻点可区别关联着色及邻点可区别关联色数,研究了圈、完全二部图、Cm.Fn图的邻点可区别关联着色,并确定了它们的邻点可区别关联色数.     

Dynamic choosability of triangle‐free graphs and sparse random graphs

Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have .     

On some colorings of a double graph

In this note, we present some results concerning the chromatic index, the total chromatic index, the adjacent vertex distinguishing chromatic index and the adjacent vertex distinguishing total chromatic index for double graphs. In particular, we study the double graphs of class 1 and of type 1.     

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

Sum choice numbers of some graphs

Let f be a function assigning list sizes to the vertices of a graph G. The sum choice number of G is the minimum ∑_v∈V(G)f(v) such that for every assignment of lists to the vertices of G, with list sizes given by f, there exists proper coloring of G from the lists. We answer a few questions raised in a paper of Berliner, Bostelmann, Brualdi, and Deaett. Namely, we determine the sum choice number of the Petersen graph, the cartesian product of paths , and the complete bipartite graph K_3,n.     

Graphs of degree 4 are 5-edge-choosable

It is shown that every simple graph with maximal degree 4 is 5-edge-choosable. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 250–264, 1999