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
A graph G is said to be ISK4-free if it does not contain any subdivision of K4 as an induced subgraph. In this paper, we propose new upper bounds for chromatic number of ISK4-free graphs and {ISK4, triangle}-free graphs.
Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of k vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every k≥1, every graph with minimum degree at least 2k2+5k−2 has k vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the k cycles are requested to have different lengths congruent to some values modulo some r. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have k vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.
The dichromatic number χ(D) of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this paper, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's Conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as Ω(log2n). We finally give a Brooks-type upper bound on the list dichromatic number of digon-free digraphs.
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.