Search

For a number l≥2, let Gl denote the family of graphs which have girth 2l+1 and have no odd hole with length greater than 2l+1. Wu, Xu and Xu conjectured that every graph in ⋃l≥2Gl is 3‐colourable. Chudnovsky et al., Wu et al., and Chen showed that every graph in G2, G3 and ⋃l≥5Gl is 3‐colourable, respectively. In this paper, we prove that every graph in G4 is 3‐colourable. This confirms Wu, Xu and Xu's conjecture. [ABSTRACT FROM AUTHOR]

Chung et al. constructed an induced subgraph of the hypercube Qn ${Q}^{n}$ with α(Qn)+1 $\alpha ({Q}^{n})+1$ vertices and with maximum degree smaller than ⌈n⌉ $\lceil \sqrt{n}\rceil $. Subsequently, Huang proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube Qn ${Q}^{n}$ is at least ⌈n⌉ $\lceil \sqrt{n}\rceil $, and posed the question: Given a graph G $G$, let f(G) $f(G)$ be the minimum of the maximum degree of an induced subgraph of G $G$ on α(G)+1 $\alpha (G)+1$ vertices, what can we say about f(G) $f(G)$? In this paper, we investigate this question for Cartesian product of paths Pm ${P}_{m}$, denoted by Pmk ${P}_{m}^{k}$. We determine the exact values of f(Pmk) $f({P}_{m}^{k})$ when m=2n+1 $m=2n+1$ by showing that f(P2n+1k)=1 $f({P}_{2n+1}^{k})=1$ for n≥2 $n\ge 2$ and f(P3k)=2 $f({P}_{3}^{k})=2$, and give a nontrivial lower bound of f(Pmk) $f({P}_{m}^{k})$ when m=2n $m=2n$ by showing that f(P2nk)≥⌈2cosπn2n+1k⌉ $f({P}_{2n}^{k})\ge \lceil 2\cos \frac{\pi n}{2n+1}\sqrt{k}\rceil $. In particular, when n=1 $n=1$, we have f(Qk)=f(P2k)≥k $f({Q}^{k})=f({P}_{2}^{k})\ge \sqrt{k}$, which is Huang's result. The lower bounds of f(P3k) $f({P}_{3}^{k})$ and f(P2nk) $f({P}_{2n}^{k})$ are given by using the spectral method provided by Huang. [ABSTRACT FROM AUTHOR]

Complementarity spectrum of a connected graph G, denoted by $ \Pi (G) $ Π (G) , is the set of spectral radii of all connected induced subgraphs of G. Further, G is said to be spectrally non-redundant if $ c(G) $ c (G) , the cardinality of $ \Pi (G) $ Π (G) , is equal to $ b(G) $ b (G) , the number of all non-isomorphic induced subgraphs of G. In this paper, we give a sufficient condition for a family of graphs to be spectrally non-redundant. Using this criterion, we show that several infinite families of graphs are spectrally non-redundant. Moreover, we apply the same condition to distinguish graphs by their spectral radius, which illustrates the main reason for associating a graph with its complementarity spectrum. [ABSTRACT FROM AUTHOR]

A simple graph G on n vertices is partition-good if and only if for all pairs (a, b) of positive integers such that a+b = n, V (G) can be partitioned into sets A,B satisfying: |A| = a, |B| = b, and G[A],G[B] are connected. G is partition-wonderful if and only if either (i) n = 1, or (ii) n > 1, G is connected, and of all pairs (a, b) of positive integers such that a + b = n, V (G) can be partitioned into sets A,B satisfying: |A| = a, |B| = b, and G[A],G[B] are partition-wonderful. We characterize the partition-good and the partition-wonderful among the complete multipartite graphs, and, along the way, prove some elementary results about these graph properties. [ABSTRACT FROM AUTHOR]

We prove that the size of the maximum induced forest (of bounded and unbounded degree) in the binomial random graph for with an arbitrary fixed is concentrated in an interval of size . We also show 2-point concentration for the size of the maximum induced forest (and tree) of bounded degree in for p = const. [ABSTRACT FROM AUTHOR]

