Linear Coloring of Planar Graphs Without 4-Cycles

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that if G is a planar graph without 4-cycles, then lc ${(G)\le \lceil \frac {\Delta}2\rceil+8}$ , where Δ denotes the maximum degree of G.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

赋权图的圆染色与区间染色

赋权图的区间染色的定义与赋权图的圆染色的定义非常类型,唯一的区别就是将Ｇ的顶点对应圆周上的孤换为Ｇ的顶点对应区间上的子区间,讨论了赋权的圆染色与区染色的关系。     

Sum List Coloring Block Graphs

A graph is f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. We characterize f-choosable functions for block graphs (graphs in which each block is a clique, including trees and line graphs of trees). The sum choice number is the minimum over all choosable functions f of the sum of the sizes in f. The sum choice number of any graph is at most the number of vertices plus the number of edges. We show that this bound is tight for block graphs.Acknowledgments. Partially supported by a grant from the Reidler Foundation. The author would like to thank an anonymous referee for useful comments.     

Additive Coloring of Planar Graphs

An additive coloring of a graph G is an assignment of positive integers \({\{1,2,\ldots ,k\}}\) to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by \({\eta (G)}\) . We prove that \({\eta (G) \, \leqslant \, 468}\) for every planar graph G. This improves a previous bound \({\eta (G) \, \leqslant \, 5544}\) due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that \({\eta (G) \, \leqslant \, 36}\) for 3-colorable planar graphs, and \({\eta (G) \, \leqslant \, 4}\) for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each \({r \, \geqslant \, 2}\) there is an r-chromatic graph G _r with no additive coloring by elements of any abelian group of order r.     

Coloring Fuzzy Circular Interval Graphs

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs.The problem is NP-complete for quasi-line graphs. For the subclass of fuzzy circular interval graphs however, one can compute the weighted coloring number in polynomial time using recent results of Chudnovsky and Ovetsky and of King and Reed. Whether one could actually compute an optimal weighted coloring of a fuzzy circular interval graph in polynomial time however was still open.We provide a combinatorial algorithm that computes weighted colorings and the weighted coloring number for fuzzy circular interval graphs efficiently. The algorithm reduces the problem to the case of circular interval graphs, then making use of an algorithm by Gijswijt to compute integer decompositions.     

蛛网图及渔网图的邻点可区别I-全染色

通过揭示完全蛛网图和渔网图的结构特点,研究了它们的邻点可区别I-全染色问题,并运用构造法给出了其邻点可区别I-全染色,从而获得了它们的邻点可区别I-全色数.     

Edge Coloring of Split Graphs

A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. This paper presents new results about the classification problem for split graphs as a contribution in the direction of solving the entire problem for this class.     

Coloring of Double Disk Graphs

We study the problem of minimizing the number of colors for vertex-coloring of double disk graphs and in this note, show a polynomial-time 31-approximation for the problem, which improves an existing result.     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

若干Mycielski图的均匀染色

如果图G的一个正常顶点染色满足任两个色类中的顶点数相差不超过1,则称为G的均匀染色.研究了一些Mycielski图的均匀染色,给出了路、圈、完全图和广义星图的Mycielski图的均匀色数.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

1—外平面图的边面全色数

一个平面图Ｇ被称为１－外平面图如果存在一个顶点ｕ 使得Ｇ－ ｕ 是一个外平面图．本文证明了Ｍｅｌｎｉｋｏｖ 的边面染色猜想对所有１－外平面图成立．     

阿基米德图的面唯一极大染色

给定平面图G的一个正常κ-顶点染色φ:V(G)→{1,2,…,κ},若对G的每个面f,与f关联的顶点所染颜色的极大颜色在与f关联的顶点中仅出现一次,则称φ是图G的面唯一极大κ-染色.图G存在面唯一极大κ-染色的κ的最小值称为G的面唯一极大色数,记作χfum(G).本文研究了阿基米德图的面唯一极大色数,证得若图G是阿基米德图,则χfum(G)=4.     

关于图的3-条件色数

For integers k0,r0,a(k,r)-coloring of a graph G is a proper k-coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min{d,r}diferent colors.The r-hued chromatic number,denoted byχr(G),is the smallest integer k for which a graph G has a(k,r)-coloring.Define a graph G is r-normal,ifχr(G)=χ(G).In this paper,we present two sufcient conditions for a graph to be 3-normal,and the best upper bound of 3-hued chromatic number of a certain families of graphs.     

Relaxed Locally Identifying Coloring of Graphs

A locally identifying coloring (lid-coloring) of a graph is a proper vertex-coloring such that the sets of colors appearing in the closed neighborhoods of any pair of adjacent vertices having distinct neighborhoods are distinct. Our goal is to study a relaxed locally identifying coloring (rlid-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessarily proper. We denote by \(\chi _{rlid}(G)\) the minimum number of colors used in a relaxed locally identifying coloring of a graph G. In this paper, we prove that the problem of deciding that \(\chi _{rlid}(G)=3\) for a 2-degenerate planar graph G is NP-complete and for a bipartite graph G is polynomial. We give several bounds of \(\chi _{rlid}(G)\) for different families of graphs and construct new graphs for which these bounds are tight. We also compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph G (\(\chi _{lid}(G)\)), the size of a minimum identifying code of G (\(\gamma _{id}(G)\)) and the chromatic number of G (\(\chi (G)\)).     

Coloring Graphs with Constraints on Connectivity

A graph G has maximal local edge‐connectivity k if the maximum number of edge‐disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks‐type theorems for k‐connected graphs with maximal local edge‐connectivity k, and for any graph with maximal local edge‐connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial‐time algorithm that, given a 3‐connected graph G with maximal local connectivity 3, outputs an optimal coloring for G. On the other hand, we prove, for , that k‐colorability is NP‐complete when restricted to minimally k‐connected graphs, and 3‐colorability is NP‐complete when restricted to ‐connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k‐colorability based on the number of vertices of degree at least , and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.