Search

We analyze the problem of majority sentiment detection in Online Social Networks (OSN), and relate the detection error probability to the underlying graph of the OSN. Modeling the underlying social network as an Ising Markov random field prior based on a given graph, we show that in the case of the empty graph (independent sentiments) and the chain graph, the detection is always inaccurate, even when the number of users grow to infinity. In the case of the complete graph, the detection is inaccurate if the connection strength is below a certain critical value, while it is asymptotically accurate if the strength is above that critical value, which is analogous to the phase transition phenomenon in statistical physics.

The imperfection ratio is a graph invariant which indicates how good a lower bound the weighted clique number gives on the weighted chromatic number, in the limit as weights get large. Its introduction was motivated by investigations of the radio channel assignment problem, where one has to assign channels to transmitters and the demands for channels at some transmitters are large. In this paper we show that the imperfection ratio behaves multiplicatively under taking the lexicographic product, which permits us to identify its possible values, investigate its extremal behaviour and its behaviour on random graphs, explore three upper bounds, and show that it is NP-hard to determine. © 2001 Academic Press.

We develop further the new versions of quantum chromatic numbers of graphs introduced by the first and fourth authors. We prove that the problem of computation of the commuting quantum chromatic number of a graph is solvable by an SDP algorithm and describe an hierarchy of variants of the commuting quantum chromatic number which converge to it. We introduce the tracial rank of a graph, a parameter that gives a lower bound for the commuting quantum chromatic number and parallels the projective rank, and prove that it is multiplicative. We describe the tracial rank, the projective rank and the fractional chromatic numbers in a unified manner that clarifies their connection with the commuting quantum chromatic number, the quantum chromatic number and the classical chromatic number, respectively. Finally, we present a new SDP algorithm that yields a parameter larger than the Lov\'asz number and is yet a lower bound for the tracial rank of the graph. We determine the precise value of the tracial rank of an odd cycle., Comment: 34 pages; v2 has improved presentation based after referees' comments, published version

An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems.

In this paper, we present an algorithm to approximate the chromatic number of a graph. The proposed approach initially removes even cycles and acyclic subgraphs, this process is called debugging, later to colour the remaining graph, we present a strategy to obtain maximal independent sets. We experimentally show that our proposal improves the results compare to JGraphT and Sage which contain a module for computing the chromatic number of a graph.

A connected graph G with chromatic number t is double-critical if G ∖ { x , y } is ( t − 2 ) -colorable for each edge x y ∈ E ( G ) . The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of Erdős and Lovasz from 1966, which is referred to as the Double-Critical Graph Conjecture, states that there are no other double-critical graphs. That is, if a graph G with chromatic number t is double-critical, then G is the complete graph on t vertices. This has been verified for t ≤ 5 , but remains open for t ≥ 6 . In this paper, we first prove that if G is a non-complete, double-critical graph with chromatic number t ≥ 6 , then no vertex of degree t + 1 is adjacent to a vertex of degree t + 1 , t + 2 , or t + 3 in G . We then use this result to show that the Double-Critical Graph Conjecture is true for double-critical graphs G with chromatic number t ≤ 8 if G is claw-free.

A graph is called an edge uncertain graph if the edges are not deterministic but exist with some belief degrees described by uncertain measure. A new definition for total uncertain graph is first introduced in this paper, that is an uncertain graph in which the vertices and the edges are not deterministic. Further, we give a concept of an α-cut of a total uncertain graph and investigate some of its properties. We color a total uncertain graph via the α-cut, and obtain α-cut chromatic numbers for all α ∈ [0, 1]. Some properties of the α-cut chromatic number are also verified.

The domination number of a graph $G$, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set of $G$. A vertex of a graph is called critical if its deletion decreases the domination number, and a graph is called critical if its all vertices are critical. A graph $G$ is called weak bicritical if for every non-critical vertex $x\in V(G)$, $G-x$ is a critical graph with $\gamma (G-x)=\gamma (G)$. In this paper, we characterize the connected weak bicritical graphs $G$ whose diameter is exactly $2\gamma (G)-2$. This is a generalization of some known results concerning the diameter of graphs with a domination-criticality., Comment: 13 pages, 0 figures

