A note on uniquely 10-colorable graphs
We prove for k at most 10, that every graph of chromatic number k with a unique k-coloring admits a clique minor of order k.
Source author record
Matthias Kriesell
Matthias Kriesell appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
12works
2topics
4close collaborators
Research graph
See the researcher in context
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.
Published work
12 published item(s)
preprint2016arXiv
Antistrong digraphs
An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices $x,y$ in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph $D$ is antistrong if it contains an antidirected $(x,y)$-trail starting and ending with a forward arc for every choice of $x,y\in V(D)$. We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to $D$ makes the resulting digraph the arc-disjoint union of $k$ antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Maximal ambiguously k-colorable graphs
A graph is ambiguously k-colorable if its vertex set admits two distinct partitions each into at most k anticliques. We give a full characterization of the maximally ambiguously k-colorable graphs in terms of quadratic matrices. As an application, we calculate the maximum number of edges an ambiguously k-colorable graph can have, and characterize the extremal graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
More on foxes
An edge in a $k$-connected graph $G$ is called {\em $k$-contractible} if the graph $G/e$ obtained from $G$ by contracting $e$ is $k$-connected. Generalizing earlier results on $3$-contractible edges in spanning trees of $3$-connected graphs, we prove that (except for the graphs $K_{k+1}$ if $k \in \{1,2\}$) (a) every spanning tree of a $k$-connected triangle free graph has two $k$-contractible edges, (b) every spanning tree of a $k$-connected graph of minimum degree at least $\frac{3}{2}k-1$ has two $k$-contractible edges, (c) for $k>3$, every DFS tree of a $k$-connected graph of minimum degree at least $\frac{3}{2}k-\frac{3}{2}$ has two $k$-contractible edges, (d) every spanning tree of a cubic $3$-connected graph nonisomorphic to $K_4$ has at least $\frac{1}{3}|V(G)|-1$ many $3$-contractible edges, and (e) every DFS tree of a $3$-connected graph nonisomorphic to $K_4$, the prism, or the prism plus a single edge has two 3-contractible edges. We also discuss in which sense these theorems are best possible.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
On minimal graphs containing k perfect matchings
We call a finite undirected graph minimally k-matchable if it has at least k distinct perfect matchings but deleting any edge results in a graph which has not. An odd subdivision of some graph G is any graph obtained by replacing every edge of G by a path of odd length connecting its end vertices such that all these paths are internally disjoint. We prove that for every k>0 there exists a finite set of graphs S(k) such that every minimally k-matchable graph is isomorphic to a disjoint union of an odd subdivision of some graph from S(k) and any number of copies of the complete graph on two vertices.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Threshold Colorings of Prisms and the Petersen Graph
Let $G$ be a graph, $r \geq t$ integers, and $N \subseteq E(G)$. An $(r,t)$-threshold-coloring of $G$ with respect to $N$ is a mapping $c: V(G) \rightarrow \{0,\ldots,r-1\}$ such that $|c(u)-c(v)| \leq t$ for every $uv \in N$ and $|c(u)-c(v)|>t$ for every $uv \in E(G) \setminus N$. A graph is total threshold colorable if there exist integers $r,t$ such that for every $N \subseteq E(G)$, $G$ admits an $(r,t)$-threshold-coloring with respect to $N$. We show that every prism is total threshold colorable, and that the Petersen graph is total threshold colorable. In contrast to this fact we show that Moebius ladders are not total threshold colorable, from which it follows that there is no characterization of being total threshold colorable in terms of a finite set of forbidden subgraphs.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Unique colorability and clique minors
For a graph G, let h(G) denote the largest k such that G has k pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let s(G) denote the largest k such that G has k pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger's conjecture states that h(G) is at least c(G), where c(G) is the chromatic number of G. Seymour conjectured that s(G) is at least |V(G)|/2 for all graphs without antitriangles, i. e. three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one c(G)-coloring. We prove generalizations of (i) if c(G) is at most 6 and G has exactly one c(G)-coloring then h(G) is at least c(G), where the proof does not use the four-color-theorem, and (ii) if G has no antitriangles and G has exactly one c(G)-coloring then s(G) is at least |V(G)|/2.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Axioms for infinite matroids
We give axiomatic foundations for non-finitary infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. This completes the solution to a problem of Rado of 1966.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Minimal Connectivity
A k-connected graph such that deleting any edge / deleting any vertex / contracting any edge results in a graph which is not k-connected is called minimally / critically / contraction-critically k-connected. These three classes play a prominent role in graph connectivity theory, and we give a brief introduction with a light emphasis on reduction- and construction theorems for classes of k-connected graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Nonseparating K4-subdivisions in graphs of minimum degree at least 4
We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
On graphs double-critical with respect to the colouring number
The colouring number col(G) of a graph G is the smallest integer k for which there is an ordering of the vertices of G such that when removing the vertices of G in the specified order no vertex of degree more than k-1 in the remaining graph is removed at any step. An edge e of a graph G is said to be double-col-critical if the colouring number of G-V(e) is at most the colouring number of G minus 2. A connected graph G is said to be double-col-critical if each edge of G is double-col-critical. We characterise the double-col-critical graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer k greater than 4 and any positive number r, there is a k-col-critical graph with the ratio of double-col-critical edges between 1- r and 1.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Vertex-disjoint directed and undirected cycles in general digraphs
The dicycle transversal number t(D) of a digraph D is the minimum size of a dicycle transversal of D, i. e. a set T of vertices of D such that D-T is acyclic. We study the following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in the underlying undirected graph of D such such that B,C are disjoint. It is known that there is a polynomial time algorithm for this problem when restricted to strongly connected graphs, which actually finds B,C if they exist. We generalize this to any class of digraphs D with either t(D) not equal to 1 or t(D)=1 and a bounded number of dicycle transversals, and show that the problem is NP-complete for a special class of digraphs D with t(D)=1 and, hence, in general.
0 citations0 reviewsNo code linkedOpen access