BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Petru Valicov contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques to study the 2-distance coloring of planar subcubic graphs. Applying these techniques we show that every subcubic planar graph $G$ of girth at least 8 has 2-distance chromatic number at most 6.
We study the minimum size $f$ of a feedback vertex set in directed and undirected $n$-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\frac{k-1}{k+1}n$ is known to be tight for graphs with bounded treewidth $k$ or bounded odd degeneracy $k$. We show that neither of the easy upper and lower bounds $\frac{k-1}{k+1}n$ and $\frac{k}{k+2}n$ can be exact for the case of even degeneracy. More precisely, for even degeneracy $k$ we prove that $f < \frac{k}{k+2}n$ and for every $ε>0$, there exists a $k$-degenerate graph for which $f\geq \frac{3k-2}{3k+4}n -ε$. For directed graphs of bounded degeneracy $k$, we prove that $f\leq\frac{k-1}{k+1}n$ and that this inequality is strict when $k$ is odd. For directed graphs of bounded treewidth $k\geq 2$, we show that $f \leq \frac{k}{k+3}n$ and for every $ε>0$, there exists a $k$-degenerate graph for which $f\geq \frac{k-2\lfloor\log_2(k)\rfloor}{k+1}n -ε$. Further, we provide several constructions of low degeneracy or treewidth and large $f$.
We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 receive distinct colors. The smallest number of colors used in such a coloring of G is its exact square chromatic number, denoted $χ^{\sharp 2}(G)$. This notion is related to other types of distance-based colorings, as well as to injective coloring. Indeed, for triangle-free graphs, exact square coloring and injective coloring coincide. We prove tight bounds on special subclasses of planar graphs: subcubic bipartite planar graphs and subcubic K 4-minor-free graphs have exact square chromatic number at most 4. We then turn our attention to the class of fullerene graphs, which are cubic planar graphs with face sizes 5 and 6. We characterize fullerene graphs with exact square chromatic number 3. Furthermore, supporting a conjecture of Chen, Hahn, Raspaud and Wang (that all subcubic planar graphs are injectively 5-colorable) we prove that any induced subgraph of a fullerene graph has exact square chromatic number at most 5. This is done by first proving that a minimum counterexample has to be on at most 80 vertices and then computationally verifying the claim for all such graphs.
We study the problem of enumerating the $k$-arc-connected orientations of a graph $G$, i.e., generating each exactly once. A first algorithm using submodular flow optimization is easy to state, but intricate to implement. In a second approach we present a simple algorithm with $O(knm^2)$ time delay and amortized time $O(m^2)$, which improves over the analysis of the submodular flow algorithm. As ingredients, we obtain enumeration algorithms for the $α$-orientations of a graph $G$ in $O(m^2)$ time delay and for the outdegree sequences attained by $k$-arc-connected orientations of $G$ in $O(knm^2)$ time delay.