The vertex arboricity $\mathrm{va}(G)$ of a multigraph $G$ is the minimum number $k$ for which $V(G)$ can be partitioned into $k$ subsets, each of which induces an acyclic subgraph of $G$. By definition, if $\mathrm{va}(G)= k$, then the chromatic number, $\chi(G)$, satisfies $k\leq \chi(G)\leq 2k$. Fundamental results by Borodin from 1976 and Bollob\'as and Manvel from 1979 imply an analog of Gallai's lower bound on the number of edges in a $(2k-1)$-critical graph. We consider a slight generalization of vertex arboricity in the setting of DP-coloring. Using this framework, we derive lower bounds on the number of edges in graphs critical for vertex arboricity and for list arboricity that are better than Gallai's bound, along with similar bounds in our DP-setting.
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.
A full-homomorphism from a graph $G$ to a graph $H$ is a function on vertex sets that preserves adjacency and non-adjacency of vertices. A graph $G$ is called a minimal $H$-obstruction if it has no full-homomorphism to $H$ but every proper vertex induced subgraph of $G$ does. Such graphs can have at most $|V(H)|+1$ vertices. The set of minimal $H$-obstructions on $|V(H)|+1$ vertices is denoted by $\mathrm{obs*}(H)$. In question 2 of the paper"Santiago Guzm{\'a}n-Pro, Full-homomorphisms to paths and cycles, Discrete Mathematics, 347(3):113800, 2024"it is asked if there is a characterization of those graphs $G$ that lie in $\mathrm{obs*}(H)$ for some graph $H$. In this paper, we give a complete answer to this question.
Zahra Rahimi, M. H. Shirdareh Haghighi, Asma Namazi Department of Mathematics et al.· 0 citations
A dominating set in a graph $G$ is a subset $S$ of its vertices such that each vertex in $G$ is either in $S$ or adjacent to a vertex in $S$. Nordhaus-Gaddum inequalities relate the values of a graph parameter on a graph and its complement. In this setting, Keough and Shane conjecture that any graph $G$ on $n$ vertices satisfies $\partial(G) + \partial(\bar{G}) \leq 2(2^{\lfloor n/2 \rfloor} - 1)(2^{\lceil n/2 \rceil} - 1) + 2$, where $\partial(G)$ is the number of dominating sets in $G$. We partially resolve this conjecture for the bipartite case by proving the stronger bound: for a bipartite graph $G$ with nonempty bipartition $(A,B)$, it holds that $\partial(G) + \partial(\bar{G}) \leq 2(2^{|A|} - 1)(2^{|B|} - 1) + 2$. We also characterize the bipartite graphs for which equality holds.
For finite simple graphs $G,H$ on a common vertex set $V$, we say that $H$ is $G$-colorable if $H$ admits a proper list coloring with list assignment $L(v)=N_G(v)$ for all $v\in V$. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call \emph{graphic list coloring}, has connections to several classical topics, including systems of distinct representatives and graph factorizations. In this paper, we investigate when a necessary Hall-type condition, introduced by Hilton and Johnson in 1990, is also sufficient for $H$ to be $G$-colorable. We characterize all graphs $H$ that are $G$-colorable whenever the pair $(H,G)$ satisfies Hall's condition, answering a question raised by Johnson. We then consider the dual problem of characterizing graphs $G$ such that, whenever $(H,G)$ satisfies Hall's condition, $H$ is $G$-colorable. In this vein, we obtain complete results for several families of graphs, such as forests, complete multipartite graphs, and grid graphs.
The bounds on the number of Eulerian orientations for certain classes of connected, loopless $4-regular graphs are improved and a divide-and-conquer algorithm is provided that leverages structural properties to compute the exact number of Eulerian orientations for separable graphs without exhaustive enumeration.
A vertex cover of a graph $G$ is a subset of vertices $C \subseteq V(G)$ such that every edge of $G$ is incident to at least one vertex in $C$. The vertex cover number of $G$ is the minimum cardinality of a vertex cover of $G$ and is denoted by $\tau(G)$. A snark is a connected, bridgeless, cubic graph that has an edge chromatic number of four, meaning its edges cannot be properly colored with only three colors. In this work, we investigate the problem of determining the value of a minimum vertex cover for classes of snark graphs. Given a positive integer $k$, we firstly prove that determining whether an arbitrary snark has a vertex cover $C$ with size $|C| \leq k$ is an NP-complete problem. Secondly, we determine the vertex cover number $\tau(G)$ for several subclasses of snark graphs, such as Flower snarks, Goldberg snarks, Generalized Blanu\v{s}a snarks and Loupekine snarks.
G. Fernandes, A. Luiz· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