What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the "basic treewidth obstructions"). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called "layered wheels," contain wheels, where a wheel consists of a hole (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. [ABSTRACT FROM AUTHOR]

The List-3-Coloring Problem is to decide, given a graph G and a list L(v) \subseteq \{ 1, 2, 3\} of colors assigned to each vertex v of G, whether G admits a proper coloring \phi with \phi (v) \in L(v) for every vertex v of G, and the 3-Coloring Problem is the List-3-Coloring Problem on instances with L(v) =\{ 1, 2, 3\} for every vertex v of G. The List-3-Coloring Problem is a classical NP-complete problem, and it is well-known that while restricted to H-free graphs (meaning graphs with no induced subgraph isomorphic to a fixed graph H), it remains NP-complete unless H is isomorphic to an induced subgraph of a path. However, the current state of art is far from proving this to be sufficient for a polynomial time algorithm; in fact, the complexity of the 3-Coloring Problem on P8-free graphs (where P8 denotes the eight-vertex path) is unknown. Here we consider a variant of the List-3-Coloring Problem called the Ordered Graph List-3-Coloring Problem, where the input is an ordered graph, that is, a graph along with a linear order on its vertex set. For ordered graphs G and H, we say G is H-free if H is not isomorphic to an induced subgraph of G with the isomorphism preserving the linear order. We prove, assuming H to be an ordered graph, a nearly complete dichotomy for the Ordered Graph List-3-Coloring Problem restricted to H-free ordered graphs. In particular, we show that the problem can be solved in polynomial time if H has at most one edge, and remains NP-complete if H has at least three edges. Moreover, in the case where H has exactly two edges, we give a complete dichotomy when the two edges of H share an end, and prove several NP-completeness results when the two edges of H do not share an end, narrowing the open cases down to three very special types of two-edge ordered graphs. [ABSTRACT FROM AUTHOR]

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all k and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of the (k × k) -wall or the line graph of a subdivision of the (k × k) -wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For t ≥ 2 , a t-theta is a graph consisting of two nonadjacent vertices and three internally vertex-disjoint paths between them, each of length at least t. A t-pyramid is a graph consisting of a vertex v , a triangle B disjoint from v and three paths starting at v and vertex-disjoint otherwise, each joining v to a vertex of B , and each of length at least t. We prove that for all k , t and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a t -theta, or a t -pyramid, or the line graph of a subdivision of the (k × k) -wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a t -theta for some t ≥ 2). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every Δ and subcubic subdivided caterpillar T , every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of T or the line graph of a subdivision of T as an induced subgraph. [ABSTRACT FROM AUTHOR]

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w (t) such that every graph in C with treewidth more than w (t) contains an induced subgraph isomorphic to one of the following: the complete graph K t , the complete bipartite graph K t , t , a subdivision of the (t × t) -wall or the line graph of a subdivision of the (t × t) -wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η , a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series. [ABSTRACT FROM AUTHOR]

The Gyárfás-Sumner conjecture says that for every forest H and every integer k , if G is H -free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H , if G is H -free and does not contain K t , t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H , the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d ≥ 2 , if G is H -free and does not contain as a subgraph the complete d -partite graph with parts of cardinality t , then its chromatic number is at most polynomial in t. [ABSTRACT FROM AUTHOR]

The size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph < R >. The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k) (Γ). We study the existence of resolving sets of size k in some families of graphs and investigate their properties. We find bounds on the metric dimension of size k of a graph Γ. We give the necessary condition for the metric dimension of size k and size (k + 1) of a graph Γ, to satisfy the inequality β(k+1)(Γ)-β(k) (Γ) ≤ 1. We will disprove a conjecture on bounds of the metric dimension of size k. For every positive integers k, l, and n such that k + 1 ≤ l ≤ n, we give a realizable result of a graph Γ of order n and l = β(k) (Γ). [ABSTRACT FROM AUTHOR]

For a positive integer n , we use K n and P n to denote a complete graph and an induced path on n vertices, respectively. A subdivision of G is a graph obtained from G by replacing the edges of G with independent paths of length at least one between their end vertices. A graph is said to be ISK 4 - free if it does not contain any subdivision of K 4 as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ISK 4 -free graph is 4-colorable. In this paper, we show that this conjecture is true for the class of P 6 -free graphs. [ABSTRACT FROM AUTHOR]

