BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
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 k+1k−1n 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 k+1k−1n and k+2kn can be exact for the case of even degeneracy. More precisely, for even degeneracy k we prove that f<k+2kn and for every ε>0, there exists a k-degenerate graph for which f≥3k+43k−2n−ε. For directed graphs of bounded degeneracy k, we prove that f≤k+1k−1n and that this inequality is strict when k is odd. For directed graphs of bounded treewidth k≥2, we show that f≤k+3kn and for every ε>0, there exists a k-degenerate graph for which f≥k+1k−2⌊log2(k)⌋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 χ♯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(knm2) time delay and amortized time O(m2), 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(m2) time delay and for the outdegree sequences attained by k-arc-connected orientations of G in O(knm2) time delay.
Given a directed graph, an acyclic set is a set of vertices inducing a subgraph with no directed cycle. In this note we show that there exist oriented planar graphs of order n for which the size of the maximum acyclic set is at most ⌈2n+1⌉, for any n. This disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.
It was proved by Raychaudhuri in 1987 that if a graph power Gk−1 is an interval graph, then so is the next power Gk. This result was extended to m-trapezoid graphs by Flotow in 1995. We extend the statement for interval graphs by showing that any interval representation of Gk−1 can be extended to an interval representation of Gk that induces the same left endpoint and right endpoint orders. The same holds for unit interval graphs. We also show that a similar fact does not hold for trapezoid graphs.
A strong edge-coloring of a graph G is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of maximum degree at most 3 and the other part is of maximum degree Δ. For every such graph, we prove that a strong 4Δ-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gyárfás, Schelp and Tuza for this class of graphs.
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree Δ has a strong edge-colouring with at most 4Δ+4 colours. We show that 3Δ+1 colours suffice if the graph has girth 6, and 4Δ colours suffice if Δ≥7 or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.
An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If $\ID(G)$ denotes the size of a minimum identifying code of an identifiable graph G, we show that the usual bound $\ID(G)\ge \lceil\log_2(n+1)\rceil$, where n denotes the order of G, can be improved to Θ(n) in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound $\ID(\mathcal{L}(G))\leq 2|V(G)|-5$, where L(G) is the line graph of G, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree~3 and arbitrarily large girth.
An identifying code of a graph G is a dominating set C such that every vertex x of G is distinguished from all other vertices by the set of vertices in C that are at distance at most 1 from x. The problem of finding an identifying code of minimum possible size turned out to be a challenging problem. It was proved by N. Bertrand that if a graph on n vertices with at least one edge admits an identifying code, then a minimum identifying code has size at most n-1. Some classes of graphs whose smallest identifying code is of size n-1 were already known, and few conjectures were formulated to classify all these graphs. In this paper, disproving these conjectures, we classify all finite graphs for which all but one of the vertices are needed to form an identifying code. We also classify all infinite graphs needing the whole set of vertices in any identifying code. New upper bounds in terms of the number of vertices and the maximum degree of a graph are also provided.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.