Search

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker's layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemerédi's regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. However, we prove that the condition cannot be used to find solutions (as opposed to approximating the optimal value) in general. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular, we show that a monotone class of graphs is hyperfinite if and only if it is fractionally-treewidth-fragile and has bounded degree. [ABSTRACT FROM AUTHOR]

Given a simple graph G , a proper total- k -coloring c : V (G) ∪ E (G) → { 1 , 2 , ... , k } is called neighbor sum distinguishing if ∑ c (u) ≠ ∑ c (v) for any two adjacent vertices u , v ∈ V (G) , where ∑ c (v) denote the sum of the color of v and the colors of edges incident with v. The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by χ Σ ′ ′ (G). Pilśniak and Woźniak conjected that χ Σ ′ ′ (G) ≤ Δ (G) + 3 for any simple graph G. Let L x (x ∈ V (G) ∪ E (G)) be a set of lists of real numbers and each of size k. The least number k for which for any specified collection of such lists, there exists a neighbor sum distinguish total coloring of G with colors from L x for each x ∈ V (G) ∪ E (G) is called the neighbor sum distinguishing total choosability of G , denoted by c h Σ ′ ′ (G). In this paper, it is proved that c h Σ ′ ′ (G) ≤ max { Δ (G) + 3 , 10 } for any planar graph G without intersecting 4-cycles. [ABSTRACT FROM AUTHOR]

A vertex coloring of a graph G is said to be a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors, and the least number of colors for which G admits a 2-distance coloring is known as the 2-distance chromatic number χ 2 (G) of G. When G is a planar graph with girth at least 6 and maximum degree Δ ≥ 6 , we prove that χ 2 (G) ≤ Δ + 4. This improves the best known bound for 2-distance coloring of planar graphs with girth six. [ABSTRACT FROM AUTHOR]

For a non-trivial connected graph Γ = Γ(V,E), an ordered subset U of vertices resolves any pair of different vertices k1,k2 ∈ V, if d(k,k1)≠d(k,k2) for some k ∈ U. Such a set U is said to be a resolving set (RS) for Γ and the smallest cardinality of U is called the metric dimension of Γ. A RS U∗ for Γ is said to be fault-tolerant resolving set (FTRS) if the property of resolving Γ holds by U∗−{k} for every k in U∗. The minimum cardinality of such a set U∗ is called the fault-tolerant metric dimension (FTMD) of Γ. It is generally denoted by dimft(Γ). In this paper, the notion of FTRS and that of FTMD have been determined for two complex families of infinite convex polytope graphs, which are obtained by joining certain copies of the prism graph together with an antiprism graph. For these two families of planar graph (viz., Dmk & Emk), we investigate several properties as well as we compare their metric and FTMD. [ABSTRACT FROM AUTHOR]

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group G, we define a simple undirected bipartite graph Γ(G) with the vertex set V (Γ(G)) = A ∪ B, where A is the set of all elements of the group G and B is the set of all subgroups H of G such that H≠{e} and two vertices a ∈ A and H ∈ B are adjacent if and only if a2 ∈ H. Here, we classify all the finite groups G whose bipartite graphs Γ(G) are planar. In addition, we also classify the finite groups G such that Γ(G) is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph Γ(G) corresponding to an infinite group G has also been investigated here. It is also observed that Γ(G) satisfies Vizing’s conjecture. [ABSTRACT FROM AUTHOR]

The k - 2 -distance coloring of the graph G refers to that it satisfies the mapping: ϕ : V (G) → { 1 , 2 , ... , k } , such that the vertex u and v , whose distance is at most 2 , receive different colors, namely ϕ (u) ≠ ϕ (v). Denote χ 2 l (G) = min { k | G   has a list k - 2 - d i s t a n c e c o l o r i n g } , which is a list 2-distance chromatic number of the graph G. This paper proves that χ 2 l (G) ≤ Δ + 5 for the graph G without 3-cycles and intersecting 4-cycles and Δ ≥ 2 4. [ABSTRACT FROM AUTHOR]

A 2-distance coloring of a graph is a proper k -coloring in which any two vertices with distance at most two get different colors. The 2-distance number is the smallest number k such that G has a 2-distance k -coloring, denoted as χ 2 (G). In 1977, Wegner conjectured that for each planar graph G with maximum degree Δ , χ 2 (G) ≤ 7 if Δ ≤ 3 , χ 2 (G) ≤ Δ + 5 if 4 ≤ Δ ≤ 7 , and χ 2 (G) ≤ ⌊ 3 Δ 2 ⌋ + 1 if Δ ≥ 8. In 2001, Thomassen supported the conjecture by proving the case Δ = 3. The conjecture is still open even for Δ = 4. In this paper, we show that χ 2 (G) ≤ 1 7 for the case Δ ≤ 5 which improves the upper bound 18 recently obtained by Hou et al. [ABSTRACT FROM AUTHOR]

