Search

In 1943, Hadwiger conjectured that every graph with no K t + 1 minor is t-colorable for every t ≥ 0 . While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980 s, Kostochka and Thomason independently proved that every graph with no K t minor has average degree O ( t log ⁡ t ) and thus is O ( t log ⁡ t ) -list-colorable. Recently, the authors and Song proved that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -colorable for every β > 1 4 . Here, we build on that result to show that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -list-colorable for every β > 1 4 . Our main new tool is an upper bound on the number of vertices in highly connected K t -minor-free graphs: We prove that for every β > 1 4 , every Ω ( t ( log ⁡ t ) β ) -connected graph with no K t minor has O ( t ( log ⁡ t ) 7 / 4 ) vertices.

The number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2 n / 17700000 . On the other hand, for infinitely many n, there exists a triangle-free planar graph with separating cycles of length 4 and 5 whose number of proper vertex-3-colorings is 2 15 n / log 2 ⁡ ( n ) .

Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph G , denoted r c ( G ) , is the least k for which G admits a (not necessarily proper) k -edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define r c ( G ) = ∞ . A graph G is rainbow critical if the deletion of any edge of G increases r c ( G ) . In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs.

Let G be a connected graph of order n , A ( G ) the adjacency matrix of G and D ( G ) the diagonal matrix of the row-sums of A ( G ) . For every real α ∈ [ 0 , 1 ] , Nikiforov defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . In this paper, we obtain a factorization of the A α -characteristic polynomial of the some families of graphs and determine in these families the conditions about α so that A α ( G ) is positive semidefinite.

We present a generalization of a combinatorial result by Aggarwal et al. (1989) on a linear-time algorithm that selects a constant fraction of leaves, with pairwise disjoint neighborhoods, from a binary tree embedded in the plane. This result of Aggarwal et al. (1989) is essential to the linear-time framework, which they also introduced, that computes certain Voronoi diagrams of points with a tree structure in linear time. An example is the diagram computed while updating the Voronoi diagram of points after deletion of one site. Our generalization allows that only a fraction of the tree leaves is considered, and it is motivated by research on linear time construction algorithms for Voronoi diagrams of non-point sites. We are given a plane tree T of n leaves, m of which have been marked, and each marked leaf is associated with a neighborhood (a subtree of T ) such that any two topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves having pairwise disjoint neighborhoods.

The main objective of this article is to study the Wiener index of zero-divisor graph of the ring of integer modulo n . We present a constructed method to calculate the Wiener index of zero-divisor graph of Z n for any positive integer n .

The eternal vertex cover problem is a variant of the classical vertex cover problem defined in terms of an infinite attacker–defender game played on a graph. In each round of the game, the defender reconfigures guards from one vertex cover to another in response to a move by the attacker. The minimum number of guards required in any winning strategy of the defender when this game is played on a graph G is the eternal vertex cover number of G , denoted by evc ( G ) . It is known that given a graph G and an integer k , checking whether evc ( G ) ≤ k is NP-hard. Further, it is known that for any graph G , mvc ( G ) ≤ evc ( G ) ≤ 2 mvc ( G ) , where mvc ( G ) is the vertex cover number of G . Though a characterization is known for graphs for which evc ( G ) = 2 mvc ( G ) , a characterization of graphs for which evc ( G ) = mvc ( G ) remained as an open problem, since 2009. We achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For biconnected chordal graphs, our characterization leads to a polynomial time algorithm for precisely determining evc ( G ) and an algorithm for determining a safe strategy for guard movement in each round of the game using only evc ( G ) guards. Though the eternal vertex cover problem is only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provide reductions establishing NP-completeness of the problem for biconnected internally triangulated planar graphs. As far as we know, this is the first NP-completeness result known for the problem for any graph class.

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben's strategy) is called the indicated chromatic number of $G$, denoted by $\chi_i(G)$. In this paper, we have shown that for any graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for all $k\geq\mathrm{col}(G)\mathrm{col}(H)$. Also, we have shown that for any graph $G$ and for some classes of graphs $H$ with $\chi(H)=\chi_i(H)=\ell$, $G[H]$ is $k$-indicated colorable if and only if $G[K_\ell]$ is $k$-indicated colorable. As a consequence of this result we have shown that for some particular families of graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for every $k\geq \chi(G[H])$. This serves as a partial answer to one of the questions raised by A. Grzesik in \cite{and}. In addition, if $G$ is a Bipartite graph or a $\{P_5,K_3\}$-free graph (or) a $\{P_5,Paw\}$-free graph and if $H$ is from the same families of graphs, then we have shown that $\chi_i(G[H])=\chi(G[H])$.