A hole in a graph G $G$ is an induced cycle of length at least four, and a k $k$‐multihole in G $G$ is the union of k $k$ pairwise disjoint and nonneighbouring holes. It is well known that if G $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer k≥1 $k\ge 1$, if G $G$ does not contain a k $k$‐multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially χ $\chi $‐bounded. [ABSTRACT FROM AUTHOR]

Let G and H be two vertex disjoint graphs. The union G ∪ H is the graph with V (G ∪ H) = V (G) ∪ (H) and E (G ∪ H) = E (G) ∪ E (H) . The join G + H is the graph with V (G + H) = V (G) ∪ V (H) and E (G + H) = E (G) ∪ E (H) ∪ { x y | x ∈ V (G) , y ∈ V (H) } . We use P k to denote a path on k vertices, use fork to denote the graph obtained from K 1 , 3 by subdividing an edge once, and use crown to denote the graph K 1 + K 1 , 3 . In this paper, we show that (i) χ (G) ≤ 3 2 (ω 2 (G) - ω (G)) if G is (crown, P 5 )-free, (ii) χ (G) ≤ 1 2 (ω 2 (G) + ω (G)) if G is (crown, fork)-free, and (iii) χ (G) ≤ 1 2 ω 2 (G) + 3 2 ω (G) + 1 if G is (crown, P 3 ∪ P 2 )-free. [ABSTRACT FROM AUTHOR]

The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V , and a sequence S 1 , S 2 , ... , S r ⊆ V of connectivity constraints, the objective is to find a set E of edges such that each S i induces a connected subgraph of the graph (V , E) and the total cost of E is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O (B 2 log n) -competitive and O ((B + log r) log n) -competitive polynomial-time algorithms, where B is an upper bound on the size of constraints, while r , n denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an Ω (B) -competitive lower bound as well as an Ω (B) -competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an O (n (log n + log r)) -competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most d. Among other things, we provide a polynomial-time ( B 2 − B + 2) B 2 -approximation algorithm for the Network Construction problem with the d -diameter requirements, when each constraint has at most B vertices, and show the APX-completeness of this variant. [ABSTRACT FROM AUTHOR]

For integer n > 0 , let f (n) be the number of rows of the largest all-0 or all-1 square submatrix of M , minimized over all n × n 0/1-matrices M. Thus f (n) = O (log ⁡ n). But let us fix a matrix H , and define f H (n) to be the same, minimized over all n × n 0/1-matrices M such that neither M nor its complement (that is, change all 0's to 1's and vice versa) contains H as a submatrix. It is known that f H (n) ≥ ε n c , where c , ε > 0 are constants depending on H. When can we take c = 1 ? If so, then one of H and its complement must be an acyclic matrix (that is, the corresponding bipartite graph is a forest). Korándi, Pach, and Tomon [6] conjectured the converse, that f H (n) is linear in n for every acyclic matrix H ; and they proved it for certain matrices H with only two rows. Their conjecture remains open, but we show f H (n) = n 1 − o (1) for every acyclic matrix H ; and indeed there is a 0/1-submatrix that is either Ω (n) × n 1 − o (1) or n 1 − o (1) × Ω (n). [ABSTRACT FROM AUTHOR]

A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. In an earlier paper [1] , Addario-Berry, Havet and Reed, with the authors, claimed to prove a conjecture of Reed, that every even-hole-free graph has a bisimplicial vertex, but we have recently been shown that the "proof" has a serious error. Here we give a proof using a different approach. [ABSTRACT FROM AUTHOR]

In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0 < τ ≤ 1 , there exists ε > 0 , such that if G has a bipartition (A , B) and does not contain H as an induced subgraph, and has at most (1 − τ) | A | ⋅ | B | edges, then there is a stable set X of G with | X ∩ A | ≥ ε | A | and | X ∩ B | ≥ ε | B |. No graphs H except forests have this property. [ABSTRACT FROM AUTHOR]

