Search

The first part of the paper studies star-cycle factors of graphs. It characterizes star-cycle factors of a graph $G$ and proves upper bounds for the minimum number of $K_{1,2}$-components in a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of a graph $G$. Furthermore, it shows where these components are located with respect to the Gallai-Edmonds decomposition of $G$ and it characterizes the edges which are not contained in any $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of $G$. The second part of the paper proves that every edge-chromatic critical graph $G$ has a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor, and the number of $K_{1,2}$-components is bounded in terms of its fractional matching number. Furthermore, it shows that for every edge $e$ of $G$, there is a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor $F$ with $e \in E(F)$. Consequences of these results for Vizing's critical graph conjectures are discussed., final version, 23 pages

Using a technique which is inspired by topology, we construct original examples of 3 - and 4 -edge critical graphs. The 3 -critical graphs cover all even orders starting from 26 ; the 4 -critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3 -critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg’s infinite family of 3 -critical graphs, Chetwynd’s 4 -critical graph of order 16 and Fiol’s 4 -critical graph of order 18 .

A spanning subgraph of a graph is defined as a path factor of the graph if its component are paths. A P≥n-factor means a path factor with each component having at least n vertices. A graph G is defined as a (P≥n, m)-factor deleted graph if G–E′ has a P≥n-factor for every E′ ⊆ E(G) with |E′| = m. A graph G is defined as a (P≥n, k)-factor critical graph if after deleting any k vertices of G the remaining graph of G admits a P≥n-factor. In this paper, we demonstrate that (i) a graph G is (P≥3, m)-factor deleted if κ(G) ≥ 2m + 1 and bind(G) ≥ 2/3 - $ \frac{3}{2}-\frac{1}{4m+4}$; (ii) a graph G is (P≥3, k)-factor critical if κ(G) ≥ k + 2 and bind(G) ≥ $ \frac{5+k}{4}$.