A subset D ⊆ V of a graph G = ( V , E ) is called a global total k -dominating set of G if D is a total k -dominating set of both G and G ¯ , the complement of G . The Minimum Global Total k - Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and the Decide Global Total k - Domination problem is the decision version of the Minimum Global Total k - Domination problem. The Decide Global Total k - Domination problem is known to be NP -complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k - Domination problem. We show the Decide Global Total k - Domination problem remains NP -complete for bipartite graphs and chordal graphs. We also show that Minimum Global Total k - Domination cannot be approximated within a factor of ( 1 − ϵ ) ln | V | for any ϵ > 0 unless P = NP for bipartite graphs as well as for chordal graphs. Next, we show that Minimum Global Total k - Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Total k - Domination problem is APX -complete for bounded degree graphs. We also show that Decide Global Total k - Domination problem is W[2] -hard for bipartite graphs and for chordal graphs when we choose the size of the GTkD-set as the parameter.

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H - Free Coloring if none of the color classes contain H as an induced subgraph. The H - Free Chromatic Number of G is the minimum number of colors required for an H - Free Coloring of G . Both The Matching Cut problem and the H - Free Coloring problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f ( | | φ | | , t ) n O ( 1 ) , where | | φ | | is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f ( | | φ | | , t ) on | | φ | | can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for Matching Cut problem and H - Free Coloring problem, parameterized by the tree-width of G . The single exponential FPT algorithm for the Matching Cut problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H -free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G .

Sierpinski triangle graphs S n have often been mistaken for Sierpinski graphs S 3 n . Whereas the latter’s metric properties are by now well understood, the former graphs were mostly just considered as a pictorial representation of approximations to the Sierpinski triangle fractal. Therefore, we present here a new labeling for them which shows the relation, but also the differences to the more famous Sierpinski graphs proper. On the base of this labeling we describe an algorithm to obtain individual distances between vertices. This type of algorithm can then be extended to base- p Sierpinski triangle graphs S p n which are related to the class of classical Sierpinski graphs S p n , p ≥ 2 . Some of the metric properties of S p n can now be investigated for S p n as well; e.g., we characterize center and periphery of S p n .

Consider a variant of the famous Tower of Hanoi problem where moves of the discs are allowed along the edges of a connected simple graph D whose vertices represent the vertical pegs of the puzzle. The task is to transfer a tower of n ∈ N discs from one peg to another according to the well-known rules of the classical game corresponding to D ≅ K 3 . Apart from its recreational appeal, the problem brings about fascinating integer sequences engendered by the respective minimum number of moves, i.e. the distance in the canonical metric of the state graph H D n . We construct an algorithm which solves the task for all cases but the exceptional instance of the Linear Tower of Hanoi (i.e. where D is a path graph) in which the transfer is between the two end vertices of D . Optimality of this algorithm is claimed in our central conjecture which is supported by large-scale computational explorations.

An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor., Full version of the paper to be presented in CALDAM 2020