We investigate the question how 'small' a graph can be, if it contains all members of a given class of locally finite graphs as subgraphs or induced subgraphs. More precisely, we give necessary and sufficient conditions for the existence of a connected, locally finite graph H containing all elements of a graph class G. These conditions imply that such a graph H exists for the class G d consisting of all graphs with maximum degree < d which raises the question whether in this case H can be chosen to have bounded maximum degree. We show that this is not the case, thereby answering a question recently posed by Huynh et al. [ABSTRACT FROM AUTHOR]

Say a graph G is a pentagraph if every cycle has length at least five, and every induced cycle of odd length has length five. Robertson proposed the conjecture that the Petersen graph is the only internally 4‐connected pentagraph, but this was disproved by Plummer and Zha in 2014. Plummer and Zha conjectured that every internally 4‐connected pentagraph is three‐colourable. We prove this: indeed, we will prove that every pentagraph is three‐colourable. [ABSTRACT FROM AUTHOR]

Let F 1 and F 2 be two disjoint graphs. The union F 1 ∪ F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) , and the join F 1 + F 2 is a graph with vertex set V (F 1) ∪ V (F 2) and edge set E (F 1) ∪ E (F 2) ∪ { x y | x ∈ V (F 1) and y ∈ V (F 2) } . In this paper, we present a characterization to (P 5 , K 1 ∪ K 3) -free graphs, prove that χ (G) ≤ 2 ω (G) - 1 if G is (P 5 , K 1 ∪ K 3) -free. Based on this result, we further prove that χ (G) ≤ max { 2 ω (G) , 15 } if G is a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph. We also construct a (P 5 , K 1 + (K 1 ∪ K 3)) -free graph G with χ (G) = 2 ω (G) . [ABSTRACT FROM AUTHOR]

In this paper, a new idea to configure a special graph from the discrete topological space is given. Several properties and bounds of this topological graph are introduced. Such that if the order of the non-empty set equals two, then the topological graph is isomorphic to the complete graph. If the order equals three, then the topological graph is isomorphic to the complement of the cycle graph. Our topological graph has n- 1 complete induced subgraphs with order n; or more. It also has a cycle subgraph. In addition, the clique number is obtained. The topological graph is proved simple, undirected, connected graph. It has no pendant vertex, no isolated vertex and no cut vertex. The minimum and maximum degrees are evaluated. So, the radius and diameter are studied her [ABSTRACT FROM AUTHOR]

We characterize the simple connected graphs with the second largest eigenvalue less than 1/2, which consists of 13 classes of specific graphs. These 13 classes hint that c 2 ∈ [ 1 / 2 , 2 + 5 ] , where c 2 is the minimum real number c for which every real number greater than c is a limit point in the set of the second largest eigenvalues of the simple connected graphs. We leave it as a problem. [ABSTRACT FROM AUTHOR]

A wheel is a graph consisting of an induced cycle of length at least four and a single additional vertex with at least three neighbours on the cycle. We prove that no Burling graph contains an induced wheel. Burling graphs are triangle‐free and have arbitrarily large chromatic number, so this answers a question of Trotignon and disproves a conjecture of Scott and Seymour. [ABSTRACT FROM AUTHOR]

For G=Gn,1/2$$ G={G}_{n,1/2} $$, the Erdős–Renyi random graph, let Xn$$ {X}_n $$ be the random variable representing the number of distinct partitions of V(G)$$ V(G) $$ into sets A1,...,Aq$$ {A}_1,\dots, {A}_q $$ so that the degree of each vertex in G[Ai]$$ G\left[{A}_i\right] $$ is divisible by q$$ q $$ for all i∈[q]$$ i\in \left[q\right] $$. We prove that if q≥3$$ q\ge 3 $$ is odd then Xn→dPo(1/q!)$$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left(1/q!\right) $$, and if q≥4$$ q\ge 4 $$ is even then Xn→dPo(2q/q!)$$ {X}_n\overset{d}{\to \limits}\mathrm{Po}\left({2}^q/q!\right) $$. More generally, we show that the distribution is still asymptotically Poisson when we require all degrees in G[Ai]$$ G\left[{A}_i\right] $$ to be congruent to xi$$ {x}_i $$ modulo q$$ q $$ for each i∈[q]$$ i\in \left[q\right] $$, where the residues xi$$ {x}_i $$ may be chosen freely. For q=2$$ q=2 $$, the distribution is not asymptotically Poisson, but it can be determined explicitly. [ABSTRACT FROM AUTHOR]

