点染色3-边划分图的最小度(英文)

Addrio-Berry L[1]已经证明了最小度至少为1000的图可以点染色3-边划分,在本文中,我们将其结果改进到了最小度至少为662.     

关于图P_n~k的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的.     

Coloring of Plane Graphs with Unique Maximal Colors on Faces

The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven.     

图的Smarandachely邻点边色数的界

对图G的一个k-正常变染色法f,若图G中任意相邻两点的相邻边色集合互相不包含,那么称f为图G的一个k-Smarandachely邻点边染色(简记为k-SEC),而最小的正整数k称为图G的Smarandachely邻点边色数.尝试应用Lovasz局部引理来得到了Smarandachely邻点边色数的上界.     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

图M（Pn）和M（Gn）的点可区别均匀边染色

用构造法研究了路和圈的Mycielski图的点可区别均匀边染色,得到了路和圈的Mycielski图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想（VDEECC）．     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

完全二部图的广义Mycielski图的全染色与边染色

为了找到Km,n图的广义Mycielski图的全色数与边色数,用分析的方法,考虑不同情况,给出了它的全染色法与边染色法,得到了它的全色数与边色数.     

Clique-cutsets beyond chordal graphs

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (eg, the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. Furthermore, we obtain polynomial -bounding functions for these classes.     

广义Peterson图的邻点可区别的全染色

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

图的邻点可区别无圈边染色的一个界

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.应用概率的方法得到了图G的一个邻点可区别无圈边色数的上界,其中图G为无孤立边的图.     

星和完全等二部图联图的点可区别均匀边染色

研究了星与完全等二部图的联图Sm∨Kn,n的点可区别均匀边染色。     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

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.     

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

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

Optimization problems in multiple subtree graphs

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.     

Tutorial on Surrogate Constraint Approaches for Optimization in Graphs

Surrogate constraint methods have been embedded in a variety of mathematical programming applications over the past thirty years, yet their potential uses and underlying principles remain incompletely understood by a large segment of the optimization community. In a number of significant domains of combinatorial optimization, researchers have produced solution strategies without recognizing that they can be derived as special instances of surrogate constraint methods. Once the connection to surrogate constraint ideas is exposed, additional ways to exploit this framework become visible, frequently offering opportunities for improvement.We provide a tutorial on surrogate constraint approaches for optimization in graphs, illustrating the key ideas by reference to independent set and graph coloring problems, including constructions for weighted independent sets which have applications to associated covering and weighted maximum clique problems. In these settings, the surrogate constraints can be generated relative to well-known packing and covering formulations that are convenient for exposing key notions. The surrogate constraint approaches yield widely used heuristics for identifying independent sets as simple special cases, and also afford previously unidentified heuristics that have greater power in these settings. Our tutorial also shows how the use of surrogate constraints can be placed within the context of vocabulary building strategies for independent set and coloring problems, providing a framework for applying surrogate constraints that can be used in other applications.At a higher level, we show how to make use of surrogate constraint information, together with specialized algorithms for solving associated sub-problems, to obtain stronger objective function bounds and improved choice rules for heuristic or exact methods. The theorems that support these developments yield further strategies for exploiting surrogate constraint relaxations, both in graph optimization and integer programming generally.