A graph G is P ≥ k -factor deleted if for every edge e ∈ E ( G ) , G contains a P ≥ k -factor that excludes e . We first define the concept of ( P ≥ k , n ) -critical deleted graph, that is, a graph G is ( P ≥ k , n ) -critical deleted if for every subset D ⊆ V ( G ) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a ( P ≥ k , 0 ) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an ( n + 2 ) -connected graph G is ( P ≥ 2 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 4 ; (ii) an ( n + 2 ) -connected graph G is ( P ≥ 3 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense.

Given a graph G , we call a partition ( V 1 , V 2 , … , V k ) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2 . (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0 . (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3 ), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs ( r ≥ 2 ) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature.

Let G = ( V , E ) be a simple undirected graph. A set D ⊆ V is called a vertex-edge dominating set of G if for each edge e = u v ∈ E , either u or v is in D or one vertex from their neighbor is in D . Simply, a vertex v ∈ V , vertex-edge dominates every edge u v , as well as every edge adjacent to these edges. The objective of the vertex-edge domination problem is to find a minimum size vertex-edge dominating set of G . Herein, we study the vertex-edge domination problem in unit disk graphs and prove that the decision version of the problem belongs to the NP-complete class. We also show that the problem admits a simple polynomial-time 4-factor approximation algorithm and a polynomial-time approximation scheme (PTAS) in unit disk graphs.

For a given graph $G$, the metric and edge metric dimensions of $G$, $\dim(G)$ and ${\rm edim}(G)$, are the cardinalities of the smallest possible subsets of vertices in $V(G)$ such that they uniquely identify the vertices and the edges of $G$, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph $G$ such that $\dim(G)=a$ and ${\rm edim}(G)=b$ for every pair of integers $a,b$, where $4\le b, Comment: 12 pages

Consider a region that requires to be protected from unauthorized penetrations. The border of the region, modeled as a unit line segment, consists of high priority segments that require the highest level of protection separated by low priority segments that require to be visited infinitely often. We study the problem of patrolling the border with a set of k robots. The goal is to obtain a strategy that minimizes the maximum idle time (the time that a point is left unattended) of the high priority points while visiting the low priority points infinitely often. We use the concept of single lid cover (segments of fixed length) where each high priority point is covered with at least one lid, and then we extend it to strong double-lid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let λk-1 be the minimum lid length that accepts a single λk-1-lid cover with k - 1 lids and Λ2k be the minimum lid length that accepts a strong double Λ2k-lid cover with 2k lids. We show that 2min(Λ2k, λk-1) is the lower bound of the idle time when the max speed of the robots is one. To compute Λ2k and λk-1, we present an algorithm with time complexity O(max(k, n) logn) where n is the number of high priority sections. Our algorithm improves by a factor of min(n, k) the previous O(knlogn) running time algorithm. For the upper bound, first we present a strategy with idle time λk-1 where one robot covers the unit line, and the remaining robots cover the lids of a single λk-1-lid cover with k - 1 lids. Then, we present a simple strategy with idle time 3Λ2k that splits the unit line into not-disjoint k segments of equal length that robots synchronously cover, i.e., reaching the leftmost and rightmost point simultaneously. Then, we present a complex strategy that split the unit line into k non-disjoint segments that robots asynchronously cover. We show that combining strategies one and two attain an approximation of 1.5 the optimal idle time and combining strategy one and third attain optimal idle time.

Let q be a power of the prime number p, let K = F q ( t ) , and let r ⩾ 2 be an integer. For points a , b ∈ K which are F q -linearly independent, we show that there exist positive constants N 0 and c 0 such that for each integer l ⩾ N 0 and for each generator τ of F q l / F q , we have that for all except N 0 values λ ∈ F q ‾ , the corresponding specializations a ( τ ) and b ( τ ) cannot have orders of degrees less than c 0 log ⁡ log ⁡ l as torsion points for the Drinfeld module Φ ( τ , λ ) : F q [ T ] ⟶ End F q ‾ ( G a ) (where G a is the additive group scheme), given by Φ T ( τ , λ ) ( x ) = τ x + λ x q + x q r .

Given a connected graph $G=(V,E)$ and a length function $\ell:E\to {\mathbb R}$ we let $d_{v,w}$ denote the shortest distance between vertex $v$ and vertex $w$. A $t$-spanner is a subset $E'\subseteq E$ such that if $d'_{v,w}$ denotes shortest distances in the subgraph $G'=(V,E')$ then $d'_{v,w}\leq t d_{v,w}$ for all $v,w\in V$. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p.~a 1-spanner that uses $\approx \frac12n\log n$ edges and that this is best possible. In particular, our result applies to the random graphs $G_{n,p}$ for $np\gg \log n$.

For a graph G and c R : E ( G ) → [ k ] , a path P between u , v ∈ V ( G ) is a rainbow path if for distinct e , e ′ ∈ E ( P ) , we have c R ( e ) ≠ c R ( e ′ ) . Rainbow k -Coloring takes a graph G and the objective is to check if there is c R : E ( G ) → [ k ] such that for all u , v ∈ V ( G ) there is a rainbow path between u and v. Two variants of the above problem are Subset Rainbow k -Coloring and Steiner Rainbow k -Coloring , where we are additionally given a subset S ⊆ V ( G ) × V ( G ) and S ′ ⊆ V ( G ) , respectively. Moreover, the objective is to check if there is c R : E ( G ) → [ k ] , such that there is a rainbow path for each ( u , v ) ∈ S and u , v ∈ S ′ , respectively. Under ETH, we obtain that for each k ≥ 3 : 1. Rainbow k -Coloring has no 2 o ( | E ( G ) | ) n O ( 1 ) -time algorithm. 2. Steiner Rainbow k -Coloring has no 2 o ( | S | 2 ) n O ( 1 ) -time algorithm. We also obtain that Subset Rainbow k -Coloring and Steiner Rainbow k -Coloring admit 2 O ( | S | ) n O ( 1 ) - and 2 O ( | S | 2 ) n O ( 1 ) -time algorithms, respectively.

We study growth rates of generalised Fibonacci sequences of a particular structure. These sequences are constructed from choosing two real numbers for the first two terms and always having the next term be either the sum or the difference of the two preceding terms where the pluses and minuses follow a certain pattern. In 2012, McLellan proved that if the pluses and minuses follow a periodic pattern and G n is the nth term of the resulting generalised Fibonacci sequence, then lim n → ∞ ⁡ | G n | 1 / n exists. We extend her results to recurrences of the form G m + 2 = α m G m + 1 ± G m if the choices of pluses and minuses, and of the α m follow a balancing word type pattern.

We represent a flow of a graph G = ( V , E ) as a couple ( C , e ) with C a circuit of G and e an edge of C , and its incidence vector is the 0 ∕ ± 1 vector χ C ∖ e − χ e . The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K 5 -minor, this cone can be described by the system x ( M ) ≥ 0 for all multicuts M of G . We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018).

An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. For a real number 0 f 1 , our objective is to preemptively guess the position f n within the request sequence of unknown length n : While processing the input, the online algorithm maintains a guess and is only allowed to update its guess to the position of the current element under investigation. We give a complete characterization of the optimal guessing strategies with respect to f : For f ≤ f 0 ≈ 0 . 1867 , the trivial algorithm that never updates its initial guess is (asymptotically) optimal. For f > f 0 , we give a randomized algorithm that in expectation places the guess at distance β ( f ) n from f n , where β is a non-elementary function, and we prove that this is optimal. Our findings show that the position f max n ≈ 0 . 2847 n is hardest to guess. We also give upper and lower bounds for a natural extension to weighted sequences. Our work can also be seen as the first randomized approach to the online checkpointing problem.

In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hierarchy for the solution of matroid optimization problems with polynomial objectives. This hierarchy allows to strengthen the relaxations of arbitrary linearized combinatorial optimization problems with polynomial objective functions and matroidal substructures. Finally, we give suggestions for future work.

A graph G is a B 0 -VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B 0 -VPG graph if it is a B 0 -VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B 0 -VPG graphs within four special graph classes: chordal graphs, tree-cographs, P 4 -tidy graphs and P 5 -free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B 0 -VPG graphs.

We prove a new PPA parity theorem: Given a bipartite graph G with bipartition ( A , B ) where B is a set of even-degree vertices, and given a tree T ∗ of G containing all of A , such that any vertex of B in T ∗ has degree 2 in T ∗ and such that each vertex of A which is not a leaf of T ∗ is met by an odd number of edges not in T ∗ , then there is an even number of trees of G containing all of A , with degree 0 or 2 at each vertex of B and with the same degree as T ∗ at each vertex of A . This theorem generalizes Berman’s generalization of Thomason’s generalization of Smith’s Theorem.

In d - Scattered Set we are given an (edge-weighted) graph and are asked to select at least k vertices, so that the distance between any pair is at least d , thus generalizing Independent Set . We provide upper and lower bounds on the complexity of this problem with respect to various standard graph parameters. In particular, we show the following: • For any d ≥ 2 , an O ∗ ( d tw ) -time algorithm, where tw is the treewidth of the input graph and a tight SETH-based lower bound matching this algorithm’s performance. These generalize known results for Independent Set . • d - Scattered Set is W[1]-hard parameterized by vertex cover (for edge-weighted graphs), or feedback vertex set (for unweighted graphs), even if k is an additional parameter. • A single-exponential algorithm parameterized by vertex cover for unweighted graphs, complementing the above-mentioned hardness. • A 2 O ( td 2 ) -time algorithm parameterized by tree-depth ( td ), as well as a matching ETH-based lower bound, both for unweighted graphs. We complement these mostly negative results by providing an FPT approximation scheme parameterized by treewidth. In particular, we give an algorithm which, for any error parameter ϵ > 0 , runs in time O ∗ ( ( tw ∕ ϵ ) O ( tw ) ) and returns a d ∕ ( 1 + ϵ ) -scattered set of size k , if a d -scattered set of the same size exists.

This work is devoted to the study of the Lovasz–Schrijver PSD-operator L S + applied to the edge relaxation ESTAB ( G ) of the stable set polytope STAB ( G ) of a graph G . In order to characterize the graphs G for which STAB ( G ) is achieved in one iteration of the L S + -operator, called L S + -perfect graphs, an according conjecture has been recently formulated ( L S + -Perfect Graph Conjecture). Here we study two graph classes defined by clique cutsets (pseudothreshold graphs and graphs without certain Truemper configurations). We completely describe the facets of the stable set polytope for such graphs, which enables us to show that one class is a subclass of L S + -perfect graphs, and to verify the L S + -Perfect Graph Conjecture for the other class.

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most 5 and that all vertices except for one have degree at most 54. In fact, all but at most O ( 1 ) vertices have degree 1, 2, 4, or 53. Let γ n = min ⁡ { ABC ( T ) : T is a tree of order n } . It is shown that γ n = 1 365 1 53 ( 1 + 26 55 + 156 106 ) n + O ( 1 ) ≈ 0.67737178 n + O ( 1 ) .

We show that any $m\times m$ matrix $M$ with integer entries and $\det M =\Delta \neq 0$ can be equipped by a finite digit set $\mathcal{D}\subset\mathbb{Z}^m$ such that any integer $m$-dimensional vector belongs to the set $$ {\rm Fin}_{\mathcal{D}}(M)= \Bigl\{\sum_{k\in I}M^k {d}_k : \emptyset\neq I \text{ finite subset of } \mathbb{Z} \text{ and } {d}_k \in \mathcal{D} \text{ for each } k \in I\Bigr\} \subset \bigcup\limits_{k\in \mathbb{N}} \frac{1}{\Delta^k}\mathbb{Z}^{m} \,. $$ We also characterize the matrices $M$ for which the sets $ {\rm Fin}_{\mathcal{D}}(M)$ and $ \bigcup\limits_{k\in \mathbb{N}} \frac{1}{\Delta^k}\mathbb{Z}^{m}$ coincide.

We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.

A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masa\v{r}\'ik and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\varepsilon$-flexible for list size $5$., Comment: 18 pages, 4 figures

We give a simple combinatorial description of an (n-2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s. We give a simple combinatorial description of an (n-2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s.

In an undirected graph, a proper (k, i)-coloring is an assignment of a set of k colors to each vertex such that any two adjacent vertices have at most i common colors. The (k, i)-coloring problem is to compute the minimum number of colors required for a proper (k, i)-coloring. This is a generalization of the classic graph coloring problem. Majumdar et al. [CALDAM 2017] studied this problem and showed that the decision version of the (k, i)-coloring problem is fixed parameter tractable (FPT) with tree-width as the parameter. They asked if there exists an FPT algorithm with the size of the feedback vertex set (FVS) as the parameter without using tree-width machinery. We answer this in positive by giving a parameterized algorithm with the size of the FVS as the parameter. We also give a faster and simpler exact algorithm for \((k, k-1)\)-coloring, and make progress on the NP-completeness of specific cases of (k, i)-coloring.

A vertex-deleted subgraph of a graph G is called a card of G . The reconstruction number of G is the minimum number of cards of G that suffices to determine G uniquely. A P-graph (Yongzhi, 1988) is a connected graph of order p with exactly two blocks, only one of them is K 2 and the other block has a vertex of degree p − 2 other than the cut vertex. It is shown that the reconstruction number of P-graphs is three in most of the cases, which strengthens the result of Bollobas (1990). Finally, we conclude that the reconstruction number of most of the separable graphs (connected graphs with a cut vertex) with pendant vertices is three if the reconstruction number of all other connected graphs without pendant vertices is three.

Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason’s extension of Smith’s Theorem. Our proof was not algorithmic. In this paper, I extend Thomason’s algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason’s Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E ( T ) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about “good” trees in general graphs. My proof provides an algorithm for finding a second “good” tree.

Let G be a graph and h : E ( G ) → [ 0 , 1 ] be a function. If g ( x ) ≤ ∑ e ∋ x h ( e ) ≤ f ( x ) for every x ∈ V ( G ) , then we call a graph F h with vertex set V ( G ) and edge set E h a fractional ( g , f ) -factor of G with indicator function h , where e ∋ x means the edge e incident to vertex x in G and E h = { e : e ∈ E ( G ) , h ( e ) > 0 } . We say that G admits property E ( m , n ) with respect to fractional ( g , f ) -factor if for any two sets of independent edges M and N with | M | = m , | N | = n and M ∩ N = 0 , G admits a fractional ( g , f ) -factor F h such that h ( e ) = 1 for any e ∈ M and h ( e ) = 0 for any e ∈ N . In this paper, we show a lower bound on binding number which guarantees a graph G to have property E ( 1 , n ) with respect to fractional ( g , f ) -factor.

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP -hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting.

We study the Bounded-Degree Light Approximate Shortest-path Tree problem: Given a metric space ( V , d ) on n points, a root r ∈ V and a degree bound b , the goal is to find a tree T spanning V with maximum degree at most b , total weight comparable to the weight of a Minimum Spanning Tree of ( V , d ) , and low stretch of tree distances from r to every vertex compared to input distances. Our main result is an algorithm that given a metric ( V , d ) with doubling dimension k , returns a tree T rooted at r spanning V with degree b and stretch max { O ( k ) / log b , O ( 1 ) } having weight within a constant factor the weight of a MST of ( V , d ) . On the negative side, we show that the trade-off between degree and stretch is unavoidable (up to constant factors in the Big- O ) even when the weight of the tree is not taken into account.

k -anonymous microaggregation of data in R d with d ≥ 2 is shown to be NP-hard for all k ≥ 4 , extending a previous result for the case k = 3 only. The proof uses similarities between microaggregation and the k -means problem. A reduction of Planar 3-SAT to the k -means clustering problem is adapted to 4-anonymous clustering. Then this construction is extended to arbitrary k ≥ 4 .

While presenting a combinatorial point of view to the class of equistable graphs, Miklavic and Milanic pointed out the inclusions among the classes of equistable, general partition and triangle graphs. Orlin conjectured that the first two classes were equivalent, but in 2014, Milanic and Trotignon showed that the three classes are all distinct, leading to the following hierarchy: general partition graphs ⊂ equistable graphs ⊂ triangle graphs. In this paper, we solve an open problem from Anbeek et al. (1997) by showing that all the above classes are equivalent when restricted to planar graphs. Additionally, we present short proofs on some structural properties of the general partition, equistable and triangle classes. In particular, we show that the general partition and triangle classes are both closed under the operations of substitution, induction and contraction of modules which allow us to recover several results in the literature.

We correct an error that appears in Kelly and Postle (2020) [2] . All of the main results remain valid after this correction.

Generalized Tur\'an problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem, maximizing the number of cliques of a fixed order in a graph with fixed number of vertices and bounded maximum degree, was recently completely resolved by Chase. Kirsch and Radcliffe raised a natural variant of this problem where the number of edges is fixed instead of the number of vertices. In this paper, we determine the maximum number of cliques of a fixed order in a graph with fixed number of edges and bounded maximum degree, resolving a conjecture by Kirsch and Radcliffe. We also give a complete characterization of the extremal graphs., Comment: minor changes

We consider the problem of enumerating all connected induced subgraphs of order k in an undirected graph G = ( V , E ) . Our main results are two enumeration algorithms with a delay of O ( k 2 Δ ) where Δ is the maximum degree in the input graph. This improves upon a previous delay bound (Elbassioni, 2015) for this problem. Moreover, we show that these two algorithms can be adapted to give algorithms for the problem of enumerating all connected induced subgraphs of order at most k with a delay of O ( k + Δ ) . Finally, we perform an experimental comparison of several enumeration algorithms for k ≤ 10 and k ≥ | V | − 3 .

Given an undirected graph G = ( V , E ) and a positive integer k ∈ 1 , … , | V | , we initiate the combinatorial study of stable sets of cardinality exactly k in G . Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

Series–parallel directed graphs have been generalized in various directions. Some of these generalizations control the structure of certain emerging induced subdigraphs called N ’s. They allow an efficient recognition by decomposition trees. We introduce another class of directed acyclic digraphs generalizing series–parallel directed graphs with less structure of induced N ’s. We show that they still can be efficiently recognized by a decomposition approach. In contrast, however, to the other mentioned generalization this decomposition is not unique and does not lead to a tree but a planar graph.

We prove that the ‘Upper Matching Conjecture’ of Friedland, Krop, and Markstrom and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every d and every large enough n divisible by 2d, a union of n / ( 2 d ) copies of the complete d -regular bipartite graph maximizes the number of independent sets and matchings of size k for each k over all d-regular graphs on n vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.

For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis (1991) introduced an extended formulation for the odd cycle inequalities of the stable set polytope, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there can exist exponentially many odd cycles in given graphs in general. We present another extended formulation for the odd cycle polytope that uses less variables and inequalities than Yannakakis’ formulation. Moreover, we compare the running time of both formulations as relaxations of the maximum stable set problem in a computational study.