Planar graphs without 4-cycles and close triangles are (2, 0, 0)-colorable

For a set of nonnegative integers \(c_1, \ldots , c_k\), a \((c_1, c_2,\ldots , c_k)\)-coloring of a graph G is a partition of V(G) into \(V_1, \ldots , V_k\) such that for every i, \(1\le i\le k, G[V_i]\) has maximum degree at most \(c_i\). We prove that all planar graphs without 4-cycles and no less than two edges between triangles are (2, 0, 0)-colorable.     

A sufficient condition for planar graphs to be (3, 1)-choosable

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying \(|L(x)\cap L(y)|\le d\) for each edge xy. An L-coloring is a vertex coloring \(\pi \) such that \(\pi (v) \in L(v)\) for each vertex v and \(\pi (x) \ne \pi (y)\) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4- and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5- and 6-cycles are (3, 1)-choosable.     

Packing 5-cycles into balanced complete m-partite graphs for odd m

Let be a complete m-partite graph with partite sets of sizes n ₁,n ₂,…,n _m . A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K _m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K _m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research of M.-H.W. was supported by NSC 93-2115-M-264-001.     

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.     

A new sufficient condition for a tree T to have the (2, 1)-total number $$\Delta +1$$

A k-(2, 1)-total labelling of a graph G is a mapping \(f: V(G)\cup E(G)\rightarrow \{0,1,\ldots ,k\}\) such that adjacent vertices or adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least 2. The (2, 1)-total number, denoted \(\lambda _2^t(G)\), is the minimum k such that G has a k-(2, 1)-total labelling. Let T be a tree with maximum degree \(\Delta \ge 7\). A vertex \(v\in V(T)\) is called major if \(d(v)=\Delta \), minor if \(d(v)<\Delta \), and saturated if v is major and is adjacent to exactly \(\Delta - 2\) major vertices. It is known that \(\Delta + 1 \le \lambda _2^t(T)\le \Delta + 2\). In this paper, we prove that if every major vertex is adjacent to at most \(\Delta -2\) major vertices, and every minor vertex is adjacent to at most three saturated vertices, then \(\lambda _2^t(T) = \Delta + 1\). The result is best possible with respect to these required conditions.     

What now? Cremation without tradition

Although cremation is an increasingly popular method of body disposal, there is little research on ash disposition, particularly the decisions and negotiations underlying the process. Americans who have recently encountered the cremation of loved ones for the first time have not been studied at all; the present research describes 87 of their cremation experiences. Adults who were actively involved in cremation and ash disposition decisions were interviewed about these processes at every stage, from the decision to cremate through the performance of final rituals for their dead. Results detail family and friends' active negotiations over cremation and ash disposition, the surprises they encountered, and the personally meaningful rituals they created for their loved ones. As in other emerging postdeath rituals, the enactment of individualized rituals for the dead was seen as a positive experience; accordingly, most participants preferred to be cremated and honored through nontraditional rituals themselves.     

Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

On irreducible no-hole <Emphasis Type="Italic">L</Emphasis>(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping \(f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}\) such that \(|f(u)-f(v)|\ge 2\) for all edges uv of G, and \(|f(u)-f(v)|\ge 1\) if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by \(\lambda (G)\), is min {span \(f: f\text {is an }L(2,1)\text {-coloring of } G\}\). If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if \(l\in (0,k)\) and there is no vertex v in G such that \(f(v)=l\). A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from \(\{0,1,\ldots ,k\}\), for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by \(\lambda _{inh}(G)\), is defined as \(\lambda _{inh}(G)=\min ~\{\)span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to \(\mathbb {N}\), the h-subdivision of G, denoted by \(G_{(h)}\), is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that \(G_{(h)}\) is inh-colorable for \(h(e)\ge 2\), \(e\in E(G)\), except the case \(\Delta =3\) and \(h(e)=2\) for at least one edge but not for all. Moreover we find the exact value of \(\lambda _{inh}(G_{(h)})\) in several cases and give upper bounds of the same in the remaining.     

On the <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling conjecture for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices u and v in G. An L(2, 1)-labeling of G is a function \(f: V \rightarrow \{0,1,\ldots \}\) such that for any two vertices u and v, \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of f is the difference between the largest and the smallest number in f(V). The \(\lambda \)-number \(\lambda (G)\) of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the \(\lambda \)-number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716–736, 2013).     

Planning without vision— Roots of the urban disaster

Urban planning, especially in the United States, arose in reaction to the forces of industrialization. Yet urban development remained subordinate to the deeper powers of the rising technological order and failed to find an independent inspiration, ideal, or initiative by which cities could integrate the bewildering social changes. A kind of self-defeat is proclaimed in the very language of planning. How did this happen? Even to begin to perceive the causes, it is necessary to search in the history, philosophy, and customs of the society within which urban planning emerged.     

Online integrated production–distribution scheduling problems without preemption

We study an integrated production–distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given.     

Overcoming the liability of foreignness without strong firm capabilities — the value of market-based resources

