Search

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

Let B n denote the family of all maximal bipartite planar graphs on n vertices. Given a family of graphs H , let B n (H) denote the family of all maximal bipartite planar graphs on n vertices which are not H -free. For graph G and a family of graphs H , if G is not H -free, the rainbow number of H in G , denoted by r b (G , H) , is the minimum positive integer t , such that any t -edge-colored graph G contains a rainbow copy of some graph in H. The rainbow number of H in maximal bipartite planar graph, denoted by r b (B n (H) , H) , is defined as max { r b (G , H) | G ∈ B n (H) }. A cycle on l vertices is denoted by C l. The graph obtained by arbitrarily adding one pendant edge at one vertex of a cycle C l is denoted by C l +. For any positive integer k , let C k ≔ { C 4 , C 6 , ... , C 2 k + 2 } and C k , 2 i 0 + ≔ (C k ∖ { C 2 i 0 }) ∪ { C 2 i 0 + } for some i 0 ∈ { 2 , 3 , ... , k + 1 }. In this paper, we firstly prove that r b (B n , C k) = r b (B n , C k , 2 i 0 +) = n + n − 2 k + 2 − 1 for any n ≥ max { 2 k + 2 , 5 } and k + 1 ≥ i 0 ≥ 2. We then obtain that r b (B n (H) , H) = 2 n − 4 for any n ≥ | V (H) | and k ≥ 3 , where H ∈ { C 2 k , C 2 k + }. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [ABSTRACT FROM AUTHOR]

The square of a graph G , denoted by G 2 , is obtained from G by adding an edge to connect every pair of vertices with a common neighbor in G. In this paper we prove that for every planar graph G with maximum degree at most 5, G 2 admits a proper vertex coloring using at most 17 colors, which improves the upper bound 18 recently obtained by Hou et al. (2023). [ABSTRACT FROM AUTHOR]

Cyclic vertex connectivity c κ and cyclic edge connectivity c λ are two important kinds of conditional connectivity, which reflect the number of vertices or edges that can be removed before the graph is disconnected and at least two components contain a cycle, respectively. They have important applications in various networks such as computer networks or biochemical networks. In addition, a fullerene is a special kind of molecule in chemistry. A classic fullerene graph is a 3-connected cubic planar graph with only pentagonal and hexagonal faces. (4, 5, 6)-fullerene graphs are atypical fullerene graphs which also contain 4-faces. In this paper, we prove that c κ = c λ for (4 , 5 , 6) -fullerene graphs except for four exceptional graphs with order less than 16. We also give O (ν) -algorithms to determine the cyclic vertex connectivity and the cyclic edge connectivity of (4 , 5 , 6) -fullerene graphs. [ABSTRACT FROM AUTHOR]

Four Color Theorem implies that the independence number of every planar graph is at least n / 4. A cactus graph is a connected planar graph whose block is either an edge or a cycle. In this paper, the lower bound for independence number of cactus graphs is improved to ⌈ n / 3 ⌉. Moreover, the maximum spectral radius of cactus graphs with fixed independence number is determined. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. Given a graph family G and a graph H , the anti-Ramsey number A R (G , H) is the maximum number of colors in an edge-coloring of a graph G ∈ G which has no rainbow copy of H. When G = { G } , we write A R (G , H) for short. Erdős, Simonovits and Sós introduced these numbers in the 1970s, they studied the case when G is a complete graph. Since then, many results have appeared considering G and H belonging to specific graph classes. In particular, Jendrol', Schiermeyer and Tu (Jendrol' et al., 2014) obtained an upper bound for A R (T n , k K 2) in terms of n and k for k ≥ 3 and n ≥ 2 k , where T n is the family of maximal planar graphs on n vertices. Jin and Ye (Jin and Ye, 2018) continued the study of anti-Ramsey numbers of matchings in planar graphs, by deriving an upper bound for A R (M n , k K 2) , where M n is the family of maximal outerplanar graphs on n vertices. In both works, examples are shown for which there are colorings using many colors while avoiding rainbow matchings, but the numbers of colors in these examples do not reach the upper bounds. The bounds of A R (T n , k K 2) were improved in following works by other researchers. This paper goes in the same direction of these two works, proving exact value for A R (B n , k K 2) in terms of n and k for n ≥ 6 and k ≥ 3 , where B n is the family of maximal bipartite outerplanar graphs on n vertices which contains a Hamilton cycle. [ABSTRACT FROM AUTHOR]

