11 problems

Let $B$ be the bow-tie cactus with $\mathrm{lir}(B)=4$. For a connected graph $G$ that is locally irregular colorable, let $\mathrm{lir}(G)$ denote the minimum number of colors in…

Let $G$ be a triangular cactus graph, meaning a cactus graph whose blocks are all $3$-cycles, and let its diameter be the maximum distance between two vertices of $G$. The $(S_2)$-…

Let $G$ be a connected graph, let $\mathfrak{T'}$ be the family consisting of the recursively defined family $\mathfrak{T}$ together with all odd-length paths and odd-length cycles…

A graph is locally irregular if the degrees of the end-vertices of every edge are distinct. An edge coloring is locally irregular if every color induces a locally irregular subgrap…

A graph is locally irregular if the degrees of the end-vertices of every edge are distinct. An edge coloring is locally irregular if every color induces a locally irregular subgrap…

Four-color bound. Every colorable connected graph $G$ satisfies

Let $G$ be a cactus with $k$ cycles and $b$ bridges; write $n$ for its number of vertices, $R$ for its Randić index, and $d$ for its diameter. A BC-tree is the block-cut tree of…

Let $G_t$ be the cactus graph with $k$ edges and $t$ cycles, with $G_0=K_{1,k}$. Let $\Gamma$ be a signed complete graph of order $n>5$ whose negative edges induce a cactus graph w…

Cyclomatic-number bound. For every such graph,

Let $A(n,m)$ denote the random graph with $n$ vertices and $m$ edges, and write $m=n+t$ with $t=o(n)$. Non-cactus conjecture. With high probability, $A(n,m)$ is not a cactus graph.…

Let $A(n,m)$ denote the random graph with $n$ vertices and $m$ edges. For $1/2<\alpha<1$, set $m=\alpha n$. Cactus-graph probability conjecture. The probability that $A(n,m)$ is a…