André Raspaud
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
André Raspaud has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Mickaël Montassier
LaBRI UMR CNRS 5800, Université Bordeaux I, 33405 Talence Cedex, France
8 shared publications - Edita Máčajová
Comenius University, Slovakia
3 shared publications - Weifan Wang
Zhejiang Normal University, China
3 shared publications - Xuding Zhu
School of Mathematical Sciences, Zhejiang Normal University, Jinhua, China
3 shared publications - Alexandr Kostochka
University of Illinois at Urbana–Champaign, Urbana, USA
2 shared publications - Bjarne Toft
University of Southern Denmark Odense Denmark
2 shared publications
Latest Publications
- 30 October 2020
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (1) , 199-207
Cut-Edges and Regular Factors in Regular Graphs of Odd Degree
- 30 October 2020
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (1) , 199-207
Cut-Edges and Regular Factors in Regular Graphs of Odd Degree
- Open Access
A note on adaptable choosability and choosability with separation of planar graphs
Let $F$ be a (possibly improper) edge-coloring of a graph $G$; a vertex coloring of $G$ is \emph{adapted to} $F$ if no color appears at the same time on an edge and on its two endpoints. If for some integer $k$, a graph $G$ is such that given any list assignment $L$ to the vertices of $G$, with $|L(v)| \ge k$ for all $v$, and any edge-coloring $F$ of $G$, $G$ admits a coloring $c$ adapted to $F$ where $c(v) \in L(v)$ for all $v$, then $G$ is said to be \emph{adaptably $k$-choosable}. A {\em $(k,d)$-list assignment} for a graph $G$ is a map that assigns to each vertex $v$ a list $L(v)$ of at least $k$ colors such that $|L(x) \cap L(y)| \leq d$ whenever $x$ and $y$ are adjacent. A graph is {\em $(k,d)$-choosable} if for every $(k,d)$-list assignment $L$ there is an $L$-coloring of $G$. It has been conjectured that planar graphs are $(3,1)$-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably $3$-choosable. Since $(k,1)$-choosability is a special case of adaptable $k$-choosablity, this implies that a planar graph satisfying these conditions is $(3,1)$-choosable.Open AccessA note on adaptable choosability and choosability with separation of planar graphs
Let $F$ be a (possibly improper) edge-coloring of a graph $G$; a vertex coloring of $G$ is \emph{adapted to} $F$ if no color appears at the same time on an edge and on its two endpoints. If for some integer $k$, a graph $G$ is such that given any list assignment $L$ to the vertices of $G$, with $|L(v)| \ge k$ for all $v$, and any edge-coloring $F$ of $G$, $G$ admits a coloring $c$ adapted to $F$ where $c(v) \in L(v)$ for all $v$, then $G$ is said to be \emph{adaptably $k$-choosable}. A {\em $(k,d)$-list assignment} for a graph $G$ is a map that assigns to each vertex $v$ a list $L(v)$ of at least $k$ colors such that $|L(x) \cap L(y)| \leq d$ whenever $x$ and $y$ are adjacent. A graph is {\em $(k,d)$-choosable} if for every $(k,d)$-list assignment $L$ there is an $L$-coloring of $G$. It has been conjectured that planar graphs are $(3,1)$-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably $3$-choosable. Since $(k,1)$-choosability is a special case of adaptable $k$-choosablity, this implies that a planar graph satisfying these conditions is $(3,1)$-choosable. - Open Access
Cut-edges and regular factors in regular graphs of odd degree
We study $2k$-factors in $(2r+1)$-regular graphs. Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize their result by proving for $k\le(2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. Both the restriction on $k$ and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor, as studied by Bollob\'as, Saito, and Wormald.Open AccessCut-edges and regular factors in regular graphs of odd degree
We study $2k$-factors in $(2r+1)$-regular graphs. Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize their result by proving for $k\le(2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. Both the restriction on $k$ and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor, as studied by Bollob\'as, Saito, and Wormald. - Open Access
The chromatic number of a signed graph
In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $\phi\colon V(G)\to \mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $\phi(u)$ is different from the colour $\sigma(uv)\phi(v)$, where is $\sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs.Open AccessThe chromatic number of a signed graph
In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $\phi\colon V(G)\to \mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $\phi(u)$ is different from the colour $\sigma(uv)\phi(v)$, where is $\sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs. - 11 March 2015
- Published by Wiley in Journal of Graph Theory
- Vol. 81 (2) , 120-133
Circuit Covers of Signed Graphs
- 11 March 2015
- Published by Wiley in Journal of Graph Theory
- Vol. 81 (2) , 120-133
Circuit Covers of Signed Graphs
- 6 February 2013
- Published by Wiley in Journal of Graph Theory
- Vol. 75 (2) , 191-202
Limits of Near‐Coloring of Sparse Graphs
Let be nonnegative integers. A graph G is ‐colorable if its vertex set can be partitioned into sets such that the graph induced by has maximum degree at most d for , while the graph induced by is an edgeless graph for . In this article, we give two real‐valued functions and such that any graph with maximum average degree at most is ‐colorable, and there exist non‐‐colorable graphs with average degree at most . Both these functions converge (from below) to when d tends to infinity. This implies that allowing a color to be d‐improper (i.e., of type ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type (even with a very large degree d) is somehow less powerful than using two colors of type (two stable sets).
- 6 February 2013
- Published by Wiley in Journal of Graph Theory
- Vol. 75 (2) , 191-202
Limits of Near‐Coloring of Sparse Graphs
Let be nonnegative integers. A graph G is ‐colorable if its vertex set can be partitioned into sets such that the graph induced by has maximum degree at most d for , while the graph induced by is an edgeless graph for . In this article, we give two real‐valued functions and such that any graph with maximum average degree at most is ‐colorable, and there exist non‐‐colorable graphs with average degree at most . Both these functions converge (from below) to when d tends to infinity. This implies that allowing a color to be d‐improper (i.e., of type ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type (even with a very large degree d) is somehow less powerful than using two colors of type (two stable sets).
- 9 February 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 68 (4) , 340-348
Short cycle covers of graphs and nowhere-zero flows
- 9 February 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 68 (4) , 340-348
Short cycle covers of graphs and nowhere-zero flows
- 1 February 2011
- Published by Elsevier in Discrete Mathematics
- Vol. 311 (4) , 232-238
Upper bounds on the linear chromatic number of a graph
- 1 February 2011
- Published by Elsevier in Discrete Mathematics
- Vol. 311 (4) , 232-238
Upper bounds on the linear chromatic number of a graph
- 30 September 2010
- Published by Elsevier in Information Processing Letters
- Vol. 110 (20) , 913-916
Decomposition of sparse graphs into two forests, one having bounded maximum degree
- 30 September 2010
- Published by Elsevier in Information Processing Letters
- Vol. 110 (20) , 913-916
Decomposition of sparse graphs into two forests, one having bounded maximum degree
- 4 August 2010
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 23 (1) , 79-93
On backbone coloring of graphs
- 4 August 2010
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 23 (1) , 79-93
On backbone coloring of graphs