A simple graph G is called $$\varDelta$$ -critical if $$\chi '(G) =\varDelta (G) +1$$ and $$\chi '(H) \le \varDelta (G)$$ for every proper subgraph H of G, where $$\varDelta (G)$$ and $$\chi '(G)$$ are the maximum degree and the chromatic index of G, respectively. Vizing in 1965 conjectured that any $$\varDelta$$ -critical graph contains a 2-factor, which is commonly referred to as Vizing’s 2-factor conjecture; In 1968, he proposed a weaker conjecture that the independence number of any $$\varDelta$$ -critical graph with order n is at most n/2, which is commonly referred to as Vizing’s independence number conjecture. Based on a construction of $$\varDelta$$ -critical graphs which is called Meredith extension first given by Meredith, we show that if $$\alpha (G')\le (\frac{1}{2}+f(\varDelta ))|V(G')|$$ for every $$\varDelta$$ -critical graph $$G'$$ with $$\delta (G')=\varDelta -1,$$ then $$\alpha (G)

DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvo\v{r}\'ak and Postle. We introduce and study $(i,j)$-defective DP-colorings of simple graphs. Let $g_{DP}(i,j,n)$ be the minimum number of edges in an $n$-vertex DP-$(i,j)$-critical graph. In this paper we determine sharp bound on $g_{DP}(i,j,n)$ for each $i\geq3$ and $j\geq 2i+1$ for infinitely many $n$., Comment: 17 pages

Given a graph G possibly with multiple edges but no loops, denote by Δ the maximum degree, μ the multiplicity, χ ′ the chromatic index and χ f ′ the fractional chromatic index of G, respectively. It is known that Δ ≤ χ f ′ ≤ χ ′ ≤ Δ + μ , where the upper bound is a classic result of Vizing. While deciding the exact value of χ ′ is a classic NP-complete problem, the computing of χ f ′ is in polynomial time . In fact, it is shown that if χ f ′ > Δ then χ f ′ = max ⁡ | E ( H ) | ⌊ | V ( H ) | / 2 ⌋ , where the maximality is taken over all induced subgraphs H of G. Gupta (1967), Goldberg (1973), Andersen (1977), and Seymour (1979) conjectured that χ ′ = ⌈ χ f ′ ⌉ if χ ′ ≥ Δ + 2 , which is commonly referred as Goldberg's conjecture. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: For any positive integer m with m ≥ 3 , every graph G with χ ′ > m m − 1 Δ + m − 3 m − 1 satisfies χ ′ = ⌈ χ f ′ ⌉ . Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We use an extended form of a Tashkinov tree to show that it is true for m ≤ 23 . With the same technique, we show that if χ ′ ≥ Δ + Δ / 2 3 then χ ′ = ⌈ χ f ′ ⌉ . The previous best known result is for graphs with χ ′ > Δ + Δ / 2 obtained by Scheide, and by Chen, Yu and Zang, independently. Moreover, we showthat Goldberg's conjecture holds for graphs G with Δ ≤ 23 or | V ( G ) | ≤ 23 .

Dirac introduced the notion of a k-critical graph, a graph that is not ( k − 1 ) -colorable but whose every proper subgraph is ( k − 1 ) -colorable. Brook's Theorem states that every graph with maximum degree k is k -colorable unless it contains a subgraph isomorphic to K k + 1 or an odd cycle (for k = 2 ). Equivalently, for all k ≥ 4 , the only k -critical graph of maximum degree k − 1 is K k . A natural generalization of Brook's theorem is to consider the Ore-degree of a graph, which is the maximum of d ( u ) + d ( v ) over all u v ∈ E ( G ) . Kierstead and Kostochka proved that for all k ≥ 6 the only k -critical graph with Ore-degree at most 2 k − 1 is K k . Kostochka, Rabern and Stiebitz proved that the only 5-critical graphs with Ore-degree at most 9 are K 5 and a graph they called O 5 . A different generalization of Brook's theorem, motivated by Hajos' construction, is Ore's conjectured bound on the minimum density of a k -critical graph. Recently, Kostochka and Yancey proved Gallai's conjecture. Their proof for k ≥ 5 implies the above results on Ore-degree. However, the case for k = 4 remains open, which is the subject of this paper. Kostochka and Yancey's short but beautiful proof for the case k = 4 says that if G is a 4-critical graph, then | E ( G ) | ≥ ( 5 | V ( G ) | − 2 ) / 3 . We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G , then | E ( G ) | ≥ 1.6 | V ( G ) | + . 2 α ( D 3 ( G ) ) − . 6 , where D 3 ( G ) is the graph induced by the degree three vertices of G . As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K 4 and Ore compositions.

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order n with maximum degree at least 6 n 7 is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order n with maximum degree at least 4 n 5 is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order n with maximum degree at least 3 n 4 is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs.

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph. Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals 2 is NP-complete. We deal with the CCHN of the graph itself as well.

When the vertices and edges are colored with k colors, an edge is called monochromatic if the edge and the two vertices incident with it all have the same color. The adapted chromatic number of a graph G, $$\chi _{a}\left( G\right) ,$$ is the least integer k such that for each k-edge coloring of G the vertices of G can be colored with the same set of colors without creating any monochromatic edges. It is easy to see that $$\chi _{a}\left( G\right) \le \chi \left( G\right) $$ . While this bound is tight, all the known graphs attaining this bound are not color critical. It is known that if G is a critical graph, then $$\chi _{a}\left( G\right) \le \chi \left( G\right) -1$$ . In this article we construct a family of k-critical graphs whose adapted chromatic number is exactly one less than their chromatic number. This answers a question in Molloy and Thron (J Graph Theory 71:331–351, 2012). We also study the properties of graphs that are critical with respect to adaptable chromatic number.

Graph grammars may be used to formally describe computational systems, modeling the states as graphs and the possible state changes as rules (whose left- and right-hand sides are graphs). The behavior of the system is defined by the application of these rules to the state-graphs. From a practical point of view, the extension of rules to enable description of extra conditions that must be satisfied upon rule application is highly desirable. An example is the specification of negative application conditions, or NACs, that describe situations that prevent the application of a rule. This extension of the basic formalism enhances the expressiveness of rules, generally allowing simpler specifications. Another extension that is fundamental for practical applications is the possibility to use data types, like natural numbers, lists, etc., as attributes of graphical elements (vertices and edges). Attributed graph grammars are well-investigated and used. However, there is a lack of verification techniques for this kind of grammar mainly due to the fact that data types are typically infinite domains, and thus techniques like model checking can not be used directly (without abstraction constructions). The present work provides a theoretical foundation for theorem proving graph grammars with negative application conditions and attributes. This is achieved by generating an event-B model from a graph grammar. Event-B models are composed by sets and axioms to define types, and by states and events to describe behavior. After constructing the event-B model that is semantically equivalent to a graph grammar, properties about reachable states may be proven using the various theorem provers available for event-B in the Rodin platform. This strategy allows the verification of systems with infinite-state spaces without using any kind of approximation.

In 1968, Vizing conjectured that for any Δ -critical graph G with n vertices and m edges, m ź 1 2 ( Δ - 1 ) n + 3 . Miao and Pang (2008) proved that m ź 7 4 n when Δ = 4 . However, their proof has a gap. In this paper, we first prove a new adjacency lemma and then apply this lemma to fix the gap.

Fuzzy graph coloring techniques are used to solve many complex real world problems. The chromatic number of complement of fuzzy graph is obtained and compared with the chromatic number of the corresponding fuzzy graph. The chromatic number of the resultant fuzzy graphs is studied, obtained by various operations on fuzzy graphs like union, join and types of products. A solution to routing problem is suggested by using chromaticity of fuzzy graphs.

The chromatic- edge-stability number es χ ( G ) of a graph G is the minimum number of edges whose removal results in a spanning subgraph G ′ with χ ( G ′ ) = χ ( G ) − 1 . Edge-stability critical graphs are introduced as the graphs G with the property that es χ ( G − e ) es χ ( G ) holds for every edge e ∈ E ( G ) . If G is an edge-stability critical graph with χ ( G ) = k and es χ ( G ) = l , then G is ( k , l ) -critical. Graphs which are ( 3 , 2 ) -critical and contain at most four odd cycles are classified. It is also proved that the problem of deciding whether a graph G has χ ( G ) = k and is critical for the chromatic number can be reduced in polynomial time to the problem of deciding whether a graph is ( k , 2 ) -critical.

For each surface Σ , we define Δ ( Σ ) = max { Δ ( G ) | G is a class two graph with maximum degree Δ ( G ) that can be embedded on Σ } . Hence Vizing’s Planar Graph Conjecture can be restated as Δ ( Σ ) = 5 if Σ is a sphere. For a surface Σ with Euler characteristic χ , it is known Δ ( Σ ) ≥ H ( χ ) − 1 where H ( χ ) is the Heawood number of the surface and if the Euler characteristic χ ∈ { − 7 , − 6 , … , − 1 , 0 } , Δ ( Σ ) is already known. In this paper, we study critical graphs on general surfaces and show that if G is a critical graph embeddable on a surface Σ with Euler characteristic χ ≤ − 8 , then Δ ( G ) ≤ H ( χ ) (or H ( χ ) + 1 ) for some special families of graphs, namely if the minimum degree is at most 11 or if Δ is very large etc. As applications, we show that Δ ( Σ ) ≤ H ( χ ) if χ ∈ { − 22 , − 21 , … , − 8 } ∖ { − 19 , − 16 } and Δ ( Σ ) ≤ H ( χ ) + 1 if χ ∈ { − 53 , … , − 23 } ∪ { − 19 , − 16 } . Combining this with Jungerman (1974), it follows that if χ = − 12 and Σ is orientable, then Δ ( Σ ) = H ( χ ) .

International audience; Two graph parameters are equivalent if, for every graph class, they are either both bounded or both unbounded. We provide a list of graph parameters equivalent to the acyclic chromatic number, which contains in particular the 2-edge-colored chromatic number. Recently, the CSP dichotomy conjecture has been reduced to the case of 2-edge-colored homomorphism and to the case of 2-vertex-colored homomorphism. Both reductions are rather long and follow the reduction to the case of oriented homomorphism in “Graphs and homomorphisms” by Hell and Nešetřil. We give another proof for the case of 2-vertex-colored homomorphism via a simple reduction from the case of 2-edge-colored homomorphism. Finally, we prove that deciding if the 2-edge-colored chromatic number of a 2-edge-colored graph is at most 4 is NP-complete, even if restricted to 2-connected subcubic bipartite planar graphs with arbitrarily large girth.

In this article, we provide new lower bounds for the size of edge chromatic critical graphs with maximum degrees of 10,11,12,13, 14, furthermore we characterize their class one properties.

In the big data era, graph computing is one of the challenging issues because there are numerous large graph datasets emerging from real applications. A question is: do we need to know the final exact answer for a large graph? When it is impossible to know the exact answer in a limited time, is it possible to approximate the final answer in an automatic and systematic way without having to designing new approximate algorithms? The main idea behind the question is: it is more important to find out something meaningful quick from a large graph, and we should focus on finding a way of making use of large graphs instead of spending time on designing approximate algorithms. In this paper, we give an innovative approach which automatically and systematically synthesizes a program to approximate the original program. We show that we can give users some answers with reasonable accuracy and high efficiency for a wide spectrum of graph algorithms, without having to know the details of graph algorithms. We have conducted extensive experimental studies using many graph algorithms that are supported in the existing graph systems and large real graphs. Our extensive experimental results reveal that our automatically approximating approach is highly feasible.

We discuss the problem of finding critical sets in graphs, a concept which has appeared in a number of guises in the combinatorics and graph theory literature. The case of the Sudoku graph receives particular attention, because critical sets correspond to minimal fair puzzles. We define four parameters associated with the sizes of extremal critical sets and (a) prove several general results concerning the properties of these parameters, including their computational intractability, (b) compute their values exactly for some classes of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a number of open questions regarding critical sets and the aforementioned parameters.

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.

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.

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.

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.

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 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 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.

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.

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.

In edge colouring it is often useful to have information about the degree distribution of the neighbours of a given vertex. For example, the well-known Vizing's Adjacency Lemma provides a useful lower bound on the number of vertices of maximum degree adjacent to a given one in a critical graph. We consider an extension of this problem, where we seek information on vertices at distance two from a given vertex in a critical graph. We extend and, simultaneously, generalize to multigraphs two results proved, respectively, by Zhang [Every planar graph with maximum degree seven is Class 1, Graphs Combin. 16 (2000) 467–495] and Sanders and Zhao [Planar graphs of maximum degree seven are Class 1, J. Combin. Theory Ser. B 83 (2001) 201–212].

Let γpr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γpr (G – v) < γpr (G). We call these graphs γpr -critical. In this paper, we present a method of constructing γpr -critical graphs from smaller ones. Moreover, we show that the diameter of a γpr -critical graph is at most $$\frac{3}{2}(\gamma_{pr} (G)-2)$$and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear].

The adaptable chromatic number of a graph G is the smallest integer k such that for any edge k-colouring of G there exists a vertex k-colouring of G in which the same colour never appears on an edge and both its endpoints. (Neither the edge nor the vertex colourings are necessarily proper in the usual sense.)We give an efficient characterization of graphs with adaptable chromatic number at most two, and prove that it is NP-hard to decide if a given graph has adaptable chromatic number at most k, for any k≥3. The adaptable chromatic number cannot exceed the chromatic number; for complete graphs, the adaptable chromatic number seems to be near the square root of the chromatic number. On the other hand, there are graphs of arbitrarily high girth and chromatic number, in which the adaptable chromatic number coincides with the classical chromatic number. In analogy with well-known properties of chromatic numbers, we also discuss the adaptable chromatic numbers of planar graphs, and of graphs with bounded degree, proving a Brooks-like result.

A graph G with maximum degree @D and edge chromatic number @g^'(G)>@D is [email protected] if @g^'(G-e)[email protected] for every edge e of G. New lower bounds are given for the average degree of an [email protected] graph, which improve on the best bounds previously known for most values of @D. Examples of [email protected] graphs are also given. In almost all cases, there remains a large gap between the best lower bound known and the smallest average degree of any known [email protected] 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.

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.

Given a directed graph G=(V(G),A(G)), a subset X of V(G) is an interval of G provided that for any a,[email protected]?X and [email protected]?V(G)-X, (a,x)@?A(G) if and only if (b,x)@?A(G), and similarly for (x,a) and (x,b). For example, @A, {x}([email protected]?V(G)) and V(G) are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial; otherwise, it is decomposable. An indecomposable directed graph G is then critical if for each [email protected]?V(G), G(V(G)-{x}) is decomposable and if there are x [email protected]?V(G) such that G(V(G)-{x,y}) is indecomposable. A generalization of the lexicographic sum is introduced to describe a process of construction of the critical and infinite directed graphs. It follows that for every critical and infinite directed graph G, there are x [email protected]?V(G) such that G and G(V(G)-{x,y}) are isomorphic. It is then deduced that if G is an indecomposable and infinite directed graph and if there is a finite subset F of V(G) such that |F|>=2 and G(V(G)-F) is indecomposable, then there are x [email protected]?V(G) such that G(V(G)-{x,y}) is indecomposable.

Direct reciprocity is a mechanism for the evolution of cooperation based on the idea of repeated encounters between the same two individuals. Here we examine direct reciprocity in structured populations, where individuals occupy the vertices of a graph. The edges denote who interacts with whom. The graph represents spatial structure or a social network. For birth-death or pairwise comparison updating, we find that evolutionary stability of direct reciprocity is more restrictive on a graph than in a well-mixed population, but the condition for reciprocators to be advantageous is less restrictive on a graph. For death-birth and imitation updating, in contrast, both conditions are easier to fulfill on a graph. Moreover, for all four update mechanisms, reciprocators can dominate defectors on a graph, which is never possible in a well-mixed population. We also study the effect of an error rate, which increases with the number of links per individual; interacting with more people simultaneously enhances the probability of making mistakes. We provide analytic derivations for all results.

In this paper, we apply some new algebraic no-homomorphism theorems in conjunction with some new chromatic parameters to estimate the circular chromatic number of graphs. To show the applicability of the general results, as a couple of examples, we generalize a well known inequality for the fractional chromatic number of graphs and we also show that the circular chromatic number of the graph obtained from the Petersen graph by excluding one vertex is equal to 3. Also, we focus on the Johnson–Holroyd–Stahl conjecture about the circular chromatic number of Kneser graphs and we propose an approach to this conjecture. In this regard, we introduce a new related conjecture on Kneser graphs and we also provide some supporting evidence.

Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\in V(G))$ be a family of sets such that $|L(v)|\ge 5$ for every $v\in V(G)$. By an $L$-coloring of a subgraph $J$ of $G$ we mean a (proper) coloring $\phi$ of $J$ such that $\phi(v)\in L(v)$ for every vertex $v$ of $J$. We prove a conjecture of Dvorak et al. that if $H$ is a minimal subgraph of $G$ such that $C$ is a subgraph of $H$ and every $L$-coloring of $C$ that extends to an $L$-coloring of $H$ also extends to an $L$-coloring of $G$, then $|V(H)|\le 19|V(C)|$. This is a lemma that plays an important role in subsequent papers, because it motivates the study of graphs embedded in surfaces that satisfy an isoperimetric inequality suggested by this result. Such study turned out to be quite profitable for the subject of list coloring graphs on surfaces., Comment: 25 pages, 2 figures

