Search

In Evans and Francis (2022) and Hendel (2021) the authors investigated resistance distance in triangular grid graphs and observed several types of asymptotic behavior. This paper extends their work by studying the initial, non-asymptotic, behavior found when equivalent circuit transformations are performed, reducing the rows in the triangular grid graph one row at a time. The main conjecture characterizes, after reducing an arbitrary number of times an initial triangular grid all of whose edge resistances are identically one, when edge resistance values are less than, equal to, or greater than one. A special case of the conjecture is proven. The main theorem identifies patterns of repeating edge resistances arising in diagonals of a triangular grid reduced s times provided the original grid has at least 4 s rows of triangles. This paper also improves upon the notation, concepts, and proof techniques introduced by the authors previously. [ABSTRACT FROM AUTHOR]

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

The biclique B of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph K B (G) of a graph G is the graph with the bicliques of G as its vertices where two vertices of K B (G) are adjacent if and only if they have a common vertex in G. In this paper, we disprove a conjecture of Groshaus and Montero concerning Helly property of biclique graphs (Groshaus and Montero, 2021) and two conjectures of Montero concerning vertex removal in biclique graphs (Montero, 2022). In addition, we confirm a conjecture of Montero about the structural characterization of biclique graphs in the same paper. [ABSTRACT FROM AUTHOR]

El Sahili conjectured that every oriented n -path, where n ≥ 8 , is contained in every n -chromatic digraph. This conjecture was confirmed by Gallai–Hasse–Roy–Vitaver's theorem for directed paths and by Addario-Berry et al. for oriented paths with two blocks. A block of an oriented path is a maximal directed subpath. El Joubbeh showed that every (4 n − 4) -chromatic digraph contains every oriented n -path with three blocks. For oriented paths with more than three blocks, Addario-Berry et al. established that every oriented n -tree, and hence every oriented n -path with any number of blocks, is contained in every ( n 2 2 − n 2 + 1) -chromatic digraph. This paper proposes an improvement to the bound on the chromatic number for digraphs that must include all paths consisting of four blocks. In fact, we extend El Joubbeh's bound on the chromatic number from (4 n − 4) for digraphs that should contain every n -path with three blocks to (4 n − 2) for digraphs that should be contain every n -path with four blocks. This bound surpasses the one provided by Addario-Berry et al. Furthermore, we show that every oriented n -path with t blocks, t ≥ 4 , is contained in every (4 r (t) n + q (t)) -chromatic digraph where r (t) = log 2 (t − 1) and q (t) = − 20 7 8 r (t) − 1 + 6 7 . Finally, the paper highlights an improvement in the bound of Addario-Berry et al. for n -paths with t blocks, where t ≤ n − 1 2 + 1. [ABSTRACT FROM AUTHOR]

The Borodin–Kostochka conjecture says that for a graph G , if Δ (G) ≥ 9 , then χ (G) ≤ max { Δ (G) − 1 , ω (G) }. Cranston and Rabern in [SIAM J. Discrete. Math. 27 (2013) 534–549] proved the conjecture holding for K 1 , 3 -free graphs. In this paper, we prove that the conjecture holds for K 1 , 3 ¯ -free graphs, where K 1 , 3 ¯ denotes the complement of K 1 , 3. [ABSTRACT FROM AUTHOR]

A bipartite graph G = (A , B , E) is said to be a biconvex bipartite graph if there exist orderings < A in A and < B in B such that the neighbors of every vertex in A are consecutive with respect to < B and the neighbors of every vertex in B are consecutive with respect to < A. A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this paper, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph. Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs. [ABSTRACT FROM AUTHOR]

One of the most interesting open problems of a digraph is Seymour's Second Neighborhood Conjecture (SSNC), which asserts that every digraph D has a vertex v satisfying d + + (v) ≥ d + (v) , we called such vertex v a Seymour vertex. Sullivan stated two compromise conjectures on SSNC. Let v ∈ V (D) if d + + (v) ≥ d − (v) , then v is called a Sullivan-1 vertex. If d + + (v) + d + (v) ≥ 2 d − (v) , then v is called a Sullivan-2 vertex. In this paper, we give a condition that the digraph has n Seymour vertices. And we also prove that every random tournament T n has n Sullivan-1 vertices and at least n 2 − n log n Sullivan-2 vertices with high probability. [ABSTRACT FROM AUTHOR]

