Search

A graph is k-vertex-critical if χ (G) = k but χ (G - v) < k for all v ∈ V (G) . We construct new infinite families of k-vertex-critical (P 5 , C 5) -free graphs for all k ≥ 6 . Our construction generalises known constructions for 4-vertex-critical P 7 -free graphs and 5-vertex-critical P 5 -free graphs and is in contrast to the fact that there are only finitely many 5-vertex-critical (P 5 , C 5) -free graphs. In fact, our construction is even more well-structured, being (2 P 2 , K 3 + P 1 , C 5) -free. [ABSTRACT FROM AUTHOR]

A graph G is k -vertex-critical if χ (G) = k but χ (G − v) < k for all v ∈ V (G) where χ (G) denotes the chromatic number of G. We show that there are only finitely many k -vertex-critical (P 3 + ℓ P 1) -free graphs for all k ≥ 1 and all ℓ ≥ 0. Together with previous results, the only graphs H for which it is unknown if there are an infinite number of k -vertex-critical H -free graphs is H = (P 4 + ℓ P 1) for all ℓ ≥ 1. We consider a restriction on the smallest open case, and show that there are only finitely many k -vertex-critical (gem, co-gem)-free graphs for all k , where gem = P 4 + P 1 ¯. To do this, we show the stronger result that every vertex-critical (gem, co-gem)-free graph is either complete or a clique expansion of C 5. This characterization allows us to give the complete list of all k -vertex-critical (gem, co-gem)-free graphs for all k ≤ 16. [ABSTRACT FROM AUTHOR]

We study diameter 2-critical graphs (for short, D2C graphs), i.e. graphs of diameter 2 whose diameter increases after removing any edge. Our results include structural considerations, new examples and a particular relationship with minimal 2-self-centered graphs stating that these graph classes are almost identical. We pay an attention to primitive D2C graphs (PD2C graphs) which, by definition, have no two vertices with the same set of neighbours. It is known that a graph of diameter 2 and order n, which has no dominating vertex, has at least 2n - 5 edges, and the graphs that attain this bound are also known. It occurs that exactly three of them are PD2C. The next natural step is to consider PD2C graphs with 2n - 4 edges. In this context, we determine an infinite family of PD2C graphs which, for every n ≥ 6, contains exactly one graph with 2n - 4 edges. We also prove that there are exactly seven Hamiltonian PD2C graphs with the required number of edges. We show that for n ≤ 13, there exists a unique PD2C graph with 2n - 4 edges that does not belong to the obtained family nor is Hamiltonian. It is conjectured that this is a unique example of such a graph. [ABSTRACT FROM AUTHOR]

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.

The cutwidth of a graph G is the smallest integer k ( k ≥ 1 ) such that the vertices of G are arranged in a linear layout [ v 1 , v 2 ,... , v n ] , in such a way that for each i = 1 , 2 ,... , n − 1 , there are at most k edges with one endpoint in { v 1 , v 2 ,... , v i } and the other in { v i + 1 ,... , v n } . The cutwidth problem for G is to determine the cutwidth k of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex v 0 , and graph class with a central cycle C q of length q ≤ 6 , respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition S with cardinality 2, 3 or 4, where each member of S is either a 2-cutwith graph or a 3-cutwidth graph. [ABSTRACT FROM AUTHOR]

Let G1 and G2 be two undirected graphs. Let u1, v1 ∈ V (G1) and u2, v2 ∈ V (G2). A parallel composition forms a new graph H that combines G1 and G2 by contracting the vertices u1 with u2 and v1 with v2. A new kind of graph called a parallel critical graph is introduced in this paper. We present the critical property using the domination number of G1 and G2 and provide a necessary and sufficient condition for parallel critical graphs. Few results relating to some class of graphs and parallel composition are discussed in this paper. [ABSTRACT FROM AUTHOR]

Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χρ(H) < χρ(G). We characterize χρ-critical graphs with diameter 2, and χρ-critical block graphs with diameter 3. Furthermore, we characterize χρ-critical graphs with small packing chromatic number, and we also consider χρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χρ(G)+1)/2 ≤ χρ(G−e) ≤ χρ(G), and provide a corresponding realization result, which shows that χρ(G − e) can achieve any of the integers between these bounds.

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line P n with n = | V (G) | vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k > 1 . We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs. [ABSTRACT FROM AUTHOR]