Uncertain graphs are prevalent in several applications including communications systems, biological databases, and social networks. The ever increasing size of the underlying data renders both graph storage and query processing extremely expensive. Sparsification has often been used to reduce the size of deterministic graphs by maintaining only the important edges. However, adaptation of deterministic sparsification methods fails in the uncertain setting. To overcome this problem, we introduce the first sparsification techniques aimed explicitly at uncertain graphs. The proposed methods reduce the number of edges and redistribute their probabilities in order to decrease the graph size, while preserving its underlying structure. The resulting graph can be used to efficiently and accurately approximate any query and mining tasks on the original graph. An extensive experimental evaluation with real and synthetic datasets illustrates the effectiveness of our techniques on several common graph tasks, including clustering coefficient, page rank, reliability, and shortest path distance.

Kostochka and Yancey proved that every 5-critical graph G satisfies: |E(G)|>= (9/4)|V(G)| - 5/4. A construction of Ore gives an infinite family of graphs meeting this bound. We prove that there exists e,d > 0 such that if G is a 5-critical graph, then |E(G)| >= (9/4 + e)|V(G)|- 5/4 - dT(G), where T(G) is the maximum number of vertex-disjoint cliques of size three or four where cliques of size four have twice the weight of a clique of size three. As a corollary, a triangle-free 5-critical graph G satisfies: |E(G)|>=(9/4 + e)|V(G)| - 5/4., 25 pages, revised according to referee comments

My favorite graph theory conjectures involve the effects of edge removal on the diameter of a graph and the effects of edge addition on the domination and total domination numbers of a graph. Loosely speaking, “criticality” means that the value of the parameter in question always changes under the graph modification. This chapter presents five conjectures concerning criticality, namely, a conjecture by Sumner and Blitch on the criticality of domination upon edge addition, a conjecture by Murty and Simon on the criticality of diameter upon edge removal, and three conjectures on the criticality of total domination upon edge addition. These last three conjectures involving total domination are closely related, and surprisingly, a solution to one of them would provide a solution to the Murty-Simon Conjecture on diameter.

Let γ t ( G ) denote the total domination number of the graph G . The graph G is said to be total domination edge critical, or simply γ t ( G ) -critical, if γ t ( G + e ) < γ t ( G ) for each e ? E ( G ? ) . We show that any γ t ( G ) -critical graph G with γ t ( G ) ? 5 has at most γ t ( G ) - 2 leaves, and characterize those γ t -critical graphs G having exactly γ t ( G ) - 2 leaves. We also constructively establish the existence (with one exception) of h -critical graphs G with k leaves, where k is any nonnegative integer at most h - 2 . Finally, we characterize the γ t -critical unicyclic graphs.

We extend results about critically k -colorable graphs to choosability and paintability (list colorability and on-line list colorability). Using a strong version of Brooks’ Theorem, we generalize Gallai’s Theorem about the structure of the low-degree subgraph of critically k -colorable graphs, and introduce a more adequate lowest-degree subgraph. We prove lower bounds for the edge density of critical graphs, and generalize Heawood’s Map-Coloring Theorem about graphs on higher surfaces to paintability. We also show that on a fixed given surface, there are only finitely many critically k -paintable/ k -choosable/ k -colorable graphs, if k ≥ 6 . In this situation, we can determine in polynomial time k -paintability, k -choosability and k -colorability, by giving a polynomial time coloring strategy for “Mrs. Correct”. Our generalizations of k -choosability theorems also concern the treatment of non-constant list sizes (non-constant k ). Finally, we use a Ramsey-type lemma to deduce all 2-paintable, 2-choosable, critically 3-paintable and critically 3-choosable graphs, with respect to vertex deletion and to edge deletion.

The star chromatic index χs′(G) 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 Δ=Δ(G). Our best lower bound on χs′ in terms of Δ is 2Δ(1+o(1)) 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.

Submitted by Domingos Cardoso (dcardoso@ua.pt) on 2015-02-23T12:34:51Z No. of bitstreams: 1 CardosoSilvaSzymanski2012.pdf: 171493 bytes, checksum: 728aad06b0b6ed4e732ce16a4c81301e (MD5) Approved for entry into archive by Rita Goncalves(ritaisabel@ua.pt) on 2015-02-23T17:43:28Z (GMT) No. of bitstreams: 1 CardosoSilvaSzymanski2012.pdf: 171493 bytes, checksum: 728aad06b0b6ed4e732ce16a4c81301e (MD5) Made available in DSpace on 2015-02-23T17:43:28Z (GMT). No. of bitstreams: 1 CardosoSilvaSzymanski2012.pdf: 171493 bytes, checksum: 728aad06b0b6ed4e732ce16a4c81301e (MD5) Previous issue date: 2012-04

