Source author record

Andre Raspaud

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Injective edge-coloring of sparse graphs

An injective edge-coloring $c$ of a graph $G$ is an edge-coloring such that if $e_1$ , $e_2$ , and $e_3$ are three consecutive edges in $G$ (they are consecutive if they form a path or a cycle of length three), then $e_1$ and $e_3$ receive different colors. The minimum integer $k$ such that, $G$ has an injective edge-coloring with $k$ colors, is called the injective chromatic index of $G$ ( $χ'_{\textrm{inj}}(G)$ ). This parameter was introduced by Cardoso et \textit{al.} \cite{CCCD} motivated by the Packet Radio Network problem. They proved that computing $χ'_{\textrm{inj}}(G)$ of a graph $G$ is NP-hard. We give new upper bounds for this parameter and we present the relationships of the injective edge-coloring with other colorings of graphs. The obtained general bound gives 8 for the injective chromatic index of a subcubic graph. If the graph is subcubic bipartite we improve this last bound. We prove that a subcubic bipartite graph has an injective chromatic index bounded by $6$ . We also prove that if $G$ is a subcubic graph with maximum average degree less than $\frac{7}{3}$ (resp. $\frac{8}{3}$ , $3$ ), then $G$ admits an injective edge-coloring with at most 4 (resp. $6$ , $7$ ) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs.

preprint2013arXiv

$(3,1)^*$ -choosability of planar graphs without adjacent short cycles

A list assignment of a graph $G$ is a function $L$ that assigns a list $L(v)$ of colors to each vertex $v\in V(G)$ . An $(L,d)^*$ -coloring is a mapping $π$ that assigns a color $π(v)\in L(v)$ to each vertex $v\in V(G)$ so that at most $d$ neighbors of $v$ receive color $π(v)$ . A graph $G$ is said to be $(k,d)^*$ -choosable if it admits an $(L,d)^*$ -coloring for every list assignment $L$ with $|L(v)|\ge k$ for all $v\in V(G)$ . In 2001, Lih et al. \cite{LSWZ-01} proved that planar graphs without 4- and $l$ -cycles are $(3,1)^*$ -choosable, where $l\in \{5,6,7\}$ . Later, Dong and Xu \cite{DX-09} proved that planar graphs without 4- and l-cycles are $(3,1)^*$ -choosable, where $l\in \{8,9\}$ . There exist planar graphs containing 4-cycles that are not $(3,1)^*$ -choosable (Crown, Crown and Woodall, 1986 \cite{CCW-86}). This partly explains the fact that in all above known sufficient conditions for the $(3,1)^*$ -choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles. More precisely, we prove that every planar graph without 4-cycles adjacent to 3- and 4-cycles is $(3,1)^*$ -choosable. This is a common strengthening of all above mentioned results. Moreover as a consequence we give a partial answer to a question of Xu and Zhang \cite{XZ-07} and show that every planar graph without 4-cycles is $(3,1)^*$ -choosable.

preprint2010arXiv

Covering a graph by forests and a matching

We prove that for any positive integer $k$ , the edges of any graph whose fractional arboricity is at most $k + 1/(3k+2)$ can be decomposed into $k$ forests and a matching.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Andre Raspaud

Research overview

Is this your work?

3 publications

Injective edge-coloring of sparse graphs

$(3,1)^*$ -choosability of planar graphs without adjacent short cycles

Covering a graph by forests and a matching

See the researcher in context

Building this map preview

Andre Raspaud

Research overview

Is this your work?

3 publications

Injective edge-coloring of sparse graphs

(3,1)∗(3,1)^*(3,1)∗-choosability of planar graphs without adjacent short cycles

Covering a graph by forests and a matching

See the researcher in context

Building this map preview

$(3,1)^*$ -choosability of planar graphs without adjacent short cycles