The Gallai–Ramsey number g r k (K 3 : H 1 , H 2 , ⋯ , H k) is the smallest integer n such that every k-edge-colored K n contains either a rainbow K 3 or a monochromatic H i in color i for some i ∈ [ k ] . We define the star-critical Gallai–Ramsey number g r k ∗ (K 3 : H 1 , H 2 , ⋯ , H k) as the smallest integer s such that every k-edge-colored K n - K 1 , n - 1 - s contains either a rainbow K 3 or a monochromatic H i in color i for some i ∈ [ k ] . When H = H 1 = ⋯ = H k , we simply denote g r k ∗ (K 3 : H 1 , H 2 , ⋯ , H k) by g r k ∗ (K 3 : H) . We determine the star-critical Gallai–Ramsey numbers for complete graphs and some small graphs. Furthermore, we show that g r k ∗ (K 3 : H) is exponential in k if H is not bipartite, linear in k if H is bipartite but not a star and constant (not depending on k) if H is a star. [ABSTRACT FROM AUTHOR]

Let K1,k be a star of order k + 1 and Kn ⨆ K1,k the graph obtained from a complete graph Kn and an additional vertex v by joining v to k vertices of Kn. For graphs G and H, the star-critical Ramsey number r*(G, H) is the minimum integer k such that any red/blue edge-coloring of Kr−1 ⨆ K1,k contains a red copy of G or a blue copy of H, where r is the classical Ramsey number R(G, H). Let Cm denote a cycle of order m and Wn a wheel of order n + 1. Hook (2010) proved that r*(Wn, C3) = n + 3 for n ≥ 6. In this paper, we show that r*(Wn, Cm) = n + 3 for m odd, m ≥ 5 and n ≥ 3(m − 1)/2 + 2. [ABSTRACT FROM AUTHOR]

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line P n with n = | V (G) | vertices, in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we mainly investigated a class of decomposable k-cutwidth critical graphs for k ≥ 2 , which can be decomposed into three (k - 1) -cutwidth critical subgraphs. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G = (V, E) is a nonsplit dominating set if the induced graph ⟨V −D⟩ is connected. The nonsplit domination number γns(G) is the minimum cardinality of a nonsplit domination set. The purpose of this paper is to initiate the investigation of those graphs which are critical in the following sense: A graph G is called vertex domination critical if γ(G−v) < γ(G) for every vertex v in G. A graph G is called vertex nonsplit critical if γns(G − v) < γns(G) for every vertex v in G. Initially we test whether some particular classes of graph are γns-critical or not and then we have shown that there is no existence of 2-γns-critical graph. Then 3-γns-critical graphs are characterized. [ABSTRACT FROM AUTHOR]

The cutwidth of a graph G is the smallest integer k (k≥1) such that the vertices of G are arranged in a linear layout [v1,v2,...,vn], in such a way that for each i=1,2,...,n−1, there are at most k edges with one endpoint in {v1,v2,...,vi} and the other in {vi+1,...,vn}. The cutwidth problem for G is to determine the cutwidth k of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex v0, and graph class with a central cycle Cq of length q≤6, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition S with cardinality 2, 3 or 4, where each member of S is either a 2-cutwith graph or a 3-cutwidth graph.

In this paper, we study multi-level distance edge labeling for infinite rectangular, hexagonal and triangular grids. We label the edges with non-negative integers. If the edges are adjacent, then their color difference is at least 2 and if they are separated by exactly a single edge, then their colors must be distinct. We find the edge coloring number of these grids to be 9, 7 and 16, respectively so that we could color the edges of a rectangular, hexagonal and triangular grid with at most 10, 8 and 17 colors, respectively using this coloring technique. Repeating the sequence pattern for different grids, we can color the edges of a grid of larger size.

Given simple graphs H 1 , H 2 , ... , H c , the Ramsey number r (H 1 , H 2 , ... , H c) is the smallest positive integer n such that every edge-colored K n with c colors contains a subgraph in color i isomorphic to H i for some i ∈ { 1 , 2 , ... , c }. The critical graphs for r (H 1 , H 2 , ... , H c) are edge-colored complete graphs on r (H 1 , H 2 , ... , H c) − 1 vertices with c colors which contain no subgraphs in color i isomorphic to H i for any i ∈ { 1 , 2 , ... , c }. For n 1 ≥ n 2 ≥ ⋯ ≥ n c ≥ 1 , Cockayne and Lorimer (1975) showed that r (n 1 K 2 , n 2 K 2 , ... , n c K 2) = n 1 + 1 + ∑ i = 1 c (n i − 1) , in which n i K 2 is a matching of size n i. Using the Gallai–Edmonds Theorem, we characterized all the critical graphs for r (n 1 K 2 , n 2 K 2 , ... , n c K 2) , implying a new proof for this Ramsey number. [ABSTRACT FROM AUTHOR]