A total dominating set of a graph G = ( V , E ) with no isolated vertex is a set S ? V such that every vertex is adjacent to a vertex in S . The minimum cardinality of a total dominating set of G is the total domination number γ t ( G ) of G . Let k ? 3 be an integer. A graph G with no isolated vertex is k - γ t -vertex critical if γ t ( G ) = k and γ t ( G - v ) < k for every vertex v of G that is not adjacent to a vertex of degree one. In this note we study 3- γ t -vertex critical graphs of diameter three. We prove that such graphs have order at least 10, and we characterize all 3- γ t -vertex critical graphs of order 10. Moreover, we show that for every even number n ? 10 , there is a 3- γ t -vertex critical graph of order n .

A max-plus matrix $A$ is called weakly stable if the sequence (orbit) $x,A\otimes x,A^{2}\otimes x,\ldots$ does not reach an eigenvector of $A$ for any $x$ unless $x$ is an eigenvector. This is in contrast to previously studied strongly stable (robust) matrices for which the orbit reaches an eigenvector with any nontrivial starting vector. Max-plus matrices are used to describe multiprocessor interactive systems for which reachability of a steady regime is equivalent to reachability of an eigenvector by a matrix orbit. We prove that an irreducible matrix is weakly stable if and only if its critical graph is a Hamiltonian cycle in the associated graph. We extend this condition to reducible matrices. These criteria can be checked in polynomial time.

A graph G is said to be 3-domination critical if its domination number γ(G) = 3 and γ(G + e) = 2 for any edge e not contained in G. In this paper we first establish some structural properties of 3-domination critical graphs with diameter equal to 3. In particular, this allows us to characterize a special family of 3-domination critical graphs which contains those with minimum degree one. Moreover, we show that if the minimum degree of a 3-domination critical graph G is at least 3, then α(G) ≤ κ(G) + 1 or G is superconnected, where α(G) is the independence number and κ(G) is the vertex-connectivity of G.

We study extremal graphs for the extremal values of the second largest Q-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest Q-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k ? 3 and diameter d and if G has no critical vertices, then d ≤ 2k?3.

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P 4 -tidy graphs and ( q , q − 4 )-graphs, for every fixed q. These classes include cographs, P 4 -sparse and P 4 -lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of ( q , q − 4 )-graphs. All these coloring problems are known to be NP-hard for general graphs.

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.

We consider graph densities in countably inflnite graphs. The independence density of a flnite graph G of order n is its proportion of independent sets to all subsets of vertices, while the chromatic density is its proportion of proper n-colourings to all mappings from vertices of G to f1;2;:::;ng. For both densities, we extend their deflnition to countable graphs via limits of chains of flnite graphs. We show that independence densities exist for all chains, and are unique regardless of which limiting chain is used. We prove that independence densities are always rational; in fact, the closure of the set of possible values is contained in the rationals. In contrast, we show that the inflnite random graph contains chains realizing all real numbers in [0;1] as a chromatic density.

