Daniel A. Quiroz

activity

20162026

most citedClique immersions and independence number

11 citations · 44 across the 21 of their papers we have counts for

collaborators

21 papers

math.CO2026

Odd minors or odd immersions in graphs with independence number two

Antonia Bermúdez, Bruno L. Netto, Daniel A. Quiroz

Kühn, Sauermann, Steiner and Wigderson recently disproved the Odd Hadwiger Conjecture, even for graphs with independence number 2. For this class of graphs the conjecture is known…

math.CO2026

Odd Hadwiger number and graph products

Henry Echeverría, Andrea Jiménez, Suchismita Mishra +2

The Odd Hadwiger number of a graph $G$ is the largest integer $r$ such that $G$ has a clique of size $r$ as an odd minor. In this paper, we investigate how large is the Odd Hadwige…

math.CO2026

Homomorphism counting for immersion-closed classes is not isomorphism

Andrea Jiménez, Benjamin Moore, Daniel A. Quiroz +1

Lovász proved that two graphs $G$ and $H$ are isomorphic if $hom (K, G) = hom (K, H)$ for all graphs $K$ , where $hom (G_{1}, G_{2})$ denotes the number of homomorphisms from $G_{1}$ to $G_2…

math.CO2025

Totally odd immersions of complete graphs in graph products

Henry Echeverría, Andrea Jiménez, Suchismita Mishra +2

For a graph $G$ , let $im (G)$ denote the maximum integer $t$ such that $G$ contains $K_{t}$ as an immersion. A recent paper of Collins, Heenehan, and McDonald (2023) studied the behav…

cs.DM2025

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs

Laurent Beaudou, Jan Bok, Florent Foucaud +2

The \emph{ $r$ -neighbourhood complexity} of a graph $G$ is the function counting, for a given integer $k$ , the largest possible number, over all vertex-subsets $A$ of size $k$ , of s…

math.CO2024

Colouring negative exact-distance graphs of signed graphs

Reza Naserasr, Patrice Ossona de Mendez, Daniel A. Quiroz +2

The $k$ -th exact-distance graph, of a graph $G$ has $V (G)$ as its vertex set, and $x y$ as an edge if and only if the distance between $x$ and $y$ is (exactly) $k$ in $G$ . We consid…

math.CO2023

Balanced-chromatic number and Hadwiger-like conjectures

Andrea Jiménez, Jessica McDonald, Reza Naserasr +2

Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward…

math.CO2023★ 1 cited

Boundedness for proper conflict-free and odd colorings

Andrea Jiménez, Kolja Knauer, Carla Negri Lintzmayer +7

The proper conflict-free chromatic number, $χ_{p c f} (G)$ , of a graph $G$ is the least $k$ such that $G$ has a proper $k$ -coloring in which for each non-isolated vertex there is a co…

math.CO2023

Subchromatic numbers of powers of graphs with excluded minors

Pedro P. Cortés, Pankaj Kumar, Benjamin Moore +2

A $k$ -subcolouring of a graph $G$ is a function $f : V (G) \to {0, \dots, k - 1}$ such that the set of vertices coloured $i$ induce a disjoint union of cliques. The subchromatic number…

math.CO2023★ 3 cited

Totally odd immersions in line graphs

Andrea Jiménez, Daniel A. Quiroz, Christopher Thraves Caro

The immersion-analogue of Hadwiger's Conjecture states that every graph $G$ contains an immersion of $K_{χ (G)}$ . This conjecture has been recently strengthened in the following way…

math.CO2023★ 4 cited

Biclique immersions in graphs with independence number 2

Fábio Botler, Andrea Jiménez, Carla N. Lintzmayer +3

The analogue of Hadwiger's conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{χ (G)}$ . For graphs with independence number 2, this is equ…

math.CO2022★ 3 cited

Characterizing and recognizing exact-distance squares of graphs

Yandong Bai, Pedro P. Cortés, Reza Naserasr +1

For a graph $G = (V, E)$ , its exact-distance square, $G^{[♯2]}$ , is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have d…

math.CO2022★ 2 cited

The treewidth and pathwidth of graph unions

Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz +3

Given two $n$ -vertex graphs $G_{1}$ and $G_{2}$ of bounded treewidth, is there an $n$ -vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_{1}$ and $G_{2}$ ? Our main res…

math.CO2020★ 1 cited

Clique immersions in graphs of independence number two with certain forbidden subgraphs

Daniel A. Quiroz

The Lescure-Meyniel conjecture is the analogue of Hadwiger's conjecture for the immersion order. It states that every graph $G$ contains the complete graph $K_{χ (G)}$ as an immersi…

math.CO2020

Universal arrays

Matías Pavez-Signé, Daniel A. Quiroz, Nicolás Sanhueza-Matamala

A word on $q$ symbols is a sequence of letters from a fixed alphabet of size $q$ . For an integer $k \geq 1$ , we say that a word $w$ is $k$ -universal if, given an arbitrary word of le…

math.CO2019★ 11 cited

Clique immersions and independence number

Sebastián Bustamante, Daniel A. Quiroz, Maya Stein +1

The analogue of Hadwiger's conjecture for the immersion order states that every graph $G$ contains $K_{χ (G)}$ as an immersion. If true, it would imply that every graph with $n$ ver…

cs.LO2018

Model-Checking on Ordered Structures

Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…

math.CO2017★ 3 cited

Colouring exact distance graphs of chordal graphs

Daniel A. Quiroz

For a graph $G = (V, E)$ and positive integer $p$ , the exact distance- $p$ graph $G^{[♮ p]}$ is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if an…

cs.LO2017★ 5 cited

Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion

Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…

math.CO2016★ 3 cited

Chromatic Numbers of Exact Distance Graphs

Jan van den Heuvel, H. A. Kierstead, Daniel A. Quiroz

For any graph $G = (V, E)$ and positive integer $p$ , the exact distance- $p$ graph $G^{[♮ p]}$ is the graph with vertex set $V$ , which has an edge between vertices $x$ and $y$ i…

math.CO2016★ 8 cited

On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz +2

The generalised colouring numbers $col_{r} (G)$ and $wcol_{r} (G)$ were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…