An odd c - coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing an odd number of times within its open neighborhood. A proper conflict-free c - coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing exactly once within its neighborhood. Clearly, every proper conflict-free c -coloring is also an odd c -coloring. Cranston conjectured that every graph G with maximum average degree mad (G) < 4 c c + 2 (where c ≥ 4) has an odd c -coloring, and he proved this conjecture for c ∈ { 5 , 6 }. Note that the bound 4 c c + 2 is best possible. Cho et al. solved Cranston's conjecture for c ≥ 5 , strengthening the result by transitioning from odd c -coloring to proper conflict-free c -coloring. However, they did not provide all the extremal non-colorable graphs G with mad (G) = 4 c c + 2 , which remains an open question of interest. In this paper, we tackle this intriguing extremal problem. We aim to characterize all non-proper conflict-free c -colorable graphs G with mad (G) = 4 c c + 2 . For the case of c = 4 , Cranston's conjecture is not true, as evidenced by the existence of a counterexample: a graph whose every block is a 5-cycle. Cho et al. proved that a graph G with mad (G) < 22 9 and no induced 5-cycles has an odd 4-coloring. We improve this result by proving that a graph G with mad (G) ≤ 22 9 (with equality allowed) is not odd 4-colorable if and only if G belongs to a specific class of graphs. On the other hand, Cho et al. established that a planar graph with girth at least 5 has an odd 6-coloring; we improve it by proving that a planar graph without 4 − -cycles adjacent to 7 − -cycles also has an odd 6-coloring. [ABSTRACT FROM AUTHOR]

Let A be the family of planar graphs without 4-cycles and 5-cycles. In 2013, Hill et al. proved that every graph G ∈ A has a partition dividing V (G) into three sets, where two of them are independent, and the other induces a graph with a maximum degree at most 3. In 2021 Cho, Choi, and Park conjectured that every graph G ∈ A has a partition dividing V (G) into two sets, where one set induces a forest, and the other induces a forest with a maximum degree at most 2. In this paper, we show that every graph G ∈ A has a partition dividing V (G) into two sets, where one set induces a forest, and the other induces a disjoint union of paths and subdivisions of K 1 , 3. The result improves the aforementioned result by Hill et al. and yields progress toward the conjecture of Cho, Choi, and Park. [ABSTRACT FROM AUTHOR]

A weak DP-coloring is a new coloring combining DP-coloring and vertex-partition, which was introduced by Sittitrai and Nakprasit. Sribunhung et al. proved that planar graphs without 4- and 7-cycles are weakly DP-( F 2 , F 2 , F 0 )-colorable. Fang and Wang proved that planar graphs without 4, 6-cycles or 4, 8-cycles are weakly DP-( F 2 , F 2 , F 0 )-colorable. In this paper, we show that planar graphs without 4- and 9-cycles are weakly DP-( F 2 , F 2 , F 0 )-colorable. [ABSTRACT FROM AUTHOR]