We prove that for every n , there is a graph G with χ (G) ≥ n and ω (G) ≤ 3 such that every induced subgraph H of G with ω (H) ≤ 2 satisfies χ (H) ≤ 4. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5. [ABSTRACT FROM AUTHOR]

The induced subgraph of a unit graph with vertex set as the non unit elements of a ring R is a graph obtained by deleting all unit elements of R. In a graph Γ, a subset of the vertex set is called a perfect code if the balls with radius 1 centred on the subset are pairwise disjoint and their unions yield the whole vertex set. In this paper, we determine the perfect codes of induced subgraphs of the unit graphs associated with some finite commutative rings R with unity that has a vertex set as non unit elements of R. Moreover, we classify the commutative rings in which their associated induced subgraphs of unit graphs admit the trivial and non-trivial perfect codes. We also characterize the commutative rings based on the induced subgraph of unit graphs that do not admit the perfect codes. Furthermore, we prove that the complement induced subgraph of unit graph admit only the trivial subring perfect code. [ABSTRACT FROM AUTHOR]

The Gyárfás–Sumner conjecture says that for every forest H $H$, there is a function fH ${f}_{H}$ such that if G $G$ is H $H$‐free then χ(G)≤fH(ω(G)) $\chi (G)\le {f}_{H}(\omega (G))$ (where χ,ω $\chi ,\omega $ are the chromatic number and the clique number of G $G$). Louis Esperet conjectured that, whenever such a statement holds, fH ${f}_{H}$ can be chosen to be a polynomial. The Gyárfás–Sumner conjecture is only known to be true for a modest set of forests H $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when H $H$ is a five‐vertex path. Here we prove Esperet's conjecture when each component of H $H$ is a star. [ABSTRACT FROM AUTHOR]

A "double star" is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star H $H$, there is a function fH ${f}_{H}$ such that if G $G$ does not contain H $H$ as an induced subgraph then χ(G)≤fH(ω(G)) $\chi (G)\le {f}_{H}(\omega (G))$ (where χ,ω $\chi ,\omega $ are the chromatic number and the clique number of G $G$). Here we prove that fH ${f}_{H}$ can be chosen to be a polynomial. [ABSTRACT FROM AUTHOR]

Given a vertex-weighted connected graph G = (V , E , w (·)) , the maximally balanced connected graphk-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max–mink-BGP (min–maxk-BGP, respectively), and has received much study since about four decades ago. On general graphs, max–mink-BGP is strongly NP-hard for every fixed k ≥ 2 , and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max–min BGP, and cannot be approximated within 6/5 unless P = NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min–max 3-BGP and a 5/3-approximation for max–min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge. [ABSTRACT FROM AUTHOR]

A long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed the conjecture with c ≥ 10 - 4 . However, this is far from optimal for special family of graphs. Scott proved that c ≥ (2 χ) - 1 for graphs with chromatic number χ ≥ 2 and conjectured that c ≥ χ - 1 . Partial tight bounds of c are also established by various authors for graphs such as trees, graphs with maximum degree 3 or K 4 -minor-free graphs. In this paper, we further prove that c ≥ 2 / 5 for planar graphs with girth at least 7, and the bound is tight. We also show that c ≤ 1 / 3 for general planar graphs and c ≥ 1 / 3 for planar graphs with girth at least 6. [ABSTRACT FROM AUTHOR]

An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock proved that detecting an even (respectively, odd) hole containing a given vertex is NP‐complete. Conforti, Cornuéjols, Kapoor, and Vušković gave the first known polynomial‐time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour estimated that Conforti et al.'s algorithm runs in O(n40) time on an n‐vertex graph and reduced the required time to O(n31). Subsequently, da Silva and Vušković, Chang and Lu, and Lai, Lu, and Thorup improved the time to O(n19), O(n11), and O(n9), respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl that runs in O(n9) time, which Lai et al. also reduced to O(n8). By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour (respectively) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP‐hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for 16 years by, for example, Chudnovsky et al. and Johnson. We resolve this open problem by augmenting Chudnovsky et al.'s even‐hole detection algorithm into the first known polynomial‐time algorithm, running in O(n31) time, for finding a shortest even hole in an n‐vertex graph that contains even holes. [ABSTRACT FROM AUTHOR]

Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5‐cycles that an n‐vertex planar graph can contain. [ABSTRACT FROM AUTHOR]