A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, we study multi-level distance edge labeling for infinite rectangular, hexagonal and triangular grids. We label the edges with non-negative integers. If the edges are adjacent, then their color difference is at least 2 and if they are separated by exactly a single edge, then their colors must be distinct. We find the edge coloring number of these grids to be 9, 7 and 16, respectively so that we could color the edges of a rectangular, hexagonal and triangular grid with at most 10, 8 and 17 colors, respectively using this coloring technique. Repeating the sequence pattern for different grids, we can color the edges of a grid of larger size. [ABSTRACT FROM AUTHOR]

The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification will be used in the proof of r∗(Pn, Pm).

Let γtg(G) denote the game total domination number of a graph G, and let G|v mean that a vertex v of G is declared to be already totally dominated. A graph G is total domination game critical if γtg(G|v)<γtg(G) holds for every vertex v in G. If γtg(G)=k, then G is further called k-γtg-critical. In this paper, we prove that the circular ladder C4k□K2 is 4k-γtg-critical and that the Möbius ladder ML2k is 2k-γtg-critical. [ABSTRACT FROM AUTHOR]

The domination number of a graph G, denoted by γ(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∈V(G), G-x is a critical graph with γ(G-x)=γ(G). Furuya (Australas. J. Comb. 62:184-196, 2015) proved that the diameter of a connected weak bicritical graph G is at most 2γ(G)-2. In this paper, we characterize the connected weak bicritical graphs G whose diameter is exactly 2γ(G)-2. This is a generalization of some known results concerning the diameter of graphs with a domination-criticality. [ABSTRACT FROM AUTHOR]

Let C 1 and C 2 be two sets of cycles. We determine all generalised Ramsey numbers R ( C 1 , C 2 ) such that C 1 or C 2 contains a cycle of length at most 6. This generalises previous results of Erdős, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also provide a complete classification of most ( C 1 , C 2 ) -critical graphs such that C 1 or C 2 contains a cycle of length at most 5. For length 4, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which | C 1 | = | C 2 | = 1 . For lengths 3 and 5, our results are new also in this special case. [ABSTRACT FROM AUTHOR]

We describe an algorithm for generating all k-critical [ABSTRACT FROM AUTHOR]

A (simple) k-matching in a graph is a subgraph all of whose nodes have degree at most k. The k-matching problem is to find a k-matching with a maximum number of edges. Wellknown results for the classical 1-matching problem, such as the Tutte{Berge min-max theorem and Edmonds's polynomial-time algorithm, are known to generalize to k-matchings. These 1-matching results are also known to generalize to the problem of finding a subgraph, with a maximum number of nodes, whose connected components are isolated edges and 1-critical (or hypomatchable) graphs from a specified set (e.g., triangles or pentagons). In this paper we present a new common generalization of these two generalized 1-matching problems. We present an algorithm, a min-max theorem, and a structure theorem (that generalizes the Edmonds{Gallai theorem for 1-matchings). Even when specialized to k-matchings, our min-max and structure theorems appear to be new. [ABSTRACT FROM AUTHOR]

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let G be a graph and L(G) be the set of all odd cycle lengths of G. We prove that (1) if L(G) = f3; 3 + 2lg, where l ≥ 2, then x(G) = maxf3; !(G)g, and (2) if L(G) = fk; k + 2lg, where k ≥ 5 and l ≥ 1, then x(G) = 3. These, together with the case L(G) = f3; 5g solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916{4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069{1088]. Our results also improve a classical theorem of Gyárfás which asserts that x (G) ≤ 2jL(G)j + 2 for any graph G. [ABSTRACT FROM AUTHOR]

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on $$g_c$$ -colorings of simple graphs. In this article, disconnected $$g_c$$ -critical graphs are studied firstly and their structure characteristics are depicted. [ABSTRACT FROM AUTHOR]

We give a new, stronger proof that there are only finitely many k -vertex-critical (P 5 , gem)-free graphs for all k. Our proof further refines the structure of these graphs and allows for the implementation of a simple exhaustive computer search to completely list all 6- and 7-vertex-critical (P 5 , gem)-free graphs. Our results imply the existence of polynomial-time certifying algorithms to decide the k -colourability of (P 5 , gem)-free graphs for all k where the certificate is either a k -colouring or a (k + 1) -vertex-critical induced subgraph. Our complete lists for k ≤ 7 allow for the implementation of these algorithms for all k ≤ 6. [ABSTRACT FROM AUTHOR]