The Spherical Zoning Problem (SZP) seeks to partition a finite 3D volume comprised of convex polytope cells, or units, into k zones such that each zone's surface is spherical (i.e., homeomorphic to a sphere). A special case of the classical Connected Graph Partition Problem, SZP is motivated by applications in 3D geospatial partitioning such as airspace sectorization and oceanographic clustering. For general graph partitioning problems, local search optimization often considers the flip operation, which transfers one cell from its current zone, or part, to a neighboring zone in each iteration. Applying local search optimization to SZP requires new computational methods to assess flip feasibility; methods tailored to planar graph partitioning (e.g., for geographic districting) break down when faced with the spherical zones constraint due to inherent complexities when extending from 2D to 3D environments. This paper introduces the 3D geo-graph, a model for enforcing zone sphericity during a local search flip for solving SZP. The time complexity of SZP flip verification with the 3D geo-graph is, in the worst case, linear in the number of cells sharing some boundary with the flipped cell and linearithmic in the number of faces, edges, and vertices on the cell's surface. Computational experiments on space-filling honeycombs demonstrate that the 3D geo-graph enables efficient flip verification for large-scale SZP instances. • The Spherical Zoning Problem (SZP) is a 3D graph partitioning variant. • The 3D geo-graph model accelerates exploration of the space of SZP solutions. • Experiments on two natural cell structures confirm theoretical efficiency. • Potential applications include oceanographic zoning and airspace sectorization. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be drawn in the sphere or plane so that any edge has at most one crossing point with another edge. It is known that a 1-planar graph G with at least three vertices contains at most 4 | V (G) | − 8 edges, so G is optimal if G has exactly 4 | V (G) | − 8 edges. Fujisawa et al. (2018) first considered matching extension of optimal 1-planar graphs, obtained that each optimal 1-planar graph of even order is 1-extendable and characterized 2-extendable optimal 1-planar graphs and 3-matchings extendable to perfect matchings as well. In this short paper, we prove that no optimal 1-planar graph is 3-extendable. Further we mainly obtain that no 1-planar graph is 5-extendable by the discharge method and also construct a 4-extendable 1-planar graph. Finally we get that no 1-planar graph is 7-factor-critical and no optimal 1-planar graph is 6-factor-critical. [ABSTRACT FROM AUTHOR]

In a graph, G = (V , E) without an isolated vertex, a dominating set D ⊆ V , is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D such that distance between u and v is at most two in G. Given a graph G = (V , E) without an isolated vertex, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number , denoted by γ t 2 (G) , is the minimum cardinality of a semitotal dominating set of G. It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. (2020) proved that the problem can be solved in polynomial time for bounded MIM-width graphs, which include many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey (2019) also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem. [ABSTRACT FROM AUTHOR]

Given a graph G , a near-bipartition of G is a partition of V (G) into S and F , where S is a stable set, and F induces a forest. Given a graph G and a vertex set P inducing a P 4 in G , a vertex v is said partner of P if v ∈ V (G) ∖ P and G [ P ∪ { v } ] has at least two P 4 's. A graph G is P 4 -tidy if any P 4 in G has at most one partner. In this paper, we study the property of having a near-bipartition on P 4 -tidy graphs. We also consider a variant of that property that requires F being a tree. While the problem of determining whether an input graph has a near-bipartition is NP-complete even for graphs with maximum degree four, perfect graphs, graphs with diameter three, line graphs, and planar graphs, we show that the class of near-bipartite P 4 -tidy graphs admit finite forbidden induced subgraph characterization. In addition, we also present a characterization for P 4 -tidy graphs admitting a partition of its vertex set into a stable set and a tree. [ABSTRACT FROM AUTHOR]

