Chromatic Number (chromatic + number)

Distribution by Scientific Domains


Selected Abstracts


Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function

JOURNAL OF GRAPH THEORY, Issue 1 2006
Claude Tardif
Abstract Let f(n),=,min{,(G,×,H),:,G and H are n -chromatic digraphs} and g(n),=,min{,(G,×,H),:,G and H are n -chromatic graphs}. We prove that f is bounded if and only if g is bounded. © 2005 Wiley Periodicals, Inc. J Graph Theory [source]


Subgraph-avoiding coloring of graphs

JOURNAL OF GRAPH THEORY, Issue 4 2010
Jia Shen
Abstract Given a "forbidden graph" F and an integer k, an F-avoiding k-coloring of a graph G is a k -coloring of the vertices of G such that no maximal F -free subgraph of G is monochromatic. The F-avoiding chromatic numberacF(G) is the smallest integer k such that G is F -avoiding k -colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that acF(G) , C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for acF(G) in terms of various invariants of G are also given. Particularly, we prove that , where n is the order of G and F is not Kk or . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300,310, 2010 [source]


Path homomorphisms, graph colorings, and boolean matrices

JOURNAL OF GRAPH THEORY, Issue 3 2010
Jaroslav Ne
Abstract We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path into some orientation of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path depends on the relation between the "algebraic length" and "derived algebraic length" of . This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 198,209, 2010 [source]


Proof of a conjecture on fractional Ramsey numbers

JOURNAL OF GRAPH THEORY, Issue 2 2010
Jason Brown
Abstract Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, ,, ak) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164,178, 2010 [source]


M -degrees of quadrangle-free planar graphs

JOURNAL OF GRAPH THEORY, Issue 1 2009
Oleg V. Borodin
Abstract The M-degree of an edge xy in a graph is the maximum of the degrees of x and y. The M-degree of a graph G is the minimum over M -degrees of its edges. In order to get upper bounds on the game chromatic number, He et al showed that every planar graph G without leaves and 4-cycles has M -degree at most 8 and gave an example of such a graph with M -degree 3. This yields upper bounds on the game chromatic number of C4 -free planar graphs. We determine the maximum possible M -degrees for planar, projective-planar and toroidal graphs without leaves and 4-cycles. In particular, for planar and projective-planar graphs this maximum is 7. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 80,85, 2009 [source]


A new upper bound on the cyclic chromatic number,

JOURNAL OF GRAPH THEORY, Issue 1 2007
O. V. Borodin
Abstract A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number ,c. Let ,* be the maximum face degree of a graph. There exist plane graphs with ,c = ,3/2 ,*,. Ore and Plummer [5] proved that ,c , 2, ,*, which bound was improved to ,9/5, ,*, by Borodin, Sanders, and Zhao [1], and to ,5/3,,*, by Sanders and Zhao [7]. We introduce a new parameter k*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that ,c , max {,* + 3,k* + 2, ,* + 14, 3, k* + 6, 18}, and if ,* , 4 and k* , 4, then ,c , ,* + 3,k* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory [source]


The last excluded case of Dirac's map-color theorem for choosability

JOURNAL OF GRAPH THEORY, Issue 4 2006
Daniel Král'
Abstract In 1890, Heawood established the upper bound on the chromatic number of every graph embedded on a surface of Euler genus , , 1. Almost 80 years later, the bound was shown to be tight by Ringel and Youngs. These two results have became known under the name of the Map-Color Theorem. In 1956, Dirac refined this by showing that the upper bound H(,) is obtained only if a graph G contains KH, as a subgraph except for three surfaces. Albertson and Hutchinson settled these excluded cases in 1979. This result is nowadays known as Dirac's Map-Color Theorem. Böhme, Mohar, and Stiebitz extended Dirac's Map-Color Theorem to the case of choosability by showing that G is (H(,) , 1)-choosable unless G contains KH(,) as a subgraph for , , 1 and , , 3. In the present paper, we settle the excluded case of , = 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 319,354, 2006 [source]


Improved bounds for the chromatic number of a graph

JOURNAL OF GRAPH THEORY, Issue 3 2004
S. Louis Hakimi
Abstract After giving a new proof of a well-known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres-Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge-cut (V1, V2) in a graph G, together with colorings of ,V1, and ,V2,, what is the least number of colors in a coloring of G which "respects" the colorings of ,V1, and ,V2, ? We give a constructive optimal solution of this problem, and use it to derive a new upper bound for the chromatic number of a graph. As easy corollaries, we obtain several interesting bounds which also appear to be new, as well as classical bounds of Dirac and Ore, and the above mentioned bounds of Matula and Szekeres-Wilf. We conclude by considering two algorithms suggested by our results. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 217,225, 2004 [source]


On the complexity of the circular chromatic number

JOURNAL OF GRAPH THEORY, Issue 3 2004
H. Hatami
Abstract Circular chromatic number, ,c is a natural generalization of chromatic number. It is known that it is NP -hard to determine whether or not an arbitrary graph G satisfies ,(G)=,c(G). In this paper we prove that this problem is NP -hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k,,,2 and n,,,3, for a given graph G with ,(G),=,n, it is NP -complete to verify if . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226,230, 2004 [source]


Size ramsey numbers of stars versus 4-chromatic graphs,