A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge-Δ-critical if χ′(G−e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge-Δ-critical graph of order n is less than **image**. For large Δ, this improves on the best bound previously known, which was roughly **image**; the bound conjectured by Vizing, which would be best possible, is **image**. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98-103, 2011 © 2011 Wiley Periodicals, Inc.

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by ? pr (G), is the minimum cardinality of a paired dominating set of G. A graph with no isolated vertex is called paired domination vertex critical, or briefly ? pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, ? pr (G?v) pr (G). A ? pr -critical graph G is said to be k-? pr -critical if ? pr (G)=k. In this paper, we firstly show that every 4-? pr -critical graph of even order has a perfect matching if it is K 1,5-free and every 4-? pr -critical graph of odd order is factor-critical if it is K 1,5-free. Secondly, we show that every 6-? pr -critical graph of even order has a perfect matching if it is K 1,4-free.

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of ``topologically t-chromatic'' graphs. We show that this minimum for large enough t-chromatic Schrijver graphs and t-chromatic generalized Mycielski graphs of appropriate parameters is the upper integer part of t/4+1., Comment: 18 pages

A graph has thickness t if the edges can be decomposed into t and no fewer planar layers. We study one aspect of a generalization of Ringel's famous Earth-Moon problem: what is the largest chromatic number of any thickness-2 graph? In particular, given a graph G we consider the r-inflation of G and find bounds on both the thickness and the chromatic number of the inflated graphs. In some instances, the best possible bounds on both the chromatic number and thickness are achieved. We end with several open problems.

The dramatic proliferation of sophisticated networks has resulted in a growing need for supporting effective querying and mining methods over such large-scale graph-structured data. At the core of many advanced network operations lies a common and critical graph query primitive: how to search graph structures efficiently within a large network? Unfortunately, the graph query is hard due to the NP-complete nature of subgraph isomorphism. It becomes even challenging when the network examined is large and diverse. In this paper, we present a high performance graph indexing mechanism, SPath, to address the graph query problem on large networks. SPath leverages decomposed shortest paths around vertex neighborhood as basic indexing units, which prove to be both effective in graph search space pruning and highly scalable in index construction and deployment. Via SPath, a graph query is processed and optimized beyond the traditional vertex-at-a-time fashion to a more efficient path-at-a-time way: the query is first decomposed to a set of shortest paths, among which a subset of candidates with good selectivity is picked by a query plan optimizer; Candidate paths are further joined together to help recover the query graph to finalize the graph query processing. We evaluate SPath with the state-of-the-art GraphQL on both real and synthetic data sets. Our experimental studies demonstrate the effectiveness and scalability of SPath, which proves to be a more practical and efficient indexing method in addressing graph queries on large networks.

A vertex subset S of a graph G = (V, E) is a double dominating set for G if |N[v]∩S| ≥ 2 for each vertex v ∈ V, where N[v] = {u |uv ∈ E}∪{v}. The double domination number of G, denoted by γ×2(G), is the cardinality of a smallest double dominating set of G. A graph G is said to be double domination edge critical if γ×2(G + e) < γ×2(G) for any edge e ∉ E. A double domination edge critical graph G with γ×2(G) = k is called k - γ×2(G)-critical. In this paper, we first show that G has a perfect matching if G is a connected 3 - γ×2(G)-critical graph of even order. Secondly, we show that G is factor-critical if G is a connected 3 - γ×2(G)-critical graph with odd order and minimum degree at least 2. Finally, we show that G is factor-critical if G is a connected K1,4-free 4 - γ×2(G)-critical graph of odd order with minimum degree at least 2.

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product K"[email protected]?K"n is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.

Let G be a graph with vertex set V(G). For any [email protected]?V(G) we use @w(G-S) to denote the number of components of G-S. The toughness of G, t(G), is defined as t(G)=min{|S|/@w(G-S)|[email protected]?V(G),@w(G-S)>1} if G is not complete; otherwise, set t(G)=+~. In this paper, we consider the relationship between the toughness and fractional (g,f,n)-critical graphs. It is proved that a graph G is a (g,f,n)-critical graph if t(G)>=(b^2-1)(n+1)/a.

Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ c -critical if γ c (G) = k, but γ c (G + xy)

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number @c"t(G) of G. The graph G is total domination edge critical if for every edge e in the complement of G, @c"t(G+e)

In this note the (?,3)-critical graphs are fairly classified. We show that a (?,k)- critical graph is not necessarily a (?,k?)-critical for k?? k and k,k? E {1,2,3}. The (2,3)-critical graphs are definitely characterized. Also the properties of (?,3)-critical graphs are verified once their edge connectivity are 3.

Amit, Linial, and Matousek (Random lifts of graphs III: independence and chromatic number, Random Struct. Algorithms, 2002) have raised the following question: Is the chromatic number of random h-lifts of K 5 asymptotically (for h → ∞ ) almost surely (a.a.s.) equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of K 5 \ e is a.a.s. three. We actually prove a stronger statement where K 5 \ e can be replaced by a graph obtained from joining a cycle to a stable set.

A subdivision of K"4 is called an odd-K"4 if each triangle of the K"4 is subdivided to form an odd cycle, and is called a fully odd-K"4 if each of the six edges of the K"4 is subdivided into a path of odd length. A graph G is called stability critical if the deletion of any edge from G increases the stability number. In 1993, Sewell and Trotter conjectured that in a stability critical graph every triple of edges which share a common end is contained in a fully odd-K"4. The purpose of this note is to show that such a triple is contained in an odd-K"4.

A secure dominating set X of a graph G is a dominating set with the property that each vertex [email protected]?V"G-X is adjacent to a vertex [email protected]?X such that (X-{v})@?{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by @c"s(G). We are interested in the effect of edge removal on @c"s(G), and characterize @c"s-ER-critical graphs, i.e. graphs for which @c"s(G-e)>@c"s(G) for any edge e of G, bipartite @c"s-ER-critical graphs and @c"s-ER-critical trees.

In max algebra it is well known that the sequence of max algebraic powers A k , with A an irreducible square matrix, becomes periodic after a finite transient time T ( A ) , and the ultimate period γ is equal to the cyclicity of the critical graph of A . In this connection, we study computational complexity of the following problems: (1) for a given k , compute a periodic power A r with r ≡ k ( mod γ ) and r ⩾ T ( A ) , (2) for a given x , find the ultimate period of { A l ⊗ x } . We show that both problems can be solved by matrix squaring in O ( n 3 log n ) operations. The main idea is to apply an appropriate diagonal similarity scaling A ↦ X - 1 AX , called visualization scaling, and to study the role of cyclic classes of the critical graph.

The paper studies the problem indicated in the title, which arises in connection with the well-known Nelson–Erdos–Hadwiger problem of finding the chromatic number of the Euclidean space.

A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, @g"D(G), is defined similarly. It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n^3log^3n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph's distinguishing chromatic number.

In this paper, using the chromatic properties of power graphs we propose a new approach for placing resources in symmetric networks. Our novel placement scheme guarantees a perfect placement when such a solution is feasible in the topology, while in general it answers the question of k-resource placement at a distance d where each non-resource node is able to access k resource nodes within at most d hops away. We define a quasi-perfect graph as a graph whose clique number and chromatic number are equal. We derive important properties of quasi-perfect graphs and use them to find a solution for the resource placement problem. We have also applied the proposed method to find a distant resource placement in the popular hypercube network as an example. We have also considered the problem of sparse resource placement.

Identifying critical nodes in a graph is important to understand the structural characteristics and the connectivity properties of the network. In this paper, we focus on detecting critical nodes, or nodes whose deletion results in the minimum pair-wise connectivity among the remaining nodes. This problem, known as the critical node problem has applications in several fields including biomedicine, telecommunications, and military strategic planning. We show that the recognition version of the problem is NP-complete and derive a mathematical formulation based on integer linear programming. In addition, we propose a heuristic for the problem which exploits the combinatorial structure of the graph. The heuristic is then enhanced by the application of a local improvement method. A computational study is presented in which we apply the integer programming formulation and the heuristic to real and randomly generated data sets. For all instances tested, the heuristic is able to efficiently provide optimal solutions in a fraction of the time required by a commercial software package.

Let G be a graph, and let a,b and k be nonnegative integers with [email protected][email protected]?b. An [a,b]-factor of graph G is defined as a spanning subgraph F of G such that [email protected]?d"F(x)@?b for each [email protected]?V(G). Then a graph G is called an (a,b,k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a,b]-factor. In this paper, it is proved that if @k(G)>=max{(a+1)b+2k2,(a+1)^[email protected](G)+4bk4b}, then G is an (a,b,k)-critical graph. Furthermore, it is showed that the result in this paper is best possible in some sense.

In this paper, we prove several new results on chromatic index critical graphs. We also prove that if G is a @D(>=4)-critical graph, then n"@D>=2@?j=2@D-1n"jj-1+12n"3, where n"j is the number of vertices having degree j in G.

We study the evolution of the chromatic number of a random intersection graph and show that, in a certain range of parameters, these random graphs can be colored optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.

We provide a complete list of 6-critical graphs that can be embedded on the Klein bottle settling a problem of Thomassen [J. Combin. Theory Ser. B, 70 (1997), pp. 67-100, Problem 3]. The list consists of nine nonisomorphic graphs which have altogether 18 nonisomorphic 2-cell embeddings and one embedding that is not 2-cell.