The linear 2-arboricity of a graph G , denoted by la 2 (G) , is the least integer k such that G can be partitioned into k edge-disjoint forests, whose components are paths of length at most 2. A 1-planar graph is a graph that can be drawn in the Euclidean plane such that each edge crosses at most one edge. An IC-planar is a 1-planar graph satisfying the condition that each vertex is incident with at most one crossing edge. It is shown in this paper that every IC-planar graph G with maximum degree Δ has la 2 (G) ≤ ⌈ Δ + 1 2 ⌉ + 6. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V (G) and edge set E (G) , and let d (u , w) denote the length of a u − w geodesic in G. For any vertex v ∈ V (G) and any edge e = x y ∈ E (G) , let d (e , v) = min { d (x , v) , d (y , v) }. For any distinct edges e 1 , e 2 ∈ E (G) , let R { e 1 , e 2 } = { z ∈ V (G) : d (z , e 1) ≠ d (z , e 2) }. Kelenc, Tratnik and Yero [Discrete Appl. Math. 251 (2018) 204-220] introduced the notion of an edge resolving set and the edge dimension of a graph: A vertex subset S ⊆ V (G) is an edge resolving set of G if | S ∩ R { e 1 , e 2 } | ≥ 1 for any distinct edges e 1 , e 2 ∈ E (G) , and the edge dimension , edim (G) , of G is the minimum cardinality among all edge resolving sets of G. For a function g defined on V (G) and for U ⊆ V (G) , let g (U) = ∑ s ∈ U g (s). A real-valued function g : V (G) → [ 0 , 1 ] is an edge resolving function of G if g (R { e 1 , e 2 }) ≥ 1 for any distinct edges e 1 , e 2 ∈ E (G). The fractional edge dimension , edim f (G) , of G is min { g (V (G)) : g is an edge resolving function of G }. Note that edim f (G) reduces to edim (G) if the codomain of edge resolving functions is restricted to { 0 , 1 }. In this paper, we introduce and study the fractional edge dimension of graphs, and we obtain some general results on the edge dimension of graphs. We show that there exist two non-isomorphic graphs on the same vertex set with the same edge metric coordinates. We construct two graphs G and H such that H ⊂ G and both edim (H) − edim (G) and edim f (H) − edim f (G) can be arbitrarily large. We show that a graph G with edim (G) = 2 cannot have K 5 or K 3 , 3 as a subgraph, and we construct a non-planar graph H satisfying edim (H) = 2. It is easy to see that, for any connected graph G of order at least three, 1 ≤ edim f (G) ≤ | V (G) | 2 ; we characterize graphs G satisfying edim f (G) = 1 and examine some graph classes satisfying edim f (G) = | V (G) | 2 . We also determine the fractional edge dimension for some classes of graphs. [ABSTRACT FROM AUTHOR]

A graph is k -degenerate if every subgraph H has a vertex v with d H (v) ≤ k. The class of degenerate graphs plays an important role in the graph coloring theory. Observed that every k -degenerate graph is (k + 1) -choosable and (k + 1) -DP-colorable. Bernshteyn and Lee defined a generalization of k -degenerate graphs, which is called weakly k -degenerate. The weak degeneracy plus one is an upper bound for many graph coloring parameters, such as choice number, DP-chromatic number and DP-paint number. In this paper, we give two sufficient conditions for a plane graph without 4- and 6-cycles to be weakly 2-degenerate, which implies that every such graph is 3-DP-colorable and near-bipartite, where a graph is near-bipartite if its vertex set can be partitioned into an independent set and an acyclic set. [ABSTRACT FROM AUTHOR]

A (d , h) -decomposition of a graph G is an ordered pair (D , H) such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G − E (H) with maximum out-degree at most d. In this paper, we prove that for l ∈ { 5 , 6 , 7 , 8 , 9 } , every planar graph without 4- and l -cycles is (2 , 1) -decomposable. As a consequence, for every planar graph G without 4- and l -cycles, there exists a matching M , such that G − M is 3-DP-colorable and has Alon-Tarsi number at most 3. In particular, G is 1-defective 3-DP-colorable, 1-defective 3-paintable and 1-defective 3-choosable. These strengthen the results in [Discrete Appl. Math. 157 (2) (2009) 433–436] and [Discrete Math. 343 (2020) 111797]. [ABSTRACT FROM AUTHOR]

Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G , and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square-graphs by a sequence of "square-boundary" amalgamations. These considerations also lead to an O (n log n) -time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs. [ABSTRACT FROM AUTHOR]

The neighbor-distinguishing index χ a ′ (G) of a graph G is the smallest k for which G admits a proper edge k -coloring such that any two adjacent vertices have different color sets of their incident edges. It was conjectured that every simple graph G , different from a 5-cycle, without isolated edges has χ a ′ (G) ≤ Δ + 2. In 2004, Horňák et al. confirmed the conjecture for planar graphs with Δ ≥ 12. Recently, Cheng et al. extended this result to planar graphs with Δ ≥ 11. In this paper, we furthermore improve the result to planar graphs with Δ ≥ 10. [ABSTRACT FROM AUTHOR]