The domination game is played on a graph G by two players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph G is contained in the closed neighbourhood of the set of selected vertices. Dominator's aim is to reach this state in as few moves as possible, whereas Staller wants the game to last as long as possible. In this paper, we prove that if G has n vertices and minimum degree at least 2, then Dominator has a strategy to finish the domination game on G within 10 n / 17 + 1 / 17 moves, thus making progress towards a conjecture by Bujtás, Iršič and Klavžar. [ABSTRACT FROM AUTHOR]

For a vertex v of a graph, the local complementation at v is an operation that replaces the neighborhood of v by its complement graph. Two graphs are locally equivalent if one is obtained from the other by a sequence of local complementations. A graph H is a vertex-minor of a graph G if H is an induced subgraph of a graph locally equivalent to G. Although this concept was introduced in the 1980s, it was not widely known and except for the survey paper of Bouchet published in 1990, there is no comprehensive survey listing all the new developments. We survey classic and recent theorems and conjectures on vertex-minors and related concepts such as circle graphs, cut-rank functions, rank-width, and interlace polynomials. [ABSTRACT FROM AUTHOR]

In an edge-colored graph G , let d m o n (v) denote the maximum number of edges with the same color incident with a vertex v in G , called the monochromatic-degree of v. The maximum value of d m o n (v) over all vertices v ∈ V (G) is called the maximum monochromatic-degree of G , denoted by Δ m o n (G). Li et al. in 2019 conjectured that every edge-colored complete graph G of order n with Δ m o n (G) ≤ n − 3 k + 1 contains k vertex-disjoint properly colored (PC for short) cycles of length at most 4, and they showed that the conjecture holds for k = 2. Han et al. showed that every edge-colored complete graph G of order n with Δ m o n (G) ≤ n − 2 k contains k PC cycles of different lengths. They further got the condition Δ m o n (G) ≤ n − 6 for the existence of two vertex-disjoint PC cycles of different lengths. In this paper, we consider the problems of the existence of edge-disjoint PC cycles of length at most 4 (different lengths) in an edge-colored complete graph G of order n. [ABSTRACT FROM AUTHOR]

In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Massé et al. found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words' tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area. [ABSTRACT FROM AUTHOR]

Alishahi and Hajiabolhassan found that for some classes of graphs, the wonderful equality χ G , r K 2 = | E (G) | − ex G , r K 2 holds as an amazing relationship between chromatic number and generalized Turán number. This powerful equality enabled them to determine chromatic numbers of some interesting and important classes of graphs. They conjectured that the aforementioned equality holds for all connected graphs G. Iradmusa, by a nice elegant use of a class of cubic graphs, called snarks, made counterexamples to this conjecture for which χ G , r K 2 = 1 and | E (G) | − ex G , r K 2 = 3. In this paper, for any arbitrary positive integer Θ , we explicitly construct a sequence of trees T r r = 1 ∞ for which lim r → ∞ (| E T r | − ex T r , r K 2 ) = + ∞ while χ T r , r K 2 = Θ for all r ≥ 3. [ABSTRACT FROM AUTHOR]

Wang and Yu (2022) prove an enhanced version of the Erdős–Lovász Tihany conjecture for line graphs of multigraphs. That is, let s , t and ℓ be arbitrary integers with t ≥ s ≥ 3. 5 ℓ + 2 , ℓ ≥ 0. If the line graph L (G) of some multigraph G has chromatic number s + t − 1 > ω (L (G)) , then there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + ℓ. In this paper, for integers s and t with t ≥ s ≥ 7 , we prove that for each line graph L (G) with χ (L (G)) = s + t − 1 ≥ ω (L (G)) , there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + 2 , which slightly improves the recent result of Wang and Yu (2022) for ℓ = 2. [ABSTRACT FROM AUTHOR]

A graph G is minimally t -tough if the toughness of G is t and deletion of any edge from G decreases its toughness. Kriesell conjectured that the minimum degree of a minimally 1-tough graph is 2, and Katona et al. proposed a generalized version of the conjecture that the minimum degree of a minimally t -tough graph is ⌈ 2 t ⌉. In this paper, we characterize the minimally 1 / a -tough, 2 K 2 -free graphs for an integer a. [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]

