Cover Image

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Beaudou, Laurent, Brosse, Caroline, Defrain, Oscar, Foucaud, Florent, Lagoutte, Aurélie, Limouzy, Vincent, Pastor, Lucas
Format:	Preprint
Published:	2021
Subjects:	Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Local certification of geometric graph classes
by: Defrain, Oscar, et al.
Published: (2023)

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
by: Beaudou, Laurent, et al.
Published: (2025)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
by: Brosse, Caroline, et al.
Published: (2024)

A quasi-optimal upper bound for induced paths in sparse graphs
by: Couëtoux, Basile, et al.
Published: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
by: Foucaud, Florent, et al.
Published: (2025)

Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
by: Chakraborty, Dibyayan, et al.
Published: (2025)

The Canadian Traveller Problem on outerplanar graphs
by: Beaudou, Laurent, et al.
Published: (2024)

Splitting vertices of bipartite graphs preserves de Bruijn-Erdős property
by: Beaudou, Laurent, et al.
Published: (2025)

Contact graphs of boxes with unidirectional contacts
by: Gonçalves, Daniel, et al.
Published: (2023)

Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
by: Das, Sandip, et al.
Published: (2023)

Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
by: Dailly, Antoine, et al.
Published: (2018)

Locating-dominating partitions for some classes of graphs
by: Foucaud, Florent, et al.
Published: (2025)

Distance-based (and path-based) covering problems for graphs of given cyclomatic number
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Monitoring arc-geodetic sets of oriented graphs
by: Das, Tapas, et al.
Published: (2024)

On three domination-based identification problems in block graphs
by: Chakraborty, Dipayan, et al.
Published: (2018)

On locating and neighbor-locating colorings of sparse graphs
by: Chakraborty, Dipayan, et al.
Published: (2023)

Extremal digraphs for open neighbourhood location-domination and identifying codes
by: Foucaud, Florent, et al.
Published: (2023)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

Enumerating minimal solution sets for metric graph problems
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Determining a graph from its reconfiguration graph
by: Berthe, Gaétan, et al.
Published: (2025)

Generating minimal redundant and maximal irredundant sets in incidence graphs
by: Castelo, Emanuel, et al.
Published: (2026)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

Backbone colouring of chordal graphs
by: Araújo, Júlio, et al.
Published: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Nowhere-zero flow reconfiguration
by: Esperet, Louis, et al.
Published: (2025)

Chromatic discrepancy of locally $s$-colourable graphs
by: Corsini, Timothée, et al.
Published: (2025)

The Graph Coloring Game on $4\times n$-Grids
by: Brosse, Caroline, et al.
Published: (2024)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Colouring t-perfect graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

Contractions in perfect graph
by: Dupont-Bouillard, Alexandre, et al.
Published: (2024)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
by: Bartier, Valentin, et al.
Published: (2023)

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
by: De Meyer, Lucas, et al.
Published: (2025)

Acyclic colourings of graphs with obstructions
by: Chuet, Quentin, et al.
Published: (2022)