The concept of “liability of foreignness” — the costs of doing business abroad — has been known and discussed since the mid-1970s. At the core of these discussions is the role that firm capabilities play in overcoming or limiting these costs. This raises the question of how firms with inappropriate, limited or constrained capabilities relative to their host environment overcome the liability of foreignness. This paper focuses on the subsidiaries of “emerging multinationals” and how they manage the demands of a technologically and economically highly developed host country. A host location with sophisticated markets and well-developed institutional infrastructure may be a highly challenging environment for firms that have grown their organizational capabilities in less developed contexts. This paper explores that situation and considers how resources available on the market — for example through supplier inputs — assist subsidiaries to benefit from their presence in a munificent location. Despite the acknowledged limitations of a transaction-based approach, this paper presents evidence that purchasing knowledge provides an accessible strategy for overcoming some liabilities of foreignness.     

1 1的答案

都市的下午,你在路上随机地找人发问,请他说出1 1的答案,谁都直觉地认为是个无聊粗俗的文字游戏,而想找到一个令你失望的答案:为了证明自己不是白痴,答案是2的可     

1对1激活营销

所有的顾客并非天生平等,他们贡献给企业不同的价值。为何要一样对待最忠实、最有利的顾客和那些勉强收回服务成本的顾客?当今的顾客也有不同的需求,他们要求被单独对待,而且他们也应该受到这种礼遇。正是这些差异导致了顾客消费行为之间形形色色的不同口味。所有企业都必须清醒认识到这些差异,并立即着手处理这些     

农民1毛1斤没人要,市民1块1斤买不来

农民的白菜一毛钱一斤没人要,市场的白菜卖价却超过一块钱一斤。连日来,黑龙江、河北、河南等多地蔬菜滞销,而与之形成巨大反差的是,市民“菜篮子”菜价居高难下。一方面是“菜贱伤农”,另一方面是“菜贵民忧”,怪圈频现的背后,是小农户与大市场的不适应,以及政府“有形手”和市场“无形手”调控的错位。     

1对1模式的效率

目前还没有哪个人才网上有这样系统的个性化服务,而且界面非常友好,评价一个网站也不能仅凭点击率,更看成交率高不高,雅虎和深圳希捷尔人力资源有限公司双手握在了一起     

"1+1+1"管理模式的创建与实践

建立比较完善的现代企业制度，其中要件之一就是要求达到管理科学。从我们中铁 16局二处兵改工到转轨建制的实际出发，我们推出了“ 1＋ 1＋ 1”管理模式，应用数量化的方法，通过运筹学的模型来为决策者提供解决问题的一个方案。用“ 1＋ 1＋ 1”不代替现实情况，就是在一个目标系统基础上建立以经济责任指标为主体、项目管理模式为对象、责任成本控制为手段，逐步向项目法施工推进的一种决策框架。 一、实行“ 1＋ 1＋ 1”管理模式是企业深化改革、自我完善、自我发展的客观需要 作为国有大中型施工企业，我处自 1984年“兵改工”以来，经…     

"1+1"上新台阶

在美国的得克萨斯州,一家名叫"东方咖啡"的饭店以其与众不同的经营方式吸引着大批游客,生意十分火爆.它的独特之处在于两个方面::一是向顾客提供的是饭店自己种植的蔬菜和水果,从来不会打农药灭虫,新鲜干净,符合环保要求,堪称绿色食品;二是顾客可以走到菜园里面散散心,看一看盘中的食物是怎样长出来的.     

A note on (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling of graphs

Let \(G=(V, E)\) be a graph. For two vertices u and v in G, we denote \(d_G(u, v)\) the distance between u and v. A vertex v is called an i-neighbor of u if \(d_G(u,v)=i\). Let s, t and k be nonnegative integers. An (s, t)-relaxed k-L(2, 1)-labeling of a graph G is an assignment of labels from \(\{0, 1, \ldots , k\}\) to the vertices of G if the following three conditions are met: (1) adjacent vertices get different labels; (2) for any vertex u of G, there are at most s 1-neighbors of u receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex u of G, the number of 2-neighbors of u assigned the label f(u) is at most t. The (s, t)-relaxed L(2, 1)-labeling number \(\lambda _{2,1}^{s,t}(G)\) of G is the minimum k such that G admits an (s, t)-relaxed k-L(2, 1)-labeling. In this article, we refute Conjecture 4 and Conjecture 5 stated in (Lin in J Comb Optim. doi: 10.1007/s10878-014-9746-9, 2013).     

1-(-1)的奥妙

数学这门科学,有人把它誉之为探索自然秘密、打开科学宝库的“一把钥匙”。恩格斯曾指出:“数学:辩证的辅助工具和表现方式”。(《自然辩证法》人民出版社1971年版,第3页)在社会生活中,人们用数学表示某种哲理的事例比比皆是。比如,爱因斯坦曾列过一个数学公式:A=x+y+z。他解释“A”代表成功,“x”代表艰苦劳动,“y”代表正确