In the study of edge colorings of ordinary graphs, Vizing's adjacency lemma plays a crucial role. In this paper, we extend Vizing's adjacency lemma to critical signed graphs with even maximum degrees. As an application, we show that the signed planar graph conjecture is true for signed planar graphs with maximum degree at least 8, and that every k -degenerate signed graph with maximum degree at least 2 k is class one. [ABSTRACT FROM AUTHOR]

The problems of recognizing series–parallel graphs, outerplanar graphs, and generalized series–parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O (| E | + | V |) -time certifying algorithm that simultaneously determines if a graph G = (V , E) is series–parallel, outerplanar, or generalized series–parallel is presented. The positive certificates are a construction sequence for constructing G if G is series–parallel, a generalized construction sequence for constructing G if G is generalized series–parallel but not series–parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components. [ABSTRACT FROM AUTHOR]

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM (O (log n)) protocol for this class, that is, a distributed interactive protocol with O (log n) -bit proof size in n -node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a dMAM (O (log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O (log n) bits. This result also holds for the class of graphs with bounded non-orientable genus , that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes , i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus. [ABSTRACT FROM AUTHOR]

In this short paper, we introduce a new vertex coloring whose motivation comes from our series on odd edge-colorings of graphs. A proper vertex coloring φ of a graph G is said to be odd if for each non-isolated vertex x ∈ V (G) there exists a color c such that φ − 1 (c) ∩ N (x) is odd-sized. We prove that every simple planar graph admits an odd 9-coloring, and conjecture that 5 colors always suffice. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the edge monitoring problem. A vertex v monitors an edge e if both endpoints together with v form a triangle in the graph. Given a graph G = (V , E) and a weight function on edges c where c (e) is the number of monitors that needs the edge e , the problem is to seek a minimum subset of monitors S such that every edge e in the graph is monitored by at least c (e) vertices in S. Therefore, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices. [ABSTRACT FROM AUTHOR]

Let G be a finite, simple, and connected graph with the vertex set V and the edge set E. The distance between the vertex u and the edge e = v w is defined as d (u , e) = min { d (u , v) , d (u , w) }. A vertex x distinguishes two edges e 1 , e 2 if d (x , e 1) ≠ d (x , e 2). A subset L e of V is called an edge metric generator for G if every two distinct edges of G are distinguished by some vertex of L e. The minimum cardinality of an edge metric generator for G is called the edge metric dimension and is denoted by d i m e (G). Similarly, a vertex x distinguishes two elements (vertices or edges) u , v ∈ V ∪ E if d (x , u) ≠ d (x , v). A subset L m of V is called a mixed metric generator for G if every two distinct elements (vertices and edges) of G are distinguished by some vertex of L m. The minimum cardinality of a mixed metric generator for G is called the mixed metric dimension and is denoted by d i m m (G). In this paper, we study the edge metric dimension and mixed metric dimension of planar graph Q n. We prove that the edge metric dimension and the mixed metric dimension of Q n are both finite and do not depend upon the number of vertices. [ABSTRACT FROM AUTHOR]

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

The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we consider the following ▪ (▪) problem. The input is a graph G = (V , E) , with each vertex in the set V having an assigned color, " ▪ " or " ▪ ". We seek a maximum-cardinality subset V ′ ⊆ V of vertices that is ▪ (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices), such that the subgraph induced by the vertex set V ′ in G is connected. We show that the BCS problem is NP-hard, even for bipartite graphs G (with red/blue color assignment not necessarily being a proper 2-coloring). Further, we consider this problem on various graph classes, e.g., planar graphs, chordal graphs, trees, split graphs, bipartite graphs with a proper red/blue 2-coloring, and graphs with diameter 2. For each of these classes we either prove NP-hardness or design a polynomial time algorithm. [ABSTRACT FROM AUTHOR]

An (F , F d) -partition of a graph G is a partition of V (G) into sets V 1 and V 2 such that the induced graph G [ V 1 ] is a forest and G [ V 2 ] is a forest of maximum degree at most d. It was known that every planar graph without triangles is (F , F 3) -partitionable. In this paper, we show that planar graphs without triangles and chordal 6-cycles are (F , F 2) -partitionable. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper coloring of the vertices of G in which each vertex of the graph dominates every vertex of some color class, where a vertex dominates itself and all vertices adjacent to it. The dominator chromatic number of G is the minimum number of colors among all dominator coloring of G. A total dominator coloring of a graph G is a proper coloring of the vertices of G in which each vertex of the graph dominates every vertex of some color class other than its own. The total dominator chromatic number of G is the minimum number of colors among all total dominator coloring of G. In this paper, we present bounds on the dominator chromatic number and total dominator chromatic number of a planar graphs with small diameter. In particular we show the dominator chromatic number of a planar graph of diameter 2 is at most 5. We also present results for the special cases of outerplanar graphs and bipartite planar graphs. [ABSTRACT FROM AUTHOR]

An adjacent vertex distinguishing edge coloring is a proper edge coloring such that any two adjacent vertices have distinct sets consisting of colors of their incident edges. It was conjectured that if G is a connected graph with at least 6 vertices, then χ a ′ (G) ≤ Δ (G) + 2. In this paper, we consider the list version of adjacent vertex distinguishing edge coloring and show that if G is a planar graph without isolated edges, then ch a ′ (G) ≤ max { 13 , Δ (G) + 2 } , where ch a ′ (G) is the adjacent vertex distinguishing edge choosability. This result implies that the above conjecture holds for planar graphs with maximum degree at least 11. Our approach is based on the Combinatorial Nullstellensatz and the discharging method. [ABSTRACT FROM AUTHOR]

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 ∈ L (v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvořák, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph G is ɛ -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 ɛ -fraction of the requests in S. It is conjectured that planar graphs are ɛ -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řík and show that planar graphs without K 4 − are ɛ -flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are ɛ -flexible for list size 4. Finally, we introduce a new (slightly weaker) form of ɛ -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 ɛ -flexible for list size 5. [ABSTRACT FROM AUTHOR]

For a set of nonnegative integers c 1 , ... , c k , a (c 1 , c 2 , ... , c k) -coloring of a graph G is a partition of V (G) into V 1 , ... , V k such that for every i , 1 ≤ i ≤ k , G [ V i ] has maximum degree at most c i. In this paper, we prove that all planar graphs without 4-cycles and intersecting triangles are (1 , 1 , 0) -colorable. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k -degenerate graph in O k time per solution using O n + m space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H -minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. [ABSTRACT FROM AUTHOR]

While presenting a combinatorial point of view to the class of equistable graphs, Miklavič and Milanič 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, Milanič 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. [ABSTRACT FROM AUTHOR]

An acyclic digraph in which every vertex has indegree at most i and outdegree at most j is called an (i , j) digraph for some positive integers i and j. Lee et al. (2017) studied the phylogeny graphs of (2 , 2) digraphs and gave sufficient conditions and necessary conditions for a (2 , 2) digraph to have a chordal phylogeny graph. Their work was motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have chordal moral graphs (phylogeny graphs are called moral graphs in Bayesian network theory). In this paper, we extend their work. We completely characterize the phylogeny graph of a (1 , i) digraph and an (i , 1) digraph, respectively, for any positive integer i. Then, we study phylogeny graphs of (2 , j) digraphs to show that the phylogeny graph of a (2 , j) digraph D is chordal if the underlying graph of D is chordal for any positive integer j. Especially, we show that as long as the underlying graph of a (2 , 2) digraph is chordal, its phylogeny graph is not only chordal but also planar. [ABSTRACT FROM AUTHOR]