We present a new distributed model for graph computations motivated by limited information sharing. Two or more independent entities have collected large social graphs. They wish to compute the result of running graph algorithms on the entire set of relationships. Because the information is sensitive or economically valuable, they do not wish to simply combine the information in a single location. We consider two models for computing the solution to graph algorithms in this setting: 1) limited-sharing: the two entities can share only a poly logarithmic size subgraph, 2) low-trust: the entities must not reveal any information beyond the query answer, assuming they are all honest but curious. We believe this model captures realistic constraints on cooperating autonomous data centres' have results for both models for s-t connectivity, one of the simplest graph problems that requires global information in the worst case. In the limited-sharing model, our results exploit social network structure. Standard communication complexity gives polynomial lower bounds on s-t connectivity for general graphs. However, if the graph for each data centre has a giant component and these giant components intersect, then we can overcome this lower bound, computing-t connectivity while exchanging O(log ^2 n) bits for a constant number of data centers. We can also test the assumption that the giant components overlap using O(log ^2 n) bits provided the (unknown) overlap is sufficiently large. The second result is in the low trust model. We give a secure multi-party computation (MPC) algorithm that 1) does not make cryptographic assumptions when there are 3 or more entities, and 2) is efficient, especially when compared to the usual garbled circuit approach. The entities learn only the yes/no answer. No party learns anything about the others' graph, not even node names. This algorithm does not require any special graph structure. This secure MPC result for s-t connectivity is one of the first that involves a few parties computing on large inputs, instead of many parties computing on a few local values.

We prove that there are 24 4-critical $P_6$-free graphs, and give the complete list. We remark that, if $H$ is connected and not a subgraph of $P_6$, there are infinitely many 4-critical $H$-free graphs. Our result answers questions of Golovach et al. and Seymour., 31 pages

In this paper, we give new lower bounds for the size of Δ-critical graphs with Δ=8,9 which improve the partial results of Luo [6] and Y. Zhao [12].