A strong edge-coloring of a graph G is a proper edge-coloring such that any two edges with distance at most 2 receive different colors. The strong chromatic index of G , denoted by χ s ′ (G) , is the least possible number of colors in a strong edge-coloring of G. Erdős and Nešetřil conjectured that every graph G with maximum degree Δ (G) has χ s ′ (G) ≤ 5 4 Δ (G) 2 − 1 2 Δ (G) + 1 4 if Δ (G) is odd and χ s ′ (G) ≤ 5 4 Δ (G) 2 if Δ (G) is even. In this paper, we prove that if G is a graph with Δ (G) ≤ 5 and maximum average degree less than 22 5 , then χ s ′ (G) ≤ 29. Our result implies that Erdős' conjecture holds for the case Δ (G) = 5 , if G has no subgraph with average degree at least 22 5. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , the exponential second Zagreb index is defined as e M 2 (G) = ∑ u v ∈ E e d (u) d (v) , where d (v) is the degree of vertex v ∈ V. Recently, Eliasi (2022) posed a conjecture about (n , m) -graphs with maximum e M 2 when n ≤ m ≤ 2 n − 3. In this paper, we show that this conjecture is true. Furthermore, we determine the graphs with maximum e M 2 among all (n , m) -graphs when 2 n − 3 < m. [ABSTRACT FROM AUTHOR]

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly the graphs that contain an isolated vertex. Furthermore, it is known that all other graphs have fractional domatic number at least 2. In this note we characterize graphs with fractional domatic number 2. More specifically, we show that a graph without isolated vertices has fractional domatic number 2 if and only if it has a vertex of degree 1 or a connected component isomorphic to a 4-cycle. We conjecture that if the fractional domatic number is more than 2, then it is at least 7/3. [ABSTRACT FROM AUTHOR]

A graph in which the two end-vertices of every edge have distinct degrees is called locally irregular. An edge coloring of a graph G such that every color induces a locally irregular subgraph of G is said to be locally irregular. A graph G which admits a locally irregular edge coloring is called colorable. The Local Irregularity Conjecture claims that 3 colors are enough for locally irregular edge coloring of any colorable graph. Not so long ago the only known graphs which do not admit a locally irregular 3-edge coloring were the non-colorable graphs, all of which are cacti. This fact motivated us to study locally irregular 3-edge colorings of cacti, which first resulted with the finding of the bow-tie graph B , a colorable cactus graph which requires 4 colors for a locally irregular edge coloring. As the graph B disproves the stated form of the Local Irregularity Conjecture, here we continue the study of locally irregular 3-edge colorings of cacti in relation to the conjecture. In this paper we confirm that all other cacti are locally irregular 3-edge colorable. This result makes us to believe that B is the only counterexample to the conjecture not only in the class of cacti, but also in general. [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]

Brooks' theorem states that for a graph G , if Δ (G) ≥ 3 and ω (G) ≤ Δ (G) , then χ (G) ≤ Δ (G). In this paper, we show that this chromatic bound can be further strengthened on (P 6 , C 4 , H) -free graphs, where H ∈ { b u l l , d i a m o n d }. In particular, we prove that for a (P 6 , C 4 , b u l l) -free graph G , if Δ (G) ≥ 9 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also prove that for a (P 6 , C 4 , d i a m o n d) -free graph G , if Δ (G) ≥ 5 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also show that similar results hold for (P 10 , p a w) -free graphs and (P 5 , C 5) -free graphs. These results validate the Borodin–Kostochka conjecture on these graph classes. [ABSTRACT FROM AUTHOR]

The resistance of a cubic graph is the smallest number of edges whose removal produces a 3-edge-colourable graph. The flow resistance is the minimum number of zeros in an integer 4-flow on the graph. Fiol et al. (2018) made a conjecture that the flow resistance of a bridgeless cubic graph never exceeds its resistance. The conjecture has recently been proved to be false by displaying a family of nontrivial snarks with resistance n and flow resistance 2 n (Allie et al., 2022). In this paper, we strengthen the result by showing that the ratio of the flow resistance to the resistance of a snark can be arbitrarily large. [ABSTRACT FROM AUTHOR]