For a graph G and a sequence S = (s1,s2,...,sk) of positive integers with s1 ≤ S2 ≤ ... ≤ Sk, we say that G is packing S-colorable or G admits a packing S-coloring, if V(G) can be partitioned into k subsets V1, V2, ..., Vk such that for each 1 ≤ i ≤ k and any x, y ∈ V, x ≠ y, there is d(x, y) ≥ Si + 1, where d(x, y) is the distance of vertices x and y in G. For simplicity, we define the packing S-coloring as packing [2, 8] coloring while S = (1, 1, 2, 2, 2, 2, 2, 2, 2, 2). In this paper, we proved that every planar graph G with maximum degree Δ ≤ 4 is packing [2,8] colorable. [ABSTRACT FROM AUTHOR]

Tutte's embedding theorem states that every 3-connected graph without a K 5 - or K 3 , 3 -minor (i.e., a planar graph) is embedded in the plane if the outer face is in convex position and the interior vertices are convex combinations of their neighbors. We show that this result extends to simply connected tetrahedral meshes in a natural way: for the tetrahedral mesh to be embedded if the outer polyhedron is in convex position and the interior vertices are convex combination of their neighbors it is sufficient (but not necessary) that the graph of the tetrahedral mesh contains no K 6 and no K 3 , 3 , 1 , and all triangles incident on three boundary vertices are boundary triangles. [ABSTRACT FROM AUTHOR]

The planar Turán numberexP(n,H) of a graph H is the maximum number of edges in an n‐vertex planar graph without H as a subgraph. Let Ck denote the cycle of length k. The planar Turán number exP(n,Ck) is known for k≤7. We show that dense planar graphs with a certain connectivity property (known as circuit graphs) contain large near triangulations, and we use this result to obtain consequences for planar Turán numbers. In particular, we prove that there is a constant D so that exP(n,Ck)≤3n−6−Dn/klog2 3 for all k≥4 and n≥klog2 3. When k≥11 this bound is tight up to the constant D and proves a conjecture of Cranston, Lidický, Liu, and Shantanam. [ABSTRACT FROM AUTHOR]

For two integers s ≥ 0 , t ≥ 0 , a graph G is (s , t) - supereulerian , if for every pair of disjoint subsets X , Y ⊂ E (G) , with | X | ≤ s , | Y | ≤ t , G has a spanning eulerian subgraph H with X ⊂ E (H) and Y ∩ E (H) = 0̸. Pulleyblank (1979) proved that even within planar graphs, determining if a graph G is (0 , 0) -supereulerian is NP-complete. Xiong et al. (2021) identified a function j 0 (s , t) such that every (s , t) -supereulerian graph must have edge connectivity at least j 0 (s , t). Examples have been found that having edge connectivity at least j 0 (s , t) is not sufficient to warrant the graph to be (s , t) -supereulerian. A graph family S is optimally (s , t) - supereulerian if for every pair of given non-negative integers (s , t) , a graph G ∈ S is (s , t) -supereulerian if and only if κ ′ (G) ≥ j 0 (s , t). Hence the (s , t) -supereulerian problem in such a graph family can be solved in polynomial time with minimally required edge-connectivity. In this research, we prove that the family of all squares of graphs of order at least 5 is optimally (s , t) -supereulerian. [ABSTRACT FROM AUTHOR]

ABSTRACT In 1956, Tutte proved the celebrated theorem that every 4‐connected planar graph is Hamiltonian. This result implies that every more than 32 $\frac{3}{2}$‐tough planar graph on at least three vertices is Hamiltonian and so has a 2‐factor. Owens in 1999 constructed non‐Hamiltonian maximal planar graphs of toughness arbitrarily close to 32 $\frac{3}{2}$ and asked whether there exists a maximal non‐Hamiltonian planar graph of toughness exactly 32 $\frac{3}{2}$. In fact, the graphs Owens constructed do not even contain a 2‐factor. Thus the toughness of exactly 32 $\frac{3}{2}$ is the only case left in asking the existence of 2‐factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. In this paper, we close this gap by constructing a maximal 32 $\frac{3}{2}$‐tough plane graph with no 2‐factor, answering the question asked by Owens as well as by Bauer, Broersma, and Schmeichel. [ABSTRACT FROM AUTHOR]

