8 papers · 1 filter
Odd coloring graphs with linear neighborhood complexity
James Davies, Meike Hatzel, Kolja Knauer +2
We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if is the class of all circle graphs, or…
Strong odd coloring in minor-closed classes
Miriam Goetze, Fabian Klute, Kolja Knauer +3
We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.
Girth in -representable matroids
James Davies, Meike Hatzel, Kolja Knauer +2
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field and any integer , every cosimple -representable matroid with sufficiently large gi…
Boundedness and Separation in the Graph Covering Number Framework
Miriam Goetze, Peter Stumpf, Torsten Ueckerdt
For a graph class and a graph , the four -covering numbers of , namely global , union ,…
On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
Alex Koutsoutis, Kilian Krause, Chun-Hung Liu +2
We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth o…
The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number
Miriam Goetze, Torsten Ueckerdt
A proper vertex-coloring of a graph is -dynamic if the neighbors of each vertex receive at least different colors. In this note, we prove that if…