A P 4 -free graph is called a cograph. In this paper we partially characterize finite groups whose power graph is a cograph. As we will see, this problem is a generalization of the determination of groups in which every element has prime power order, first raised by Graham Higman in 1957 and fully solved very recently. First we determine all groups G and H for which the power graph of G × H is a cograph. We show that groups whose power graph is a cograph can be characterised by a condition only involving elements whose orders are prime or the product of two (possibly equal) primes. Some important graph classes are also taken under consideration. For finite simple groups we show that in most of the cases their power graphs are not cographs: the only ones for which the power graphs are cographs are certain groups PSL (2 , q) and Sz (q) and the group PSL (3 , 4). However, a complete determination of these groups involves some hard number-theoretic problems. [ABSTRACT FROM AUTHOR]

An open triangle is a 3-vertex subgraph with two edges, i.e., an induced path of length . A formula for the maximum number of open triangles in -vertex graphs with edges is proved in the paper. We also present a full characterization of graphs for which the maximum is attained. [ABSTRACT FROM AUTHOR]

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs. [ABSTRACT FROM AUTHOR]

The nullity of a graph is the multiplicity of zero as an eigenvalue in its adjacency spectrum. Let G be a connected graph with n vertices, maximum degree Δ and nullity η. B. Cheng et al. (2020) proved that if G is not complete bipartite and Δ ≥ 3 , then η ≤ (Δ − 2) n Δ − 1. In this paper we prove that the said inequality for η becomes equality only if Δ = 3 , and identify all extremal graphs that attain the equality. As an immediate by-product, some connected graphs G with Δ = 3 that satisfy η = n − 1 2 are found. We work with 0-basic subgraphs and develop a new proof technique that is based on the concepts of dual vertex and pendant-dual vertex. Some open problems are also posed. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and m edges. The minimum edge dominating energy is equal to the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of graph G. In this paper, we establish some bounds for the minimum edge dominating energy of subgraphs of a graph. [ABSTRACT FROM AUTHOR]

Let Sk denote a star with k edges. The line graph of the complete graph Kn is denoted by L(Kn). In this paper, we prove that the graph L(Kn) has an S4-decomposition if and only if n ≥ 6 and n ≡ n ≡ 0, 1, 2, 4, 6 (mod 8). [ABSTRACT FROM AUTHOR]

Recently, Huang showed that every (2n−1+1)‐vertex induced subgraph of the n‐dimensional hypercube has maximum degree at least n. In this paper, we discuss the induced subgraphs of Cartesian product graphs and semistrong product graphs to generalize Huang's result. Let Γ1 be a connected signed bipartite graph of order n and Γ2 be a connected signed graph of order m. By defining two kinds of signed product of Γ1 and Γ2, denoted by Γ1□˜Γ2 and Γ1⋈˜Γ2, we show that if Γ1 and Γ2 have exactly two distinct adjacency eigenvalues ±θ1 and ±θ2, respectively, then every (12mn+1)‐vertex induced subgraph of Γ1□˜Γ2 (resp., Γ1⋈˜Γ2) has maximum degree at least θ12+θ22 (resp., (θ12+1)θ22). Moreover, we discuss the eigenvalues of Γ1□˜Γ2 and Γ1⋈˜Γ2 and obtain a sufficient and necessary condition such that the spectrum of Γ1□˜Γ2 and Γ1⋈˜Γ2 is symmetric with respect to 0, from which we obtain more general results on maximum degree of the induced subgraphs. [ABSTRACT FROM AUTHOR]

The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains the complete graph K X(G) as an immersion. Like its minor-order counterpart it is open even for graphs with independence number 2. Let G and H be graphs with independence number at most 2, such that |V(H)| ≤ 4. We show that if G is H -free, then G satisfies the conjecture. [ABSTRACT FROM AUTHOR]