ABSTRACT If L $L$ is a list assignment of r $r$ colors to each vertex of an n $n$‐vertex graph G $G$, then an equitable L $L$‐coloring of G $G$ is a proper coloring of vertices of G $G$ from their lists such that no color is used more than ⌈n/r⌉ $\lceil n/r\rceil $ times. A graph is equitably r $r$‐choosable if it has an equitable L $L$‐coloring for every r $r$‐list assignment L $L$. In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer r $r$ every graph G $G$ with maximum degree at most r−1 $r-1$ is equitably r $r$‐choosable. The main result of this paper is that for each r≥9 $r\ge 9$ and each planar graph G $G$, a stronger statement holds: if the maximum degree of G $G$ is at most r $r$, then G $G$ is equitably r $r$‐choosable. In fact, we prove the result for a broader class of graphs—the class ℬ ${\rm{ {\mathcal B} }}$ of the graphs in which each bipartite subgraph B $B$ with |V(B)|≥3 $|V(B)|\ge 3$ has at most 2|V(B)|−4 $2|V(B)|-4$ edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in ℬ ${\rm{ {\mathcal B} }}$, in particular, for all planar graphs. We also introduce the new stronger notion of strongly equitable (SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE r $r$‐choosable, then it is both equitably r $r$‐choosable and equitably r $r$‐colorable, while neither of being equitably r $r$‐choosable and equitably r $r$‐colorable implies the other. [ABSTRACT FROM AUTHOR]

An (n , m) -graph is characterized by n types of arcs and m types of edges. A homomorphism of an (n , m) -graph G to an (n , m) -graph H , is a vertex mapping that preserves adjacency, direction, and type. The (n , m) -chromatic number of G , denoted by χ n , m (G) , is the minimum value of | V (H) | such that there exists a homomorphism of G to H. The theory of homomorphisms of (n , m) -graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic, Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of G is bounded by a function of χ n , m (G) but not the other way around. Additionally, we show that the acyclic chromatic number of G is bounded by a function of χ n , m (G) , a result already known in the reverse direction. Furthermore, we prove that the (n , m) -chromatic number for the family of graphs with maximum average degree less than 2 + 2 4 (2 n + m) − 1 , including the subfamily of planar graphs with girth at least 8 (2 n + m) , equals 2 (2 n + m) + 1. This improves upon previous findings, which proved the (n , m) -chromatic number for planar graphs with girth at least 10 (2 n + m) − 4 is 2 (2 n + m) + 1. It is established that the (n , m) -chromatic number for the family T 2 of partial 2-trees is both bounded below and above by quadratic functions of (2 n + m) , with the lower bound being tight when (2 n + m) = 2. We prove 14 ≤ χ (0 , 3) (T 2) ≤ 15 and 14 ≤ χ (1 , 1) (T 2) ≤ 21 which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof. [ABSTRACT FROM AUTHOR]

The planar Turán number of a graph H , denoted by e x P (n , H) , is the maximum number of edges in an n -vertex H -free planar graph. Recently, D. Ghosh, et al. initiated the topic of double stars and prove that e x P (n , S 2 , 5) ≤ 20 7 n. In this paper, we continue to study this and give a better upper bound e x P (n , S 2 , 5) ≤ 19 7 n − 18 7 for all n ≥ 1 , with equality when n = 12. This improves Ghosh's result. [ABSTRACT FROM AUTHOR]

ABSTRACT A graph is hypohamiltonian if it is non‐hamiltonian, but the deletion of every single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 40 vertices, a result due to Jooyandeh, McKay, Östergård, Pettersson, and Zamfirescu. That result is here improved upon by two planar hypohamiltonian graphs on 34 vertices. We exploited a special subgraph contained in two graphs of Jooyandeh et al., and modified it to construct the two 34‐vertex graphs and six planar hypohamiltonian graphs on 37 vertices. Each of the 34‐vertex graphs has 26 cubic vertices, improving upon the result of Jooyandeh et al. that planar hypohamiltonian graphs have 30 cubic vertices. We use the 34‐vertex graphs to construct hypohamiltonian graphs of order 34 with crossing number 1, improving the best‐known bound of 36 due to Wiener. Whether there exists a planar hypohamiltonian graph on 41 vertices was an open question. We settled this question by applying an operation introduced by Thomassen to the 37‐vertex graphs to obtain several planar hypohamiltonian graphs on 41 vertices. The 25 planar hypohamiltonian graphs on 40 vertices of Jooyandeh et al. have no nontrivial automorphisms. The result is here improved upon by six planar hypohamiltonian graphs on 40 vertices with nontrivial automorphisms. [ABSTRACT FROM AUTHOR]

Given a simple graph G and a proper total-k-coloring φ from V (G) ∪ E(G) to {1, 2,...,k}. Let f(v) = φ(v)Πuv∈E(G)φ(uv). The coloring φ is neighbor product distinguishing if f(u) ≠ f(v) for each edge uv ∈ E(G). The neighbor product distinguishing total chromatic number of G, denoted by χ Π ′ ′ (G) , is the smallest integer k such that G admits a k-neighbor product distinguishing total coloring. Li et al. conjectured that χ Π ′ ′ (G) ≤ Δ (G) + 3 for any graph with at least two vertices. Dong et al. showed that conjecture holds for planar graphs with maximum degree at least 10. By using the famous Combinatorial Nullstellensatz, we prove that if G is a planar graph without 5-cycles, then χ Π ′ ′ (G) ≤ max { Δ (G) + 2 , 12 } . [ABSTRACT FROM AUTHOR]

In this paper, we introduce an invariant of alternating knots and links (called here WRP), namely, a pair of integer polynomials associated with their two checkerboard planar graphs from their minimal diagram. We prove that the invariant is well-defined and give its values obtained from calculations for some knots in the tables. This invariant is strong enough to distinguish all knots in the tables with up to 10 crossings (including their mirror images). We compare the strength of the new invariant with classical invariants, including the three-variable Kauffman bracket. [ABSTRACT FROM AUTHOR]

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let qB(G) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider qB(G) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ=Δ(G) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that qB(G)≤2Δ+8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, qB(G)≤2Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and qB(G)≤Δ+1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ≥4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, qB(G)≤2Δ(G) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and qB(G)≤Δ(G) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

This paper studies two variants of defective acyclic coloring of planar graphs. For a graph G $G$ and a coloring φ $\varphi $ of G $G$, a 2‐colored cycle (2CC) transversal is a subset E′ ${E}^{^{\prime} }$ of E(G) $E(G)$ that intersects every 2‐colored cycle. Let k $k$ be a positive integer. We denote by mk(G) ${m}_{k}(G)$ the minimum integer m $m$ such that G $G$ has a proper k $k$‐coloring which has a 2CC transversal of size m $m$, and by mk′(G) ${m}_{k}^{^{\prime} }(G)$ the minimum size of a subset E′ ${E}^{^{\prime} }$ of E(G) $E(G)$ such that G−E′ $G-{E}^{^{\prime} }$ is acyclic k $k$‐colorable. We prove that for any n $n$‐vertex 3‐colorable planar graph G,m3(G)≤n−3 $G,{m}_{3}(G)\le n-3$ and for any planar graph G,m4(G)≤n−5 $G,{m}_{4}(G)\le n-5$ provided that n≥5 $n\ge 5$. We show that these upper bounds are sharp: there are infinitely many planar graphs attaining these upper bounds. Moreover, the minimum 2CC transversal E′ ${E}^{^{\prime} }$ can be chosen in such a way that E′ ${E}^{^{\prime} }$ induces a forest. We also prove that for any planar graph G,m3′(G)≤(13n−42)∕10 $G,{m}_{3}^{^{\prime} }(G)\le (13n-42)\unicode{x02215}10$ and m4′(G)≤(3n−12)∕5 ${m}_{4}^{^{\prime} }(G)\le (3n-12)\unicode{x02215}5$. [ABSTRACT FROM AUTHOR]

The cycle spectrum CS(G) ${\mathscr{CS}}(G)$ of a graph G $G$ is the set of the cycle lengths in G $G$. Let G ${\mathscr{G}}$ be a graph class. For any integer k≥3 $k\ge 3$, define fG(k) ${f}_{{\mathscr{G}}}(k)$ to be the least integer k′≥k ${k}^{^{\prime} }\ge k$ such that for any G∈G $G\in {\mathscr{G}}$ with circumference at least k,CS(G)∩[k,k′]≠∅ $k,{\mathscr{CS}}(G)\cap [k,{k}^{^{\prime} }]\ne \varnothing $. Denote by P,P3,PC ${\mathscr{P}},{\mathscr{P}}3,{\mathscr{PC}}$, and PC3 ${\mathscr{PC}}3$ the classes of 3‐connected planar graphs, 3‐connected cubic planar graphs, 3‐connected claw‐free planar graphs, and 3‐connected claw‐free cubic planar graphs, respectively. The values of fP(k) ${f}_{{\mathscr{P}}}(k)$ and fP3(k) ${f}_{{\mathscr{P}}3}(k)$ were known for all k≥3 $k\ge 3$. In the first part of this article, we prove the claw‐free version of these results by giving the values of fPC(k) ${f}_{{\mathscr{PC}}}(k)$ and fPC3(k) ${f}_{{\mathscr{PC}}3}(k)$ for all k≥3 $k\ge 3$. In the second part we study the cycle spectra of 4‐connected planar graphs without 4‐cycles. Bondy conjectured that every 4‐connected planar graph G $G$ has all cycle lengths from 3 to ∣V(G)∣ $| V(G)| $ except possibly one even length. The truth of this conjecture would imply that every 4‐connected planar graph G $G$ without 4‐cycles has all cycle lengths other than 4. It was already known that {3,5,...,9}∪{⌊∣V(G)∣∕2⌋,...,⌈∣V(G)∣∕2⌉+3}∪{∣V(G)∣−7,...,∣V(G)∣}⊆CS(G) $\{3,5,\ldots ,9\}\cup \{\lfloor | V(G)| \unicode{x02215}2\rfloor ,\ldots ,\lceil | V(G)| \unicode{x02215}2\rceil +3\}\cup \{| V(G)| -7,\ldots ,| V(G)| \}\subseteq {\mathscr{CS}}(G)$. We prove that G $G$ can be embedded in the plane such that for any k∈{⌊∣V(G)∣∕2⌋,...,∣V(G)∣},G $k\in \{\lfloor | V(G)| \unicode{x02215}2\rfloor ,\ldots ,| V(G)| \},G$ has a k $k$‐cycle C $C$ and all vertices not in C $C$ lie in the exterior of C $C$. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Given a graph G and a parameter r, we define the r-local matroid of G to be the matroid generated by its cycles of length at most r. Extending Whitney's abstract planar duality theorem from 1932, we prove that for every r the r-local matroid of G is co-graphic if and only if G admits a certain type of embedding in a surface, which we call r-planar embedding. The maximum value of r such that a graph G admits an r-planar embedding is closely related to face-width, and such embeddings for this maximum value of r are quite often embeddings of minimum genus. Unlike minimum genus embeddings, these r-planar embeddings can be computed in polynomial time. This provides the first systematic and polynomially computable method to construct for every graph G a surface so that G embeds in that surface in an optimal way (phrased in our notion of r-planarity). [ABSTRACT FROM AUTHOR]

Inspired by the seminal result that a graph and an associated rotation system uniquely determine the topology of a closed manifold, we propose a combinatorial method for reconstruction of surfaces from points. Our method constructs a spanning tree and a rotation system. Since the tree is trivially a planar graph, its rotation system determines a genus zero surface with a single face which we proceed to incrementally refine by inserting edges to split faces. In order to raise the genus, special handles are added in a later stage by inserting edges between different faces and thus merging them. We apply our method to a wide range of input point clouds in order to investigate its effectiveness, and we compare our method to several other surface reconstruction methods. It turns out that our approach has two specific benefits over these other methods. First, the output mesh preserves the most information from the input point cloud. Second, our method provides control over the topology of the reconstructed surface. Code is available on https://github.com/cuirq3/RsR. [ABSTRACT FROM AUTHOR]

An IC-planar graph is a graph that can be drawn in the plane in such a way that each edge is crossed at most once and each vertex is incident with at most one crossed edge. In this paper, we show that every IC-planar graph can be colored with nine colors so that for every non-isolate vertex there exists a color occurring odd times in its neighbors. [ABSTRACT FROM AUTHOR]

How many copies of a fixed odd cycle, C2 m + 1 ${C}_{2m+1}$, can a planar graph contain? We answer this question asymptotically for m ∈{2 , 3 , 4 } $m\in \{2,3,4\}$ and prove a bound which is tight up to a factor of 3/2 for all other values of m $m$. This extends the prior results of Cox and Martin and of Lv, Győri, He, Salia, Tompkins, and Zhu on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass μ $\mu $ on the edges of some clique maximizes the probability that m $m$ edges sampled independently from μ $\mu $ form either a cycle or a path? [ABSTRACT FROM AUTHOR]

We characterize planar graphs and graph minors among other graph theoretic notions in terms of right-angled Artin groups (RAAGs). For this, we determine all sets of elements in RAAGs with ears as underlying graphs that are exactly the sets of vertex generators. Generalizing ear decompositions of graphs to loose ear decompositions, we characterize both decompositions in terms of RAAGs. The desired results follow as applications of loose ear decompositions of RAAGs. [ABSTRACT FROM AUTHOR]

A cover of a graph G is a graph H with vertex set V (H) = ∪v∈V(G)Lv, where Lv = {v} × [s], and the edge set M = ∪uv∈E(G)Muv, where Muv is a matching between Lu and Lv. A vertex set T ⊆ V (H) is a transversal of H if ∣T ∩ Lv∣ = 1 for each v ∈ V(G). Let f be a nonnegative integer valued function on the vertex-set of H. If for any nonempty subgraph Γ of H[T], there exists a vertex x ∈ V (H) such that d(x) < f(x), then T is called a strictly f-degenerate transversal. In this paper, we give a sufficient condition for the existence of strictly f-degenerate transversal for planar graphs without chorded 6-cycles. As a consequence, every planar graph without subgraphs isomorphic to the configurations is DP-4-colorable. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a nontrivial connected simple graph and d (a , b) be the distance between the vertices a and b in G. The metric dimension of a graph G , denoted by dim(G), refers to the smallest set of vertices required to uniquely identify every vertex in the graph G. A family of simple connected graphs say F s , where s ∈ ℕ has a constant metric dimension, if dim ( F s ) is finite and does not depend on the choice of s in F s . In this paper, we consider two infinite families of planar graphs, say Q s , where s ≥ 8 and Z s , where s ≥ 6 , and investigate their metric basis as well as the metric dimension. Additionally, we prove that the metric basis for these two graphs are independent. [ABSTRACT FROM AUTHOR]

An equitable k -coloring of a graph G is a proper vertex coloring such that | | V i | − | V j | | ≤ 1 for any i , j ∈ { 1 , 2 , ... , k } , where V i (1 ≤ i ≤ k) is the set of vertices colored with i. If there is an equitable k -coloring of G , then the graph G is said to be equitably k -colorable. In this paper, we prove that every planar graph without 5-cycles and chordal 4-cycles has an equitable k -coloring for k ≥ max { Δ (G) , 6 } , where Δ (G) is the maximum degree of  G. [ABSTRACT FROM AUTHOR]

We consider a new coloring as follows such that a subset of V (G) needs very few colors. Let G be a graph with vertex set V (G) and a , b , i be three integers with a ≥ b ≥ i ≥ 0. S is a vertex subset of G , graph G is said to be i -weak (a : b) -choosable about set S , if the following can be satisfied: For any list assignment L = { L (v) : | L (v) | = a , v ∈ V (G) } , there is a way that each vertex v of S is assigned i colors of L (v) and each vertex u of V (G) \ S is assigned b colors of L (v) such that the color sets corresponding to adjacent vertices do not intersect. In this paper, we consider the i -weak (a : b) -choosable problem of 1 -planar graphs without short cycles and prove our results by the discharging method. In this paper, we prove that every 1 -planar graph without 3 -cycles, 5 -cycles and adjacent 4 -cycles is i -weak (4 b + i : b) -choosable about set S = { v : v ∈ V (G) , d (v) = 4 }. [ABSTRACT FROM AUTHOR]

In last two decades, the basic Roman domination problem and the variants thereof have attracted many researchers from different fields to study these problems in both ways, theoretically and computationally. Function f : V → { − 1 , 1 , 2 } is the signed Roman domination function (SRDF) if and only if it satisfies the following conditions: (i) for each vertex v ∈ V of graph G the sum of the values assigned to v and all its neighbors is at least 1 and (ii) each vertex v ∈ V for which f (v) = − 1 , must be adjacent to at least one vertex u such that f (u) = 2. The minimum weight ∑ v ∈ V f (v) of all SRDFs on graph G is defined as signed Roman domination number ( γ sR (G)). Definition of the signed total Roman domination function (STRDF) follows the definition of SRDF with a minor change where condition (i) considers the sum of all values assigned to all neighbors of v to be at least one, for each vertex v. The minimum weight ∑ v ∈ V f (v) of all STRDFs on graph G is called signed total Roman domination number ( γ stR (G)). In this paper, we deal with the calculation of the signed (total) Roman domination numbers on a few classes of planar graphs from the literature. We give proofs for the exact values of the numbers γ sR (A n) and γ sR (R n) as well as the numbers γ stR (S n) and γ stR (T n). For some other classes of planar graphs, such as Q n , and T n ″ , lower and upper bounds on γ sR are presented. [ABSTRACT FROM AUTHOR]

For a simple, undirected graph G (V , E) without isolated vertices, a function h : V → { ϕ , { 1 } , { 2 } , { 1 , 2 } } which satisfies the following two conditions is called a total 2-rainbow dominating function (T2RDF) of G. (i) For all u ∈ V , if h (u) = ϕ then ∪ v ∈ N (u) h (v) = { 1 , 2 } and (ii) Every u ∈ V with h (u) ≠ ϕ is adjacent to a vertex v with h (v) ≠ ϕ. The weight of a T2RDF h of G is the value h (V) = ∑ u ∈ V | h (u) |. The total 2-rainbow domination number is the minimum weight of a T2RDF on G and is denoted by γ t r 2 (G). The minimum total 2-rainbow domination problem (MT2RDP) is to find a T2RDF of minimum weight in the input graph. In this article, we show that the problem of deciding if G has a T2RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, split graphs and planar graphs is NP-complete. On the positive side, we show that MT2RDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, we show that MT2RDP cannot be approximated within (1 −) ln | V | for any > 0 unless P=NP and also propose 2 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for it. Further, we show that MT2RDP is APX-complete for graphs with maximum degree 4. Next, it is shown that domination problem and the total 2-rainbow domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MT2RDP is presented. [ABSTRACT FROM AUTHOR]

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph G avoiding a minor has a tree-decomposition whose torsos are finite or planar; moreover the tree-decomposition is canonical, i.e. invariant under the action of the automorphism group of G. As applications of this result, we prove the following. • Every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This extends a result of Thomassen (1992) [38] who proved it in the (quasi-)4-connected case and suggested that this assumption could be omitted. In particular, this shows that a Cayley graph excludes a finite minor if and only if it avoids the countable clique as a minor. • Locally finite quasi-transitive graphs avoiding a minor are accessible (in the sense of Thomassen and Woess), which extends known results on planar graphs to any proper minor-closed family. • Minor-excluded finitely generated groups are accessible (in the group-theoretic sense) and finitely presented, which extends classical results on planar groups. • The domino problem is decidable in a minor-excluded finitely generated group if and only if the group is virtually free, which proves the minor-excluded case of a conjecture of Ballier and Stein (2018) [7]. [ABSTRACT FROM AUTHOR]

A graph G is (2 , m) -linked if, for any distinct vertices a 1 , ... , a m , b 1 , b 2 in G , there exist disjoint connected subgraphs A , B of G such that a 1 , ... , a m ∈ V (A) and b 1 , b 2 ∈ V (B). A fundamental result in structural graph theory is the characterization of (2 , 2) -linked graphs. It appears to be difficult to characterize (2 , m) -linked graphs for m ≥ 3. In this paper, we provide a partial characterization of (2 , m) -linked graphs. This implies that every (2 m + 2) -connected graphs G is (2 , m) -linked and for any distinct vertices a 1 , ... , a m , b 1 , b 2 of G , there is a path P in G between b 1 and b 2 and avoiding { a 1 , ... , a m } such that G − P is connected, improving a previous connectivity bound of 10 m. [ABSTRACT FROM AUTHOR]

We study the fashion game, a classical network coordination/anti-coordination game employed to model social dynamics in decision-making processes, especially in fashion choices. In this game, individuals, represented as vertices in a graph, make decisions based on their neighbors’ choices. Some individuals are positively influenced by their neighbors while others are negatively affected. Analyzing the game’s outcome aids in understanding fashion trends and flux within the population. In an instance of the fashion game, an action profile is formed when all individuals have made their choices. The utility of an individual under an action profile is defined according to the choices he and his neighbors made. A pure Nash equilibria is an action profile under which each individual has a nonnegative utility. To further study the existence of pure Nash equilibria, we investigate an associated optimization problem aimed at maximizing the minimal individual utility, referred to as the utility of a fashion game instance. The fashion game with two different but symmetric actions (choices) has been studied extensively in the literature. This paper seeks to extend the fashion game analysis to scenarios with more than two available actions, thereby enhancing comprehension of social dynamics in decision-making processes. We determine the utilities of all instances on paths, cycles and complete graphs. For instances where each individual likes to anti-coordinate, graph is planar and three actions are available, we illustrate the time complexity of determining the utility of such instances. Additionally, for instances containing both coordinating and anti-coordinating individuals, we extend the results on the time complexity of determining the utility of instances with two available actions to cases with more than two actions. [ABSTRACT FROM AUTHOR]

Let [Formula: see text] be a graph without any isolated vertices. A semipaired dominating set [Formula: see text] of G, is a dominating set of G, if D can be partitioned into cardinality 2 subsets such that the vertices in each of these subsets are at distance at most two from each other. The Min-Semi-PD problem is to compute a minimum cardinality semipaired dominating set of a given graph G. It is known that the decision version of the problem is NP-complete for bipartite graphs and split graphs. In this article, we resolve the complexity of the problem in two well studied graph classes, namely, AT-free graphs and planar graphs. We show that the decision version of the Min-Semi-PD problem remains NP-complete for planar graphs. On the positive side, we propose a polynomial-time exact algorithm for the Min-Semi-PD problem in AT-free graphs, but the complexity of the algorithm is quite high. So, in addition, we also give a linear-time constant factor approximation algorithm for the problem in AT-free graphs.

We consider coloring problems inspired by the theory of anti-Ramsey /rainbow colorings that we generalize to a far extent. Let F be a hereditary family of graphs; i.e., if H ∈ F and H ′ ⊂ H then also H ′ ⊂ F. For a graph G and any integer n ≥ | G | , let f (n , G | F) denote the smallest number k of colors such that any edge coloring of K n with at least k colors forces a copy of G in which each color class induces a member of F. The case F = { K 2 } is the notorious anti-Ramsey rainbow coloring problem introduced by Erdős, Simonovits and Sós in 1973. Using the F -deck of G , D (G | F) = { H : H = G − D , D ∈ F } , we define χ F (G) = min { χ (H) : H ∈ D (G | F) }. The main theorem we prove is: Suppose F is a hereditary family of graphs, and let G be a graph not a member of F. (1) If χ F (G) ≥ 3 , then f (n , G | F) = (1 + o (1)) ex (n , K χ F (G) ). (2) Otherwise f (n , G | F) = o (n 2). Among the families covered by this theorem are: matchings, acyclic graphs, planar and outerplanar graphs, d -degenerate graphs, graphs with chromatic number at most k , graphs with bounded maximum degree, and many more. We supply many concrete examples to demonstrate the wide range of applications of the main theorem; the next result is a representative of these examples. For p ≥ 5 and F = { t K 2 : t ≥ 1 } , we have f (n , K p | F) = (1 + o (1)) ex (n , K ⌈ p / 2 ⌉ ) ; this is the smallest number of colors such that any edge coloring of K n with this many colors contains a properly colored copy of K p. In other words, a certain number of colors forces nearly twice as large properly edge-colored complete subgraphs as rainbow ones. [ABSTRACT FROM AUTHOR]

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 on its neighborhood. This notion was formally introduced by Fabrici et al., who proved that planar graphs have a proper conflict-free 8-coloring and constructed a planar graph with no proper conflict-free 5-coloring. Caro, Petruševski, and Škrekovski investigated this coloring concept further, and in particular studied upper bounds on the maximum average degree that guarantees a proper conflict-free c -coloring for c ∈ { 4 , 5 , 6 }. Along these lines, we completely determine the threshold on the maximum average degree of a graph G , denoted mad (G) , that guarantees a proper conflict-free c -coloring for all c and also provide tightness examples. Namely, for c ≥ 5 we prove that a graph G with mad (G) ≤ 4 c c + 2 has a proper conflict-free c -coloring, unless G contains a 1-subdivision of the complete graph on c + 1 vertices. When c = 4 , we show that a graph G with mad (G) < 12 5 has a proper conflict-free 4-coloring, unless G contains an induced 5-cycle. In addition, we show that a planar graph with girth at least 5 has a proper conflict-free 7-coloring. [ABSTRACT FROM AUTHOR]

We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to Ck ${C}_{k}$ for some k $k$) instead of cycles (graphs with all degrees even). We give an almost‐exponential lower bound for graphs with a surface embedding of representativity at least 4. We also prove an exponential lower bound for planar graphs. We conjecture that any bridgeless cubic graph has at least 2n/2−1 ${2}^{n/2-1}$ circuit double covers and we show an infinite class of graphs for which this bound is tight. [ABSTRACT FROM AUTHOR]