JOURNAL OF GRAPH THEORY, Issue 3 2003
Oleg PikhurkoArticle first published online: 31 JAN 200
Abstract We investigate the asymptotics of the size Ramsey number î(K1,nF), where K1,n is the n -star and F is a fixed graph. The author 11 has recently proved that r,(K1,n,F)=(1+o(1))n2 for any F with chromatic number ,(F)=3. Here we show that r,(K1,n,F), n2+o(n2), if , (F) , 4 and conjecture that this is sharp. We prove the case ,(F)=4 of the conjecture, that is, that r,(K1,n,F)=(4+o(1))n2 for any 4-chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220,233, 2003 [source]


Girth and fractional chromatic number of planar graphs

JOURNAL OF GRAPH THEORY, Issue 3 2002
Amir Pirnazar
Abstract In 1959, even before the Four-Color Theorem was proved, Grötzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fractional chromatic number of a planar graph with that girth, and we provide upper and lower bounds for this quantity. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 201,217, 2002; DOI 10.1002/jgt10024 [source]


Almost all graphs with high girth and suitable density have high chromatic number

JOURNAL OF GRAPH THEORY, Issue 4 2001
Deryk Osthus
Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all ,,,,3 and k , , there exist constants C1 and C2 so that almost all graphs on n vertices and m edges whose girth is greater than , have chromatic number at least k, provided that . © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 220,226, 2001 [source]


A branch-and-cut algorithm for partition coloring

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010
Yuri Frota
Abstract Let G = (V, E, Q) be a undirected graph, where V is the set of vertices, E is the set of edges, and Q = {Q1,,,Qq} is a partition of V into q subsets. We refer to Q1,,,Qq as the components of the partition. The partition coloring problem (PCP) consists of finding a subset V, of V with exactly one vertex from each component Q1,,,Qq and such that the chromatic number of the graph induced in G by V, is minimum. This problem is a generalization of the graph coloring problem. This work presents a branch-and-cut algorithm proposed for PCP. An integer programing formulation and valid inequalities are proposed. A tabu search heuristic is used for providing primal bounds. Computational experiments are reported for random graphs and for PCP instances originating from the problem of routing and wavelength assignment in all-optical WDM networks. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source]


Improper coloring of unit disk graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2009
Frédéric Havet
Abstract Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is k -improper if no more than k neighbors of every vertex have the same colour as that assigned to the vertex. The k -improper chromatic number ,k(G) is the least number of colors needed in a k -improper coloring of a graph G. The main subject of this work is analyzing the complexity of computing ,k for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing ,k for unit interval graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]


On some properties of suboptimal colorings of graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2004
Ivo Blöchliger
Abstract Starting from the trivial observation that, in any optimal coloring of a graph, there always exists a node v such that its neighborhood N(v) contains all colors, we examine related properties in suboptimal colorings (i.e., those using more than ,(G) colors, where ,(G) is the chromatic number). In particular, we show that, in any (,(G) + p)-coloring of G, there is a node v such that its generalized neighborhood Nq(v) with q = max{2p , 1, 2} contains ,(G) colors for p , 1. Additional properties of (,(G) + p)-colorings are also given. © 2004 Wiley Periodicals, Inc. [source]


Coloring H-free hypergraphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2010
Tom Bohman
Abstract Fix r , 2 and a collection of r -uniform hypergraphs . What is the minimum number of edges in an -free r -uniform hypergraph with chromatic number greater than k? We investigate this question for various . Our results include the following: An (r,l)-system is an r -uniform hypergraph with every two edges sharing at most l vertices. For k sufficiently large, there is an (r,l)-system with chromatic number greater than k and number of edges at most c(kr,1 log k)l/(l,1), where This improves on the previous best bounds of Kostochka et al. (Random Structures Algorithms 19 (2001), 87,98). The upper bound is sharp apart from the constant c as shown in (Random Structures Algorithms 19 (2001) 87,98). The minimum number of edges in an r -uniform hypergraph with independent neighborhoods and chromatic number greater than k is of order kr+1/(r,1) log O(1)k as k , ,. This generalizes (aside from logarithmic factors) a result of Gimbel and Thomassen (Discrete Mathematics 219 (2000), 275,277) for triangle-free graphs. Let T be an r -uniform hypertree of t edges. Then every T -free r -uniform hypergraph has chromatic number at most 2(r , 1)(t , 1) + 1. This generalizes the well-known fact that every T -free graph has chromatic number at most t. Several open problems and conjectures are also posed. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source]


The game chromatic number of random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2008
Tom Bohman
Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number ,g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph Gn,p. We show that with high probability, the game chromatic number of Gn,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]


Exact and approximative algorithms for coloring G(n,p)

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2004
Amin Coja-Oghlan
We investigate the problem of coloring random graphs G(n, p) in polynomial expected time. For the case p , 1.01/n, we present an algorithm that finds an optimal coloring in linear expected time. For p , ln6(n)/n, we give algorithms which approximate the chromatic number within a factor of O( ). We also obtain an O(/ln(np))-approximation algorithm for the independence number. As an application, we propose an algorithm for deciding satisfiability of random 2k -SAT formulas over n propositional variables with , ln7(n)nk clauses in polynomial expected time. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004 [source]


Proof of a tiling conjecture of Komlós

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2003
Ali Shokoufandeh
Abstract A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n -vertex graph of minimum degree at least (1 , (1/,cr(H)))n, where ,cr(H) denotes the critical chromatic number of H, then G contains an H -matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180,205, 2003 [source]