Given positive integers p≥k $p\ge k$, and a nonnegative integer d $d$, we say a graph G $G$ is (k,d,p) $(k,d,p)$‐choosable if for every list assignment L $L$ with ∣L(v)∣≥k $| L(v)| \ge k$ for each v∈V(G) $v\in V(G)$ and ∣⋃v∈V(G)L(v)∣≤p $| {\bigcup }_{v\in V(G)}L(v)| \le p$, there exists an L $L$‐coloring of G $G$ such that each monochromatic subgraph has maximum degree at most d $d$. In particular, (k,0,k) $(k,0,k)$‐choosable means k $k$‐colorable, (k,0,+∞) $(k,0,+\infty)$‐choosable means k $k$‐choosable and (k,d,+∞) $(k,d,+\infty)$‐choosable means d $d$‐defective k $k$‐choosable. This paper proves that there are 1‐defective 3‐choosable planar graphs that are not 4‐choosable, and for any positive integers ℓ≥k≥3 $\ell \ge k\ge 3$, and nonnegative integer d $d$, there are (k,d,ℓ) $(k,d,\ell)$‐choosable graphs that are not (k,d,ℓ+1) $(k,d,\ell +1)$‐choosable. These results answer questions asked by Wang and Xu, and Kang, respectively. Our construction of (k,d,ℓ) $(k,d,\ell)$‐choosable but not (k,d,ℓ+1) $(k,d,\ell +1)$‐choosable graphs generalizes the construction of Král' and Sgall for the case d=0 $d=0$. [ABSTRACT FROM AUTHOR]

In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an n $n$‐vertex planar graph. They precisely determined the maximum number of triangles and four‐cycles and presented a conjecture for the maximum number of pentagons. In this work, we confirm their conjecture. Even more, we characterize the n $n$‐vertex, planar graphs with the maximum number of pentagons. [ABSTRACT FROM AUTHOR]

In 2018, Dvořák and Postle introduced the concept of DP-coloring which is a generalization of list coloring and recently, Bernshteyn and Kostochka used this concept to give a new coloring, called edge DP-coloring. The edge DP-chromatic number of a graph G is denoted by χ DP ′ (G) . Note that χ DP ′ (G) ≥ Δ . It is interesting to find sufficient conditions of a graph G satisfying χ DP ′ (G) = Δ . In this paper, we give the sufficient conditions of a graph G in terms of its maximum degree and maximum average degree satisfying χ DP ′ (G) = Δ . Consequences are inferred for planar graphs in terms of their maximum degree and girth. Moreover, we also prove that a planar graph G with maximum degree Δ satisfying χ DP ′ (G) = Δ . [ABSTRACT FROM AUTHOR]

Given a digraph D = (V , A) on n vertices and a vertex v ∈ V , the cycle-degree of v is the minimum size of a set S ⊆ V (D) ∖ { v } intersecting every directed cycle of D containing v. From this definition of cycle-degree, we define the c -degeneracy (or cycle-degeneracy) of D , which we denote by δ c ∗ (D). It appears to be a nice generalisation of the undirected degeneracy. For instance, the dichromatic number χ → (D) of D is bounded above by δ c ∗ (D) + 1 , where χ → (D) is the minimum integer k such that D admits a k -dicolouring, i.e. , a partition of its vertices into k acyclic subdigraphs. In this work, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture (Cereceda, 2007) to digraphs. The k - dicolouring graph of D , denoted by D k (D) , is the undirected graph whose vertices are the k -dicolourings of D and in which two k -dicolourings are adjacent if they differ on the colour of exactly one vertex. This is a generalisation of the k -colouring graph of an undirected graph G , in which the vertices are the proper k -colourings of G. We show that D k (D) has diameter at most O δ c ∗ (D) (n δ c ∗ (D) + 1) (respectively O (n 2) and (δ c ∗ (D) + 1) n) when k is at least δ c ∗ (D) + 2 (respectively 3 2 (δ c ∗ (D) + 1) and 2 (δ c ∗ (D) + 1)). This improves known results on digraph redicolouring (Bousquet et al., 2023). Next, we extend a result due to Feghali (2021) to digraphs, showing that D d + 1 (D) has diameter at most O d , ϵ (n (log n) d − 1) when D has maximum average cycle-degree at most d − ϵ. We then show that two proofs of Bonamy and Bousquet (2018) for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph χ → g (D) , which is the worst number of colours used in a greedy dicolouring. If k ≥ χ → g (D) + 1 , we show that D k (D) has diameter at most 4 ⋅ χ → (D) ⋅ n. The second one uses the D - width of a digraph, denoted by D w (D) , which is a generalisation of the treewidth to digraphs. If k ≥ D w (D) + 2 , we show that D k (D) has diameter at most 2 (n 2 + n). Finally, we give a general theorem which makes a connection between the recolourability of a digraph D and the recolourability of its underlying graph UG (D). Assume that G is a class of undirected graphs, closed under edge-deletion and with bounded chromatic number, and let k ≥ χ (G) (i.e. , k ≥ χ (G) for every G ∈ G) be such that, for every n -vertex graph G ∈ G , the diameter of the k -colouring graph of G is bounded by f (n) for some function f. We show that, for every n -vertex digraph D such that UG (D) ∈ G , the diameter of D k (D) is bounded by 2 f (n). For instance, this result directly extends a number of results on planar graph recolouring to planar digraph redicolouring. [ABSTRACT FROM AUTHOR]

For nonnegative integers d 1 , d 2 , ... , d k , a graph G is (d 1 , d 2 , ... , d k) -colorable if its vertex set can be partitioned into k subsets V 1 , V 2 , ... , V k such that V i the induced subgraph G [ V i ] has maximum degree at most d i for i ∈ { 1 , 2 , ... , k }. Cho et al. proved in 2021 that planar graphs without 4- and 5-cycles are (3 , 4) -colorable. This inspires us to investigate whether planar graphs without 4- and 6-cycles have this property. We propose the conjecture that such graphs are (d 1 , d 2) -colorable if d 1 + d 2 ≥ 7. This work provided a partially affirmative answer to the conjecture by verifying the case (d 1 , d 2) = (3 , 4). [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]